Knowra Gödel's first incompleteness theorem Gödel's first incompleteness theorem The 1931 theorem that any consistent, effectively axiomatized system containing arithmetic contains true but unprovable statements. It ended Hilbert's program of formalizing all of mathematics.
Gödel numbering : A coding that assigns each symbol, formula and proof of a formal system a unique natural number. Arithmetic statements can then talk about other arithmetic statements, enabling self-reference.
Hilbert's program : The project of grounding all mathematics in a complete, consistent, finitistically provable axiom system. The theorem destroyed the central goal of completeness for arithmetic.
Gödel's second incompleteness theorem : No consistent effectively axiomatized system containing arithmetic can prove its own consistency. Its immediate companion result, proved the same year, devastating for Hilbert's program.
Goodstein's theorem : A statement about hereditary base representations whose sequences always terminate; unprovable in Peano arithmetic. Kirby and Paris showed in 1982 it is a natural sentence independent of Peano arithmetic.
P versus NP problem : The open question of whether every efficiently checkable computation has an efficient solution. A concrete statement whose independence from standard axioms remains a live possibility.
Gödel sentence : A sentence that says of itself that it is not provable in the given formal system. The fixed point constructed in the proof; neither provable nor refutable if the system is consistent.
Principia Mathematica : Whitehead and Russell's 1910–1913 formalization of mathematics, the system Gödel analyzed in 1931. The paper's title announces that incompleteness strikes this system and related ones.
Turing computability : Turing's 1936 formalization of mechanical computation via abstract Turing machines. Recasts incompleteness as undecidability: no algorithm decides all arithmetic truths.
Peano arithmetic : The standard axiom system for the natural numbers, the paradigm case of an incomplete system. The concrete system the theorem applies to, with explicit independent sentences.
Gentzen's consistency proof : Gentzen's 1936 proof of Peano arithmetic's consistency using transfinite induction up to ε₀. Shows which consistency proofs escape the second theorem, refining what is genuinely closed.
Show all 24