[FOM] Diagonalization and Self-Reference
Richard G Heck
heck at fas.harvard.edu
Sun Dec 29 14:08:46 EST 2002
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
More information about the FOM
mailing list