Godel's Incompleteness Theorems
Summary
Godel's Incompleteness Theorems are fundamental results showing the limitations of formal mathematics. The First Incompleteness Theorem shows that in any consistent logical system which includes arithmetic, some statements cannot be proved or disproved. Equivalently, the set of true statements about the natural numbers is undecidable. The Second Incompleteness Theorem states that no formal system which includes arithmetic can prove its own consistency, or that of a more powerful theory.
Context
This concept has the prerequisites:
- semantics of first-order logic (Godel's Incompleteness Theorems are statements about the semantics of first-order logic)
- proofs in first-order logic (Godel's Incompleteness Theorems are statements about proofs in first-order logic.)
- Godel numbering (Godel numbering is needed to construct the self-referential sentence in the proof.)
- decidability (The First Incompleteness Theorem can be viewed as a statement about decidability.)
- Church-Turing thesis (Expressing Godel's Incompleteness Theorem in terms of computability requires the Church-Turing thesis.)
Goals
- State Godel's First Incompleteness Theorem (in terms of some statements not being provable one way or the other)
- State the theorem in terms of the theory of natural numbers being undecidable
- State Godel's Second Incompleteness Theorem
- Be aware of Hilbert's program and why the second Incompleteness Theorem showed it to be impossible
- Prove the theorems
Core resources (read/watch one of the following)
-Free-
→ Notes on Logic (2013)
-Paid-
→ A Course in Mathematical Logic
A graduate textbook in mathematical logic.
- Section 7.10, "Undecidability," pages 347-350
- Section 7.11, "Incompleteness," pages 353-359
Other notes:
- Refer to Sections 6.1 and 7.1 for basic definitions and notation
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
- Section 3.5, "Incompleteness and undecidability," up through subsection "Recursive enumerability," pages 234-241
- Section 3.7, "Second Incompleteness Theorem," up to "Applications to set theory," pages 266-270
See also
-No Additional Notes-