[FOM] 18 Word Proof of the Godel, Rosser and Smullyan Incompleteness Theorems
panu.raatikainen at helsinki.fi
Fri Jul 16 09:21:41 EDT 2010
"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
* * *
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
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
E-mail: panu.raatikainen at helsinki.fi
More information about the FOM