[FOM] Diagonalization and Self-Reference

[Richard G Heck]

Let me take a moment to clarify the question I meant to be raising about 
diagonalization.

Consider the following argument for the inconsistency of the T-scheme.
(2)    The rhs of (2) is true iff the lhs of (2) is false.
Suppose that (2) is true. Then its rhs and lhs have the same 
truth-value. But that is impossible, since (2) says, in effect, that the 
rhs and lhs have different truth-values. So (2) is false. So its rhs and 
lhs have different truth-values. Suppose the lhs of (2) is true. Then 
its rhs is also true. Contradiction. So the lhs is false. But then the 
rhs must also be false. Contradiction, again. And contradiction overall.

Question: How can this argument be formalized in PA, where the language 
is the standard language of arithmetic plus 'T(x)'? What makes the 
problem interesting is that the most obvious way of trying to do it 
fails, that being to consider something like:
        (Ey)(rhs(x,y) & T(y)) <--> (Ey)(lhs(x,y) & ~T(y))
where 'rhs(x,y)' represents 'y is the rhs of the biconditional x', etc., 
and then diagonalize. When we do so, what we get is a sentence P such that:
(3)    PA |- P <--> [(Ey)(rhs(*P*,y) & T(y)) <--> (Ey)(lhs(*P*,y) & ~T(y))]
But P itself is not the sentence on the rhs side here. Rather, P is 
itself an existential formula. Hence, P has no rhs, and no lhs, either; 
so both halves of the rhs of (3) are provable; and so P is provable and 
true, not inconsistent with the T-scheme. The intuitive proof of (2)'s 
inconsistency given above simply fails. We can begin by saying, "Suppose 
that P is true", but then the next step, "Then its rhs and lhs have the 
same truth-value", simply can't be taken, for the simple reason that P 
has neither a rhs nor a lhs.

Jeff Ketland reminded me that I should have emphasized that this problem 
would not arise in a language that had primitive function symbols for 
all primitive recursive functions (and, in particular, a symbol for 
diagonalization). A similar point has been made by Sandy Hodges, who 
shows how, using function-symbols for concatenation and the like, we can 
get truly self-referential sentences. But my question concerned the 
language of arithmetic, not such extensions of it, as harmless as these 
may be for /some/ purposes.

Torkel Franzen has convinced me that I was a bit too quick to dismiss 
the Goedel sentence as self-referential, too. Let's be pedantic (and 
follow Boolos and Jeffrey). Let D(z,y) be a formula representing 
diagonalization, where y is the diagonalization of z iff z is the Goedel 
number of a formula A(x), with just 'x' free, and y is the Goedel number 
of the formula: (Ex)(x = Z & A(x)). (Here "Z" is the numeral for z.) Now 
let n be the Goedel number of
    (Ey)(D(x,y) & ~Bew(y)).
Then the Goedel sentence, G, is:
    (Ex)[x = N & (Ey)(D(x,y) & ~Bew(y))],
and *G* is provably the y in question. So we get the familiar:
(4)    G <--> ~Bew(*G*).
So, in some sense, G does refer to itself, since it puts enough 
conditions on y to guarantee that *G* is the relevant number, though it 
does not refer to itself by name, if I may borrow Hodges's words.

What I'm trying to suggest is that this difference, as unimportant as it 
may be for some purposes, does matter, and even can matter for 
mathematical (and not just "philosophical") purposes. Both these points 
follow, or so it seems to me, from diagonalization's failure to capture 
the intuitive inconsistency of (2). That just shows that the technique 
of diagonalization in the language of arithmetic does not produce 
sentences that are in the strictest sense self-referential. G refers to 
itself only in the sense in which P, in (3), refers to itself, and that 
sense, whatever it is, is insufficient to support the intuitive argument 
for (2)'s inconsistency, which argument depends upon taking the 
self-reference in (2) completely seriously.

Richard Heck
Professor of Philosophy
Harvard University