Kurt Godel, the greatest logician of our time, startled the world of mathematics in 1931 with his Theorem of Undecidability, which showed that some statements in mathematics are inherently "undecidable." His work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum theory brought him further worldwide fame. In this introductory volume, Raymond Smullyan, himself a well-known logician, guides the reader through the fascinating world of Godel's incompleteness theorems. The level of presentation is suitable for anyone with a basic acquaintance with mathematical logic. As a clear, concise introduction to a difficult but essential subject, the book will appeal to mathematicians, philosophers, and computer scientists.
Author(s): Raymond M. Smullyan
Series: Oxford Logic Guides
Publisher: Oxford University Press
Year: 1992
Language: English
Pages: 156
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
