Preface to the Fifth Edition xi
Computability Theory
Enumerability 3
Enumerability 3
Enumerable Sets 7
Diagonalization 16
Turing Computability 23
Uncomputability 35
The Halting Problem 35
The Productivity Function 40
Abacus Computability 45
Abacus Machines 45
Simulating Abacus Machines by Turing Machines 51
The Scope of Abacus Computability 57
Recursive Functions 63
Primitive Recursive Functions 63
Minimization 70
Recursive Sets and Relations 73
Recursive Relations 73
Semirecursive Relations 80
Further Examples 83
Equivalent Definitions of Computability 88
Coding Turing Computations 88
Universal Turing Machines 94
Recursively Enumerable Sets 96
Basic Metalogic
A Precis of First-Order Logic: Syntax 101
First-Order Logic 101
Syntax 106
A Precis of First-Order Logic: Semantics 114
Semantics 114
Metalogical Notions 119
The Undecidability of First-Order Logic 126
Logic and Turing Machines 126
Logic and Primitive Recursive Functions 132
Models 137
The Size and Number of Models 137
Equivalence Relations 142
The Lowenheim-Skolem and Compactness Theorems 146
The Existence of Models 153
Outline of the Proof 153
The First Stage of the Proof 156
The Second Stage of the Proof 157
The Third Stage of the Proof 160
Nonenumerable Languages 162
Proofs and Completeness 166
Sequent Calculus 166
Soundness and Completeness 174
Other Proof Procedures and Hilbert's Thesis 179
Arithmetization 187
Arithmetization of Syntax 187
Godel Numbers 192
More Godel Numbers 196
Representability of Recursive Functions 199
Arithmetical Definability 199
Minimal Arithmetic and Representability 207
Mathematical Induction 212
Robinson Arithmetic 216
Indefinability, Undecidability, Incompleteness 220
The Diagonal Lemma and the Limitative Theorems 220
Undecidable Sentences 224
Undecidable Sentences without the Diagonal Lemma 226
The Unprovability of Consistency 232
Further Topics
Normal Forms 243
Disjunctive and Prenex Normal Forms 243
Skolem Normal Form 247
Herbrand's Theorem 253
Eliminating Function Symbols and Identity 255
The Craig Interpolation Theorem 260
Craig's Theorem and Its Proof 260
Robinson's Joint Consistency Theorem 264
Beth's Definability Theorem 265
Monadic and Dyadic Logic 270
Solvable and Unsolvable Decision Problems 270
Monadic Logic 273
Dyadic Logic 275
Second-Order Logic 279
Arithmetical Definability 286
Arithmetical Definability and Truth 286
Arithmetical Definability and Forcing 289
Decidability of Arithmetic without Multiplication 295
Nonstandard Models 302
Order in Nonstandard Models 302
Operations in Nonstandard Models 306
Nonstandard Models of Analysis 312
Ramsey's Theorem 319
Ramsey's Theorem: Finitary and Infinitary 319
Konig's Lemma 322
Modal Logic and Provability 327
Modal Logic 327
The Logic of Provability 334
The Fixed Point and Normal Form Theorems 337
Annotated Bibliography 341
Index 343