Gödel's Incompleteness Theorems (Elements in Philosophy and Logic)

Description

This Element takes a deep dive into Gödel's 1931 paper giving the first presentation of the Incompleteness Theorems, opening up completely passages in it that might possibly puzzle the student, such as the mysterious footnote 48a. It considers the main ingredients of Gödel's proof: arithmetization, strong representability, and the Fixed Point Theorem in a layered fashion, returning to their various aspects: semantic, syntactic, computational, philosophical and mathematical, as the topic arises. It samples some of the most important proofs of the Incompleteness Theorems, e.g. due to Kuratowski, Smullyan and Robinson, as well as newer proofs, also of other independent statements, due to H. Friedman, Weiermann and Paris-Harrington. It examines the question whether the incompleteness of e.g. Peano Arithmetic gives immediately the undecidability of the Entscheidungsproblem, as Kripke has recently argued. It considers set-theoretical incompleteness, and finally considers some of the philosophical consequences considered in the literature. Cover Title Page Copyright Page Gödel’s Incompleteness Theorems Contents Introduction The First Incompleteness Theorem 1 The First Version of the Proof 2 Gödel's ``Intuitionistically Acceptable'' Second Proof of the First Incompleteness Theorem 2.1 Ingredients of the Proof 2.1.1 ω-consistency 2.1.2 Arithmetization/Gödel-Numbering 2.1.3 Primitive Recursion 2.1.4 Strong Representability or, in Gödel’s Terminology, “Decidability” 2.1.5 The Fixed Point Theorem 2.2 The Proof 2.3 Gödel’s Immediate Commentary 2.3.1 Decidability Revisited 2.3.2 The Fixed Point Theorem 2.3.3 ω-consistency, ω-inconsistency, and Nonstandard Models of Arithmetic 2.4 Gödel Remarks Further on the Scope of the First Incompleteness Theorem 2.4.1 The Mysterious Footnote 48a 2.4.2 Section 3 of 1931 2.4.3 Gödel and the Entscheidungsproblem 2.5 Computability 2.5.1 Proving the First Incompleteness Theorem fromthe Existence of a Noncomputable Set 2.6 The Fixed Point Theorem from the Computability Point of View The Second Incompleteness Theorem 3 The Unprovability of Consistency 4 Löb Conditions and Adequacy 4.1 Axiomatizations 4.2 Numbering 4.3 Consistency is Provable with Extra Assumptions 4.3.1 Gentzen 4.3.2 Turing 4.4 Does the Second Incompleteness Theorem Refutethe Hilbert Program’s Demand for an Internal Consistency Proof? Variations and Philosophical Consequences 5 Other Proofs of the First and Second Theorems 5.1 Kuratowski’s Proof 5.2 Robinson’s Diagonal-Free Proof 5.3 Smullyan’s Logic-Free Proof 5.4 A Model-Theoretic Proof of the First Incompleteness Theorem from Tennenbaum’s Theorem 6 Mathematical Incompleteness 6.1 Paris-Harrington 6.2 Kruskal’s Theorem 6.3 Weiermann’s Phase Transition Results 7 Set Theoretical Incompleteness 8 Further Philosophical Consequences of the Incompleteness Theorems 8.1 Absolute Undecidability 8.2 Intuition, Insight, and Meaning 8.3 Conclusion Glossary G.1 Peano Arithmetic PA G.2 Primitive recursive arithmetic PRA G.3 The Theory Q G.4 The Theory R G.5 The Arithmetical Hierarchy References Acknowledgements