[FOM] Sentences that "speak about themselves"
Haim Gaifman
hg17 at columbia.edu
Wed Oct 15 14:34:38 EDT 2003
Two months ago Avron asked about the possibility of
a mathematical characterization of Goedel sentences, and, more
generally, sentences that "speak about themselves".
There were also some questions about the provability-equivalence
of different versions of the Goedel sentence. The latter
have definite answers, provided they are clearly defined (e.g.,
the kinds of Goedel numberings under consideration have to be
specified). But there is no clear characterization of sentences that
"speak about themselves", or that "say of themselves
that they are not provable".
This is because the notion of "the number, or the coded object,
a sentence is about" is not amenable
to precise treatment. It is an epistemic notion that reflects
some useful way of reading the sentence.
The surest, most precise way of saying what a sentence
says is to repeat the sentence. If we use English, and the sentence
is in a formal language, we have to use some translation,
which, we tacitly assume, is sufficiently literal.
But the present problem is about a non-literal reading that
expresses a certain way of viewing the sentence.
And such an epistemic notion cannot be treated mathematically.
There are quite a few parameters to be fixed: the assigning of names to
natural numbers, the coding (Goedel numbering), GN( ), of sentences into
numbers, the background theory T, the wff Bew(x) that we employ to
say that x is provable in T.
Relative to these parameters [assuming the usual conditions about
representability in T of the syntactic notions, and about
Bew()] we might say that a Goedel sentence, G,
is one for which the following biconditional is provable in T:
(1) G <--> ~Bew('GN(G)')
(where '~' is negation). But does such a sentence "speak about
itself"? If so, then by the same
token also the sentence, L, for which the following is provable
(2) L <--> Bew('GN(L)')
speaks about itself; it says of itself that
it is provable. But then it turns out that 0=0 says of itself that
it is provable, which is a very strange way of reading 0=0.
Yet, from the general perspective of Loeb's theorem, we can regard
0=0 as a trivial instance of a sentence that says of itself
that it is provable.
More generally, if A <-->B is provable (from the axioms we take for
granted), does it follow that A and B "say the same thing"
or "are about the same numbers"? If we adopt this view,
then all provable sentences say the same thing as
0=0. On the other hand if B is trivially equivalent to A--for example,
B = A&(0=0)--then we do want to say that they say the "same" or
"nearly the same" thing. The notion is obviously graded, along more
than one dimension, and it reflects the extent to which the connection
between A and B is obvious, or natural. Fermat's last theorem is about
diophantine equations, but I am told that (in the right perspective
of the experts) it is also about elliptic curves.
For the same reasons, we cannot say that if A(x) is a wff with a
free variable and 'n' is the "standard name" of n, then A('n') is about n;
for A('n') can be trivially equivlant to B('m'), where m is a
different number. Furthermore, even a literal reading (or translation)
does not help here, because we have to presuppose some convention
for associating with numbers standard names.
Consider: (i) '2^40 +1 is prime' (ii) '1099511627777 is prime'
(iii) '0''''... is prime' (with 1099511627777 strokes after '0').
Are they all equally "about" 1099511627777 ? and if so, how far can we
go in using terms whose equality is far from obvious? Our English
usage is not of help here. Our notation is historically
determined, and we change it according to context.
For small enough numbers, we use decimal notation; does this mean
that there is something special about it, which makes it more
representative then binary notation? or hexadecimal?
For larger numbers we use some exponential notation, or some
other descriptive tool. The stroke notation '0'''...' is of course
never used in practice.
Finally, in order to represent sentences, we use some code and this
introduces another arbitrary factor. The following can be shown:
There is a Goedel numbering, GN*, of wffs and terms, which has the
usual required properties, such that the Goedel sentence "literally"
refers to itself:
(3) 0 = GN*(~Bew*('0'))
where '0' is the constant denoting 0, and Bew*(x) is (Ey)Proof*(y,x),
and Proof*( , ) represents the proof relation, with respect to the Goedel
numbering GN*. (The language is the usual Peano language, based on
s( ),+ and x).
This does not mean that ~Bew*('0') "speaks about itself" any better than
the Goedel sentence, G, for which (1) is provable.
It only means that we can smuggle a lot into the coding.
The fact that no precise definition can be given to "speaking about
itself", does not, of course, detract from the crucial role of this notion.
It is only by regarding certain sentences in this way
that we can understand Goedel's proof.
More information about the FOM
mailing list