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

[Harvey Friedman]

On Jul 11, 2010, at 9:10 PM, Charlie V wrote:

> Godel’s 1931 First Incompleteness Theorem is equivalent to the  
> assertion that truth and provability do not coincide.

This is incorrect. You are ignoring hidden assumptions, which is an  
important consideration for 18 word proofs.

The usual statements are

1. There is a true sentence that is not provable.
2. There is a sentence that is neither provable nor refutable.

To get 1, your argument requires that a) every provable sentence is  
true, b) the set of provable sentences is recursively enumerable.
To get 2, your argument also requires that a) every provable sentence  
is true, b) the set of provable sentences is recursively enumerable.

But then you have the problem of not having said enough about truth  
and provability for b) to make sense. Then once you explain what b)  
means, other issues arise concerning a), and you can't even begin to  
do anything about this in 18 words.

So in addition to this not being satisfactory definitionally, it is  
not sensitive to the weaker assumptions used by Goedel and Rosser,  
which in turn lead to stronger theorems involving general classes of  
formal systems:

Goedel's proof of 1 for PA requires less - that no sentence and its  
negation are provable.

Goedel's proof of 2 for PA requires less - that every provable Sigma01  
sentence is true.

Rosser proved 2 for PA using even less - that no sentence and its  
negation are provable.

Furthermore, R. Robinson identified a very weak finite fragment Q of  
PA such that what Rosser proved above holds with PA replaced by any  
extension of Q.

> Rosser’s 1936 extension is equivalent to the assertion that  
> provability and unrefutability do not coincide.  Smullyan’s 1961  
> Dual Form Theorem is equivalent to the assertion that truth and  
> unrefutability do not coincide.
>
> We can prove that these three sets, the true, provable and  
> unrefutable sentences, are three different sets by referring to the  
> property of being recursively enumerable, as stated in theorems of  
> the Theory of Computation:
>
> The sets of true, provable and unrefutable sentences pairwise differ  
> w.r.t. whether they or their complement is r.e.

We can resurrect what you are trying to say if we focus only on  
systems like PA - and take the realist viewpoint.

Of course, the relevant recursion theory was not around when Goedel  
proved his incompleteness theorems.

Once you try to make what you say mathematically rigorous, the usual  
complexities enter in as to the proper formulations.

Harvey Friedman