Concept
A consistent, effectively axiomatized formal system strong enough for arithmetic has sentences it cannot prove and, under the theorem's conditions, cannot prove its own consistency.
Understand it in one breath
A consistent, effectively axiomatized formal system strong enough for arithmetic has sentences it cannot prove and, under the theorem's stated conditions, cannot prove its own consistency. Gödel announced the first result at 24 in 1930 and stated both theorems in his 1931 paper.
At a glance
System | Strength | Gödel’s theorem applies? | Consequence |
|---|---|---|---|
Presburger arithmetic (addition only) | Weak | ✗ — complete and decidable | Computable; every truth is provable |
Turing-machine halting problem | Computation model | Separate theorem | Turing’s 1936 undecidability result |
Peano arithmetic (PA) | Strong | ✓ First incompleteness theorem | Truths of PA that cannot be proved within PA |
ZFC set theory | Very strong | ✓ (assuming consistency) | CH independence is a separate result of Gödel and Cohen |
Propositional logic | Weak | ✗ — decidable | SAT-solving algorithms |
A consistent, effectively axiomatized formal system strong enough for arithmetic has sentences it cannot prove. The halting problem and CH independence are related but distinct results.
Key formula
Key moments
Hilbert’s program — formalization and consistency
In the early 1920s Hilbert proposed formalizing classical mathematics axiomatically and justifying its consistency by finitary methods.
Gödel — the paper stating two theorems at age 24
After announcing the first result in Königsberg in 1930, Gödel’s 1931 paper stated both incompleteness theorems and exposed limits to the aims of Hilbert’s program.
Turing — the halting problem
Turing proved that no general algorithm can determine whether every possible program will halt — a distinct limit result about computability.
Goodstein’s theorem — a natural example of incompleteness
A statement about ordinary natural numbers was shown to be unprovable within Peano arithmetic, giving a concrete example beyond Gödel’s deliberately self-referential construction.
Modern applications
Undecidability and the halting problem, debates about the limits of AI, limits of formal verification, and the analysis of self-referential systems.
Beyond MathVoyage
Loading…