Godel's Incompleteness Theorem

Kurt Gödel's Incompleteness Theorem (1931) states that any formal mathematical theory powerful enough to express arithmetical statements is either incomplete or inconsistent. The former (incompleteness) means that the are in (the language of) the theory undeduceable sentences, i.e., sentences that could not be proved, nor disproved in the theory. The latter (inconsistency) means that the theory makes it possible to deduce both a sentence and its negation, i.e., anything, making the theory entirely useless.

For the proof, Gödel managed to construct a true sentence expressible in arithmetic that claimed its own improvability. To this end, Gödel has assigned in a certain manner to any symbol, formula, and proof a number - Gödel's number - and interpreted each as a statement about that number. In a consistent theory the property of a statement of being proveable implies the property of being true. (Here we consider only first-order systems. In its generality, the statement is not true.) Thus the statement "I am improvable" can't be provable. For that would make it true but making a false claim, which is a nonsense. It can't be false either. For that would make its negation "I am provable" true and consequently the sentence itself provable and thus also true, leading to a contradiction. Thus, the only possibility for the statement "I am improvable" is to be true and hence improvable.

In the recently republished book of logical puzzles The Lady or the Tiger? R. Smullyan reminds of the island of Knights and Knaves he discussed in his wonderful collection What Is the Name of This Book?.

Every inhabitant of that island is either knight (and then always speaks truth) or a knave (and then always lies.) Some of them in Smullyan's terminology are established as such. Do not know why, but I am more at peace with the term "certified". So some of the knights as well as knaves are certified and some are not.

On that island, no fellow may claim to be a knave. Indeed, this would make a knight a liar and a knave a truthteller, in contravention of the rules of their nature. So, when it comes to announcing their identity, every inhabitant of the island would claim to be a knight. However, it is possible for someone to claim to be an uncertified knight. What can be said about such a fellow who says, "I am not a certified knight"?

A knave he could not be, for then he would not be a knight, let alone a certified one, and would make a true sentence. Which can't be.

A certified knight could not utter the sentence either, for doing that would make it false and him a liar, a knave. But an uncertified knight will be absolutely within his rights to say, "I am not a certified knight". Since he is a knight, as he says, the sentence must be true, and then affirming the fact of his lacking in certification. He comes through as an uncertified knight, which is what he indeed is.

The parallels certified/provable and knight/true are rather transparent.

References

R. Smullyan, What Is the Name of This Book?, A Touchstone Book, 1978
R. Smullyan, The Lady or the Tiger?, Dover, 2008

Back to What Is Infinity?

It was observed by Praveen Pillai that, as stated, this sentence is incorrect. Here's an excerpt from his message:

I stumbled across your page on Godel's Incompleteness Theorem today. I thought I should let you know that your sketch proof of the First Incompleteness Theorem is incorrect, as the statement "In a consistent theory the property of a statement of being proveable implies the property of being true" in the second paragraph is false. By way of illustration, consider a trivial system which has "0=1" as its only axiom and no deduction rules. This system is consistent, as the only sentence derivable within it is "0=1" (so no sentence and its negation can be derived within this system); however, under the usual interpretation, "0=1" is certainly false.

If you replace 'consistent' with 'sound' in your sentence, the sentence becomes true and the proof works (a sound system is one in which only true sentences are derivable). With the assumption of soundness (which is a stronger assumption that consistency, since soundness implies consistency), your proof yields a weakened version of Godel's First Incompleteness Theorem, which is fine by way of illustration (since to strengthen the theorem takes much more work).

71543296