Godel numbering, self-reference, and the limits of proof
In 1931, Kurt Godel proved one of the most profound results in mathematics: any consistent formal system powerful enough to express basic arithmetic contains true statements that cannot be proved within the system. This incompleteness theorem shattered the hope that mathematics could be completely formalized.
In this lesson, you will see how Godel numbers encode formulas as integers, how self-reference creates the unprovable sentence, and where different theories fall on the completeness spectrum.
Godel's first insight: formulas are just strings of symbols, and strings can be encoded as numbers. Each symbol gets a code, and a formula becomes a sequence of codes, which is then packed into a single number using prime factorization. This allows arithmetic to "talk about" its own formulas.
Key insight: Godel numbering is a bijection between formulas and natural numbers. Since arithmetic can reason about natural numbers, it can indirectly reason about its own syntax -- the key to self-reference.
Godel's second insight: using Godel numbering, one can construct a sentence G that effectively says "G is not provable." If G were provable, it would be false (since it says it isn't provable) -- contradicting consistency. So G is not provable. But then G is true! There is a true sentence that the system cannot prove.
Key insight: The construction is analogous to the liar paradox ("this sentence is false") but replaces "false" with "not provable." Truth and provability diverge: there exist true but unprovable statements.
Not all theories are incomplete. Propositional logic and Presburger arithmetic (natural numbers with addition but no multiplication) are decidable and complete. It is the combination of addition AND multiplication that creates enough expressive power for self-reference, and hence incompleteness.
Key insight: Incompleteness is not a bug but a fundamental feature of sufficiently powerful formal systems. It tells us that mathematical truth transcends any particular formal system.