Gödel's incompleteness theorems

A formal system specifies axioms and rules for deriving theorems. In 1931 Kurt Gödel published a paper that used arithmetic to study the proofs produced by such systems. His method assigns natural-number codes to symbols, formulas and proof sequences, making it possible for arithmetic formulas to represent facts about formal proofs. A diagonal or fixed-point construction then yields a sentence linked to a claim about its own provability. Saying that this sentence simply 'says it cannot be proved' is a useful shorthand, but the precise argument concerns a technical relation between formulas, proof codes and a specified system.

In a standard modern formulation, any consistent, effectively axiomatized formal theory containing Robinson arithmetic Q has a sentence that the theory can neither prove nor refute. This means the theory is incomplete: its own rules do not decide every sentence in its language. Gödel's 1931 argument established incompleteness under a stronger consistency condition for ruling out a proof of the sentence's negation. In 1936, J. Barkley Rosser modified the construction so that consistency alone suffices for the existence of an undecidable sentence. The undecidability here is relative to the particular theory; it is not the claim that no proof could exist in any possible system.

A sufficiently strong formal theory can encode a statement asserting that it has no proof of a contradiction. If the theory is consistent and the formalized provability predicate meets the conditions needed for the theorem, the theory cannot prove this arithmetized consistency statement from within its own axioms and rules. This is a result about derivability inside the theory, not a ban on proving its consistency by using a stronger theory or other accepted mathematical reasoning. The exact formal statement depends on how the system's provability and consistency are represented.

The theorems constrained the hope, central to David Hilbert's program, that a single effective and consistent axiomatic system strong enough for arithmetic could settle every mathematical question of the relevant kind and establish its own consistency by its own means. They do not show that mathematics is contradictory, that every mathematical truth is unprovable, or that a sentence independent of one theory is unprovable absolutely. An independent sentence may be added as an axiom to a stronger theory; if that extension remains consistent and effectively axiomatized while still expressing arithmetic, the incompleteness result applies to it as well and produces a new sentence it cannot decide.

1931: Gödel publishes his incompleteness results in 'Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I' (On Formally Undecidable Propositions of Principia Mathematica and Related Systems I). 1936: J. Barkley Rosser publishes a strengthened first incompleteness result that reduces the consistency assumption needed to obtain an undecidable sentence.