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

[Charlie V]

----- 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