Knowra Gödel's incompleteness theorems Gödel's incompleteness theorems Two 1931 results by Kurt Gödel: any consistent, effectively axiomatized system containing arithmetic contains true statements it cannot prove, and cannot prove its own consistency.
Gödel numbering : A coding assigning each symbol, formula and proof of a formal language a unique natural number. Turns statements about arithmetic into arithmetic, making the system able to talk about itself.
Hilbert's program : David Hilbert's plan to secure all mathematics on a complete, consistent, finitistically provable axiom system. Gödel's second theorem showed the program could not be carried out as stated.
Principia Mathematica : Whitehead and Russell's three-volume 1910–1913 formalization of mathematics from logic. The system whose arithmetic Gödel showed incomplete in his 1931 paper.
Presburger arithmetic : Arithmetic without multiplication; complete, consistent and decidable, unlike full Peano arithmetic. Shows incompleteness depends on multiplication, not on arithmetic alone.
Continuum hypothesis : The claim that no set is strictly between the integers and the reals in size; independent of ZFC. Gödel and Cohen proved its independence, an incompleteness phenomenon made concrete.
Gödel sentence : A sentence asserting its own unprovability in a given formal system; true if the system is consistent. The self-referential statement at the heart of the first theorem's construction.
Church–Turing thesis : The claim that every effectively computable function is computable by a Turing machine. Gödel's work on undecidability prepared the ground for the formal theory of computation.
L. E. J. Brouwer : Dutch mathematician who founded intuitionism, requiring constructive proof for mathematical existence. The intuitionist challenge to classical mathematics formed the intellectual climate of 1930.
Tarski's undefinability theorem : Truth in a formal language cannot be defined within that language itself. The sibling result explaining why the Gödel sentence concerns provability, not truth.
P versus NP problem : The open question of whether every efficiently verifiable solution is efficiently findable. Many logicians suspect proof complexity and relativization barriers relate to incompleteness.
Show all 28