This classic introduction to the main areas of mathematical logic provides the basis for a first graduate course in the subject. It embodies the viewpoint that mathematical logic is not a collection of vaguely related results, but a coherent method of attacking some of the most interesting problems, which face the mathematician. The author presents the basic concepts in an unusually clear and accessible fashion, concentrating on what he views as the central topics of mathematical logic: proof theory, model theory, recursion theory, axiomatic number theory, and set theory. There are many exercises, and they provide the outline of what amounts to a second book that goes into all topics in more depth. This book has played a role in the education of many mature and accomplished researchers.
Author(s): Joseph R. Shoenfield
Edition: 1St Edition
Publisher: Addison-Wesley Educational Publishers Inc
Year: 1967
Language: English
Pages: 344
Preface......Page 3
Contents......Page 5
1. Axiom systems......Page 9
2. Formal systems......Page 10
3. Syntactical variables......Page 14
1. Functions an predicates......Page 17
2. Truth functions......Page 18
3. Variables and quantifiers......Page 20
4. First-order languages......Page 22
5. Structures......Page 26
6. Logical axioms and rules......Page 28
Problems......Page 31
1. The tautology theorem......Page 34
2. Results on quantifiers......Page 39
3. The deduction theorem......Page 41
4. The equivalence and equality theorems......Page 42
5. Prenex form......Page 44
Problems......Page 47
1. The reduction theorem......Page 49
2. The completeness theorem......Page 51
3. The consistency theorem......Page 56
4. Herbrand's theorem......Page 60
5. Addition of function symbols......Page 63
6. Extensions by definitions......Page 65
7. Interpretations......Page 69
Problems......Page 73
1. The compactness theorem......Page 77
2. Isomorphisms and substructures......Page 79
3. Cardinality of models......Page 86
4. Joint consistency......Page 87
5. Complete theories......Page 90
6. Categoricity......Page 96
Problems......Page 100
1. Calculability......Page 114
2. Recursive functions......Page 116
3. Explicit definitions......Page 118
4. Sequence numbers......Page 123
5. Church's Thesis......Page 127
6. Expression numbers......Page 130
7. Representability......Page 134
8. Church's Theorem and the Incompleteness Theorem......Page 139
9. Undecidability......Page 141
Problems......Page 145
1. Partial functions......Page 152
2. Functionals and relations......Page 155
3. Properties of recursive functionals......Page 158
4. Indices......Page 164
5. The arithmetical hierarchy......Page 168
6. Relative recursiveness......Page 172
7. Degrees......Page 177
8. The analytical hierarchy......Page 181
9. Hyperarithmetical relations......Page 183
10. The Characterization Theorem......Page 187
11. Basis theorems......Page 193
Problems......Page 198
1. Peano Arithmetic......Page 212
2. The theorem on consistency proofs......Page 217
3. The consistency proof......Page 222
4. Applications of the consistency proof......Page 231
5. Second-order arithmetic......Page 235
Problems......Page 241
1. Axioms for sets......Page 246
2. Development of set theory......Page 248
3. Ordinals......Page 254
4. Cardinals......Page 260
5. Interpretations of set theory......Page 268
6. Constructible sets......Page 278
7. The Axiom of Constructibility......Page 285
8. Forcing......Page 290
9. The independence proofs......Page 301
10. Large cardinals......Page 311
Problems......Page 323
Appendix: The Word Problem......Page 329
Index......Page 345
