Godel numbering, self-reference, and the limits of proof
In 1931 Kurt Godel showed that any consistent system strong enough for arithmetic has true statements it cannot prove. Here is how the trick works.
Pick a formula and watch each symbol become a prime raised to its code. Multiply them and one number encodes the whole formula.
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.
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 an injective encoding of formulas as natural numbers. Since arithmetic can reason about natural numbers, it can indirectly reason about its own syntax -- the key to self-reference.
Step through the five stages that build a sentence G saying "G is not provable."
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.
Click a theory to see whether it is complete, decidable, and axiomatizable. Notice where adding multiplication tips arithmetic into incompleteness.
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.
Spot a mistake or have an idea?