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