| |
| |
| Contents of Part I | |
| |
| |
| Notes from the translator | |
| |
| |
| Notes to the reader | |
| |
| |
| Introduction | |
| |
| |
| |
| Recursion theory | |
| |
| |
| |
| Primitive recursive functions and sets | |
| |
| |
| |
| Some initial definitions | |
| |
| |
| |
| Examples and closure properties | |
| |
| |
| |
| Coding of sequences | |
| |
| |
| |
| Recursive functions | |
| |
| |
| |
| Ackerman's function | |
| |
| |
| |
| The [mu]-operator and the partial recursive functions | |
| |
| |
| |
| Turing machines | |
| |
| |
| |
| Description of Turing machines | |
| |
| |
| |
| T-computable functions | |
| |
| |
| |
| T-computable partial functions are recursive | |
| |
| |
| |
| Universal Turing machines | |
| |
| |
| |
| Recursively enumerable sets | |
| |
| |
| |
| Recursive and recursively enumerable sets | |
| |
| |
| |
| The halting problem | |
| |
| |
| |
| The smn theorem | |
| |
| |
| |
| The fixed point theorems | |
| |
| |
| |
| Exercises for Chapter 5 | |
| |
| |
| |
| Formalization of arithmetic, Godel's theorems | |
| |
| |
| |
| Peano's axioms | |
| |
| |
| |
| The axioms | |
| |
| |
| |
| The ordering on the integers | |
| |
| |
| |
| Representable functions | |
| |
| |
| |
| Arithmetization of syntax | |
| |
| |
| |
| The coding of formulas | |
| |
| |
| |
| The coding of proofs | |
| |
| |
| |
| Incompleteness and undecidability theorems | |
| |
| |
| |
| Undecidability of arithmetic and predicate calculus | |
| |
| |
| |
| Godel's incompleteness theorems | |
| |
| |
| |
| Exercises for Chapter 6 | |
| |
| |
| |
| Set theory | |
| |
| |
| |
| The theories Z and ZF | |
| |
| |
| |
| The axioms | |
| |
| |
| |
| Ordered pairs, relations, and maps | |
| |
| |
| |
| Ordinal numbers and integers | |
| |
| |
| |
| Well-ordered sets | |
| |
| |
| |
| The ordinals | |
| |
| |
| |
| Operations on ordinal numbers | |
| |
| |
| |
| The integers | |
| |
| |
| |
| Inductive proofs and definitions | |
| |
| |
| |
| Induction | |
| |
| |
| |
| The axiom of choice | |
| |
| |
| |
| Cardinality | |
| |
| |
| |
| Cardinal equivalence classes | |
| |
| |
| |
| Operations on cardinal equivalence classes | |
| |
| |
| |
| The finite cardinals | |
| |
| |
| |
| Countable sets | |
| |
| |
| |
| The cardinal numbers | |
| |
| |
| |
| The axiom of foundation and the reflection schemes | |
| |
| |
| |
| The axiom of foundation | |
| |
| |
| |
| Some relative consistency results | |
| |
| |
| |
| Inaccessible cardinals | |
| |
| |
| |
| The reflection scheme | |
| |
| |
| |
| Exercises for Chapter 7 | |
| |
| |
| |
| Some model theory | |
| |
| |
| |
| Elementary substructures and extensions | |
| |
| |
| |
| Elementary substructures | |
| |
| |
| |
| The Tarski-Vaught test | |
| |
| |
| |
| Construction of elementary extensions | |
| |
| |
| |
| Elementary maps | |
| |
| |
| |
| The method of diagrams | |
| |
| |
| |
| The interpolation and definability theorems | |
| |
| |
| |
| Reduced products and ultraproducts | |
| |
| |
| |
| Preservation theorems | |
| |
| |
| |
| Preservation by substructures | |
| |
| |
| |
| Preservation by unions of chains | |
| |
| |
| |
| Preservation by reduced products | |
| |
| |
| |
| [characters not reproducible]-categorical theories | |
| |
| |
| |
| The omitting types theorem | |
| |
| |
| |
| [characters not reproducible]-categorical structures | |
| |
| |
| |
| Exercises for Chapter 8 | |
| |
| |
| Solutions to the exercises of Part II | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| Bibliography | |
| |
| |
| Index | |