Goedel's proof: With a foreword by D.R. Hofstadter

Cover......Page 1
Preface......Page 8
Contents......Page 12
I The General Idea Behind Gödel's Proof......Page 18
I. Abstract Forms of Gödel's and Tarski's Theorems......Page 22
II. Undecidable Sentences of ℓ......Page 27
§1. Syntactic Preliminaries......Page 31
§2. The Notion of Truth in ℓ_E......Page 34
§3. Arithmetic and arithmetic Sets and Relations......Page 36
§4. Concatenation to the Base b......Page 37
§5. Gödel Numbering......Page 39
§6. Diagonalization and Gödel Sentences......Page 41
§1. The Axiom System P.E.......Page 45
§2. Preliminaries......Page 47
§3. Arithmetization of the Syntax of P.E.......Page 50
§4. Gödel's Incompleteness Theorem for P.E.......Page 53
I. The Incompleteness of P.A.......Page 57
§3. Concatenation to a Prime Base......Page 60
§4. The Finite Set Lemma......Page 62
§5. Proof of Theorem E......Page 63
§6. The Incompleteness of Peano Arithmetic......Page 66
II. More on Σ_1-Relations......Page 67
V Gödel's Proof Based on ω-Consistency......Page 73
§l. A Basic Incompleteness Theorem......Page 75
§2. The ω-Consistency Lemma......Page 78
II. Σ_0-Completeness......Page 83
§4. Some Σ_0-complete Subsystems of Peano Arithmetic......Page 85
§6. The ω-Incompleteness of P.A......Page 90
VI Rosser Systems......Page 92
§l. Some Abstract Incompleteness Theorems After Rosser......Page 93
§2. A General Separation Principle......Page 94
§3. Rosser's Undecidable Sentence......Page 98
§4. The Gödel and Rosser Sentences Compared......Page 99
§5. More on Separation......Page 101
§1. Shepherdson's Representation Theorem......Page 103
§2. Exact Rosser Systems......Page 107
§3. Some Variants of Rosser's Undecidable Sentence......Page 110
§4. A Strengthening of Shepherdson's Theorems......Page 113
§1. Definability and Complete Representability......Page 114
§2. Strong Definability of Functions in S......Page 115
§3. Strong Definablity of Recursive Functions in (R)......Page 117
§4. Fixed Points and Gödel Sentences......Page 119
§5. Truth Predicates......Page 121
§1. Provability Predicates......Page 123
§2. The Unprovability of Consistency......Page 125
§3. Henkin Sentences and Löb's Theorem......Page 126
X Some General Remarks on Provability and Truth......Page 129
§l. An Analogue of the Tarski-Gödel Theorem......Page 133
§2. Normal and Stable Reasoners of Type 1......Page 134
§3. Rosser Type Reasoners......Page 137
§4. The Consistency Problem......Page 139
§5. Self-Fulfilling Beliefs and Löb's Theorem......Page 141
II. Incompleteness Arguments in a General Setting......Page 143
III. Systems of Type G......Page 146
IV. Modal Systems......Page 149
References......Page 153
Index......Page 155