From: CDJ 
Date: Mon, 2 Dec 1996 09:26:33 -0500
Organization: University of Pittsburgh


On Mon, 2 Dec 1996, Geoffrey Norman Watson wrote:

>   Reference to "THE Godel sentence" is a little misleading.

True, but not in virtue of the reasoning implicit in your below.

>   I have never seen
>   Goedel's paper,

It's worth looking at.

>   presumably this specifies a sentence to which this 
>   description
>   applies,

Namely the one which G referred to as being analagous to the Liar sentence
(though see Smullyan on why this isn't the bst analogy possible).

>   but the theorem itself can be proved in a number of different 
>   ways, 
>   using different sentences.

And in some ways that don't make use of diagonalization even. I think.

>   For instance, Boolos and Jeffrey in "Computability and Logic" use a sentence
>   equivalent to "we cannot prove that 0=1", since they are mainly concerned 
>   with the consistency of arithmetic.

>   Whereas, if I recall correctly, Kleene
>   in his textbook uses a more complicated sentence that "asserts its own 
>   unprovability", since he is more concerned with general issues of provability
>   and truth.

And these two are where you forget that _two_ theorems are commonly
attributed to Godel: the incompleteness of arithmetic, and the
unprovability of the consistency of arithmetic. (Though curiously enough,
G didn't actually supply a proof of the second theorem in his 1931.) Your
first applies to the latter, while your second applies to the former.

Nonetheless, as you say, speaking of "the Godel sentence" is not good. The
reason is that there are certain abstract properties which sentences
"like" the one G originally made have which suffice for the job G put to
it. See Smullyan's book for the general concept of _godel sentence_. It's
called something like "Godel's Incompleteness Theorems", and the concept
is introduced within the first 20 pages.

CDJ