Frank Morgan

My senior seminar on “The Big Questions” asked me for a succinct explanation of Gödel’s Incompleteness Theorem, a radical result which I’m beginning to think is a simple one.Gödel’s Incompleteness Theorem says roughly that in any consistent model including arithmetic, there are true statements which cannot be proved. The idea of the proof is to consider the statement:

“This statement cannot be proved.”

If it could be proved, what it says would be true, and it says it cannot be proved. Hence it is unprovable and therefore what it says is true.

The trouble with this proof is that the statement is self-referential. Mathematicians and logicians long ago discovered that unregulated self-reference leads to contradictions and outlawed it.

Gödel’s proof begins by encoding every statement by a natural number, called the Gödel number of the statement. For example, the statement “n is even” might be encoded by some huge Gödel number g:

= “n is even.”

Now consider the weird statement “ is not provable.” It is encoded by some Gödel number N:

= “ is not provable.”

Now look what follows by taking n = N:

= “ is not provable.”

Without violating the axioms, Gödel has presented a statement which accidentally refers to itself. As before, it is unprovable and hence true.