[FOM] 18 Word Proof of the Godel, Rosser and Smullyan Incompleteness Theorems
Charlie V
axiomsandrules at yahoo.com
Tue Jul 20 16:22:18 EDT 2010
----- Original Message ----
From: Panu Raatikainen <panu.raatikainen at helsinki.fi>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Fri, July 16, 2010 9:21:41 AM
Subject: Re: [FOM] 18 Word Proof of the Godel, Rosser and Smullyan
Incompleteness Theorems
> 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'slogic book (the 2001 edition)).
But you can get three concrete undecidable sentences utilizing a lot less proof
by noting more of my post, viz,
"When any one of these sets, P, is expressible or representable, the sentence
that expresses or represents, respectively, 'This is in P.' is undecidable."
This requires only the Recursion Theorem and includes:
1. Since unprovability is expressible: The sentence that expresses "This is not
provable." is undecidable.
2. Since refutability is expressible: The sentence that expresses "This is
refutable." is undecidable.
3. Since refutability is representable: The sentence that represents "This is
refutable." is undecidable.
> This I would happily call equivalent with Gödel's first incompleteness
theorem.
And what would you call it if you get three undecidable sentences?
Charlie Volkstorf
Cambridge, MA
--
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/
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list