Mathematical Logic
Gödel's Incompleteness Theorems
In 1931, a 25-year-old Kurt Gödel destroyed Hilbert's program with a single theorem. Any sufficiently rich mathematical theory contains true statements that cannot be proved within it. Mathematics is fundamentally larger than any of its formalizations.
- Theoretical limits of program verification: correctness of all programs cannot be proved
- Cryptography: some complexity statements may be undecidable
- Philosophy of mind: Lucas's argument about the irreducibility of human thought to an algorithm
The First Incompleteness Theorem
Gödel's first incompleteness theorem: any consistent formal system T, strong enough to encode elementary arithmetic, is syntactically incomplete-there exists a formula G such that neither G nor ¬G is derivable from T.
The Gödel sentence G is true (in the standard model ℕ) but unprovable in T. This doesn't mean mathematics 'doesn't know' the truth-we know G is true by reasoning outside system T. The system cannot 'see' this truth from within.
What does Gödel's first incompleteness theorem state?
The Second Incompleteness Theorem
Gödel's second incompleteness theorem: a consistent formal system T, strong enough to encode arithmetic, cannot prove its own consistency. The formula Con(T)-expressing 'T is consistent'-is not derivable from T.
The second theorem means mathematics is inconsistent
The second theorem means the system cannot confirm its own consistency. It may well be consistent-we simply cannot prove this from within the system.
It's like a judge being unable to objectively testify in their own case. A system's consistency can be proved in a stronger meta-system-but then the meta-system's consistency becomes the question.
Why did the second theorem destroy Hilbert's program?
Gödel Numbering
Gödel numbering is a technical device: encoding syntactic objects (formulas, proofs) as natural numbers. This allows arithmetic to 'talk about itself'-expressing metamathematical statements inside the system.
Modern proofs use lambda calculus or recursive functions instead of prime numbers, but the principle is the same. The crucial point is that the coding is primitive recursive: this guarantees PA can work with codes and recover the originals.
Why is Gödel numbering needed in the incompleteness proofs?
Self-Reference and the Diagonal Lemma
The Diagonal Lemma (self-reference lemma): for any formula F(x) there exists a sentence G such that T ⊢ G ↔ F(⌈G⌉). This is the mathematically precise way to build a formula 'talking about itself'.
Tarski's undefinability theorem is a close cousin of Gödel's theorems: the predicate Truth(x) 'x is a true sentence of PA' cannot be defined within PA. This is stronger than incompleteness: not just undecidable sentences, but the principled undefinability of truth itself.
Self-Reference and the Diagonal Lemma?
Review the concept above.
Incompleteness Theorems: Key Takeaways
- First theorem: in any rich consistent theory, there are true unprovable sentences
- Second theorem: the theory cannot prove its own consistency
- Gödel numbering: encoding syntax as numbers allows arithmetic to speak about itself
- Diagonal Lemma: for any property, a formula asserting that property about itself can be built
- Tarski's theorem: the concept of 'truth' is not definable within a sufficiently rich system
From Logic to Computation
Gödel's ideas connect directly to the undecidability of the halting problem by Turing. Unprovability ≈ uncomputability. The next lesson examines model theory-another tool for studying formal systems.
Вопросы для размышления
- The Gödel sentence G is true but unprovable in PA. How do we even know G is true?
- Do the incompleteness theorems mean mathematics is 'unfinished'? Or that it's richer than any of its formalizations?
- If we add G as a new axiom to PA, we get a stronger system. But the theorem applies to it too. What does this mean?