Mathematical Logic
Goedel Incompleteness Theorems
Hilbert's program (1920): axiomatize all of mathematics completely and consistently. Goedel (1931): impossible. One of the deepest mathematical discoveries of the 20th century - the limits of what formal systems can know about themselves.
- Turing's halting problem: undecidability of HALT is a direct consequence of the diagonal argument Goedel applied to arithmetic
- Independence of CH from ZFC: Goedel and Cohen proved that the Continuum Hypothesis is not decided by the standard axioms of set theory
- Program verification: complete automatic verification of arbitrary programs is impossible - a consequence of undecidability theorems
- Proof assistants Lean and Coq: operate in systems with the axiom of choice and univalence, each generating new independent statements
Goedel Numbering and Diagonalization
In 1931, 25-year-old Kurt Goedel proved: in any sufficiently rich consistent formal system containing Peano arithmetic, there exists a true statement that is unprovable within the system. Hilbert's program - axiomatize all of mathematics completely and consistently - turned out to be unachievable.
The theorem applies to any recursively axiomatized system containing sufficient arithmetic: PA, ZFC, ZF, type theory. The stronger the system, the more new independent sentences it generates - adding G as an axiom creates new G' by the same construction.
What does the first Goedel incompleteness theorem state?
First Goedel theorem: in any consistent formal system S containing the arithmetic of natural numbers, there exists a sentence G such that neither G nor neg G is provable in S.
Consequences for the Foundations of Mathematics
The Goedel theorems have concrete mathematical consequences. The Continuum Hypothesis (CH) is independent of ZFC: Goedel (1940) proved its consistency, Cohen (1963) proved the consistency of its negation. The Axiom of Choice is independent of ZF. The existence of large cardinals is neither provable nor refutable in ZFC.
Connection to computability: the Goedel theorem and Turing's undecidability of the halting problem are one family of diagonal arguments. Goedel encodes syntax in arithmetic; Turing encodes programs as numbers. Both constructions create a self-referential object that refutes completeness.
What does the second Goedel theorem state?
Second Goedel theorem: if S is recursively axiomatized, contains sufficient arithmetic, and is consistent, then S does not prove Con(S). This defeats Hilbert's program: a finitary justification of the consistency of mathematics is impossible.
Итоги
- Goedel numbering: formulas are mapped to numbers via prime factorization, allowing arithmetic to talk about its own syntax
- Diagonal lemma: for any predicate P there exists G equivalent to P(ulcorner G urcorner)
- First theorem: in consistent S containing PA, there exists G: S proves neither G nor neg G
- Second theorem: S does not prove Con(S) - Hilbert's program is unachievable
- CH is independent of ZFC: one of the most fundamental results of 20th-century mathematics follows from Goedel's technique
- Connection to Turing: the halting problem and Goedel theorems are one class of diagonal self-application arguments