Set theory, logic, and their limitations

Moshe Machover9780521479981, 0521479983, 0521474930, 9780521474931

In this introduction to set theory and logic, the author discusses first order logic, and gives a rigorous axiomatic presentation of Zermelo-Fraenkel set theory. He includes many methodological remarks and explanations, and demonstrates how the basic concepts of mathematics can be reduced to set theory. He explains concepts and results of recursion theory in intuitive terms, and reaches the limitative results of Skolem, Tarski, Church and Gödel (the celebrated incompleteness theorems). For students of mathematics and philosophy, this book provides an excellent introduction to logic and set theory.

---

Table of contents :
§1. Set-theoretic reductionism……Page
Cover……Page 1
Backcover……Page 2
Front Matter……Page 7
Contents……Page 9
Preface……Page 11
§1. Intuitive illustration; preliminaries……Page 15
§2. Weak induction……Page 17
§3. Strong induction……Page 19
§4. The Least Number Principle……Page 20
1. Sets and classes……Page 23
§2. The antinomies; limitation of size……Page 26
§3. Zermelo’s axioms……Page 29
§4. Intersections and differences……Page 35
§1. Ordered n-tuples, cartesian products and relations……Page 37
§2. Functions; the axiom of replacement……Page 41
§3. Equivalence and order relations……Page 44
§4. Operations on functions……Page 47
§1. Equipollence and cardinality……Page 50
§2. Ordering the cardinals; the Schröder-Bernstein Theorem……Page 52
§3. Cardinals for natural numbers……Page 55
§4. Addition……Page 57
§5. Multiplication……Page 60
§6. Exponentiation; Cantor’s Theorem……Page 64
§1. Intuitive discussion and preview……Page 67
§2. Definition and basic properties……Page 68
§3. The finite ordinals……Page 76
§4. Transfinite induction……Page 82
§5. The Representation Theorem……Page 83
§6. Transfinite Recursion……Page 87
§1. From the axiom of choice to the well-ordering theorem……Page 91
§2. From the WOT via Zorn’s Lemma back to AC……Page 95
§1. Finite cardinals……Page 102
§2. Cardinals in general……Page 106
§3. Arithmetic of the alephs……Page 111
§1. Basic syntax……Page 115
§2. Notational conventions……Page 118
§3. Propositional combinations……Page 121
§4. Basic semantics……Page 122
§5. Truth tables……Page 125
§6. The propositional calculus……Page 130
§7. The Deduction Theorem……Page 136
§8. Inconsistency and consistency……Page 138
§9. Weak completeness……Page 143
§10. Hintikka sets……Page 147
§11. The ambient metatheory……Page 148
§12. Maximal consistent sets……Page 150
§13. Strong completeness……Page 153
§1. Basic syntax……Page 156
§2. Adaptation of previous material……Page 159
§3. Mathematical structures……Page 162
§4. Basic semantics……Page 164
§5. Free and bound occurrences of variables……Page 171
§6. Substitution……Page 175
§7. Hintikka sets……Page 181
§8. Prenex formulas; parity……Page 189
§9. The first-order predicate calculus……Page 190
§10. Rules of instantiation and generalization……Page 194
§11. Consistency……Page 197
§12. Maximal consistency……Page 201
§13. Completeness……Page 202
§1. Preliminaries……Page 208
§2. Computers……Page 210
§3. Recursiveness……Page 212
§4. Closure results……Page 218
§5. The MRDP Theorem……Page 221
§1. Preliminaries……Page 224
§2. Theories……Page 229
§3. Skolem’s Theorem……Page 232
§4. Representability……Page 235
§5. Arithmeticity……Page 238
§6. Coding……Page 245
§7. Tarski’s Theorem……Page 249
§8. Axiomatizability……Page 252
§9. Baby arithmetic……Page 257
§10. Junior arithmetic……Page 263
§11. A finitely axiomatized theory……Page 270
§12. Undecidability……Page 273
§13. First-order Peano arithmetic……Page 277
§14. The First Incompleteness Theorem……Page 280
§15. The Second Incompleteness Theorem……Page 286
Appendix: Skolem’s Paradox……Page 289
§2. Hugh’s world……Page 290
§3. The paradox and its resolution……Page 293
Author index……Page 297
General index……Page 298