[FOM] 18 Word Proof of the Godel, Rosser and Smullyan Incompleteness Theorems

[Panu Raatikainen]

"Charlie V" <axiomsandrules at yahoo.com>:

>> It does not provide a concrete example of a true but unprovable statement.
>
> Incompleteness requires only that an undecidable (unprovable and  
> unrefutable) sentence be shown to exist.

True enough. But usually, when one is talking about "Gödel's first  
incompleteness theorem" and its proof, one means more than this. For  
this reason, I thought that the claim in your first posting that  
"Godel’s 1931 First Incompleteness Theorem is equivalent to the  
assertion that truth and provability do not coincide" may be slightly  
misleading. But surely this is largely a verbal issue.


>> More adequately, one could call this  a version of Tarski's theorem.
>
> Exactly what is a version of what?  My 18 word proof proves 3  
> theorems.  Are you saying that all three theorems are versions of  
> Tarski’s Undecidability Theorem?

You must mean "Tarski's undefinability theorem"...
No I am saying that the first claim, repeated also above, that "truth  
and provability do not coincide" is; or, more exactly, a consequence  
of it, together with not-so-deep second premise that provability is  
definable, or "expressible", as you correctly point out.


Please note that I am not really disagreeing here on anything  
substantial. Recursion-theoretic approach to the issue is certainly  
very illuminating.

* * *

Actually, as Herbert Enderton also emphasized in a private message,  
you can in fact get a concrete undecidable sentence by utilizing a bit  
more the tools of recursive function theory, e.g. by noting that the  
set of true sentences is productive. (see, for example,pages 257-258  
of the second edition of Enderton's
logic book (the 2001 edition)).  This I would happily call equivalent  
with Gödel's first incompleteness theorem.



All the Best

Panu



-- 
Panu Raatikainen

Ph.D., Academy Research Fellow,
Docent in Theoretical Philosophy

Department of Philosophy, History, Culture and Art Studies
P.O. Box 24  (Unioninkatu 38 A)
FIN-00014 University of Helsinki
Finland

E-mail: panu.raatikainen at helsinki.fi
http://www.mv.helsinki.fi/home/praatika/