| |
| |
| Preface to the Fifth Edition | |
| |
| |
| Computability Theory | |
| |
| |
| |
| Enumerability | |
| |
| |
| |
| Enumerability | |
| |
| |
| |
| Enumerable Sets | |
| |
| |
| |
| Diagonalization | |
| |
| |
| |
| Turing Computability | |
| |
| |
| |
| Uncomputability | |
| |
| |
| |
| The Halting Problem | |
| |
| |
| |
| The Productivity Function | |
| |
| |
| |
| Abacus Computability | |
| |
| |
| |
| Abacus Machines | |
| |
| |
| |
| Simulating Abacus Machines by Turing Machines | |
| |
| |
| |
| The Scope of Abacus Computability | |
| |
| |
| |
| Recursive Functions | |
| |
| |
| |
| Primitive Recursive Functions | |
| |
| |
| |
| Minimization | |
| |
| |
| |
| Recursive Sets and Relations | |
| |
| |
| |
| Recursive Relations | |
| |
| |
| |
| Semirecursive Relations | |
| |
| |
| |
| Further Examples | |
| |
| |
| |
| Equivalent Definitions of Computability | |
| |
| |
| |
| Coding Turing Computations | |
| |
| |
| |
| Universal Turing Machines | |
| |
| |
| |
| Recursively Enumerable Sets | |
| |
| |
| Basic Metalogic | |
| |
| |
| |
| A Precis of First-Order Logic: Syntax | |
| |
| |
| |
| First-Order Logic | |
| |
| |
| |
| Syntax | |
| |
| |
| |
| A Precis of First-Order Logic: Semantics | |
| |
| |
| |
| Semantics | |
| |
| |
| |
| Metalogical Notions | |
| |
| |
| |
| The Undecidability of First-Order Logic | |
| |
| |
| |
| Logic and Turing Machines | |
| |
| |
| |
| Logic and Primitive Recursive Functions | |
| |
| |
| |
| Models | |
| |
| |
| |
| The Size and Number of Models | |
| |
| |
| |
| Equivalence Relations | |
| |
| |
| |
| The Lowenheim-Skolem and Compactness Theorems | |
| |
| |
| |
| The Existence of Models | |
| |
| |
| |
| Outline of the Proof | |
| |
| |
| |
| The First Stage of the Proof | |
| |
| |
| |
| The Second Stage of the Proof | |
| |
| |
| |
| The Third Stage of the Proof | |
| |
| |
| |
| Nonenumerable Languages | |
| |
| |
| |
| Proofs and Completeness | |
| |
| |
| |
| Sequent Calculus | |
| |
| |
| |
| Soundness and Completeness | |
| |
| |
| |
| Other Proof Procedures and Hilbert's Thesis | |
| |
| |
| |
| Arithmetization | |
| |
| |
| |
| Arithmetization of Syntax | |
| |
| |
| |
| Godel Numbers | |
| |
| |
| |
| More Godel Numbers | |
| |
| |
| |
| Representability of Recursive Functions | |
| |
| |
| |
| Arithmetical Definability | |
| |
| |
| |
| Minimal Arithmetic and Representability | |
| |
| |
| |
| Mathematical Induction | |
| |
| |
| |
| Robinson Arithmetic | |
| |
| |
| |
| Indefinability, Undecidability, Incompleteness | |
| |
| |
| |
| The Diagonal Lemma and the Limitative Theorems | |
| |
| |
| |
| Undecidable Sentences | |
| |
| |
| |
| Undecidable Sentences without the Diagonal Lemma | |
| |
| |
| |
| The Unprovability of Consistency | |
| |
| |
| Further Topics | |
| |
| |
| |
| Normal Forms | |
| |
| |
| |
| Disjunctive and Prenex Normal Forms | |
| |
| |
| |
| Skolem Normal Form | |
| |
| |
| |
| Herbrand's Theorem | |
| |
| |
| |
| Eliminating Function Symbols and Identity | |
| |
| |
| |
| The Craig Interpolation Theorem | |
| |
| |
| |
| Craig's Theorem and Its Proof | |
| |
| |
| |
| Robinson's Joint Consistency Theorem | |
| |
| |
| |
| Beth's Definability Theorem | |
| |
| |
| |
| Monadic and Dyadic Logic | |
| |
| |
| |
| Solvable and Unsolvable Decision Problems | |
| |
| |
| |
| Monadic Logic | |
| |
| |
| |
| Dyadic Logic | |
| |
| |
| |
| Second-Order Logic | |
| |
| |
| |
| Arithmetical Definability | |
| |
| |
| |
| Arithmetical Definability and Truth | |
| |
| |
| |
| Arithmetical Definability and Forcing | |
| |
| |
| |
| Decidability of Arithmetic without Multiplication | |
| |
| |
| |
| Nonstandard Models | |
| |
| |
| |
| Order in Nonstandard Models | |
| |
| |
| |
| Operations in Nonstandard Models | |
| |
| |
| |
| Nonstandard Models of Analysis | |
| |
| |
| |
| Ramsey's Theorem | |
| |
| |
| |
| Ramsey's Theorem: Finitary and Infinitary | |
| |
| |
| |
| Konig's Lemma | |
| |
| |
| |
| Modal Logic and Provability | |
| |
| |
| |
| Modal Logic | |
| |
| |
| |
| The Logic of Provability | |
| |
| |
| |
| The Fixed Point and Normal Form Theorems | |
| |
| |
| Annotated Bibliography | |
| |
| |
| Index | |