Notes on Set Theory

14. Schr¨oder-Bernstein Theorem, 16. Problems for Chapter 2, 17.

Chapter 3. Paradoxes and axioms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

The Russell paradox, 21. Axioms (I) – (VI), 24. Axioms for definite conditions

and operations, 26. Classes, 27. Problems for Chapter 3, 30.

Chapter 4. Are sets all there is? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Ordered pairs, 34. Disjoint union, 35. Relations, 36. Equivalence relations, 37.

Functions, 38. Cardinal numbers, 42. Structured sets, 44. Problems for Chapter 4,

45.

Chapter 5. The natural numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Peano systems, 51. Existence of the natural numbers, 52. Uniqueness of the natural

numbers, 52. Recursion Theorem, 53. Addition and multiplication, 58. Pigeonhole

Principle, 62. Strings, 64. String recursion, 66. The continuum, 67. Problems for

Chapter 5, 67.

Chapter 6. Fixed points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Posets, 71. Partial functions, 74. Inductive posets, 75. Continuous Least Fixed

Point Theorem, 76. About topology, 79. Graphs, 82. Problems for Chapter 6, 83.

Streams, 84. Scott topology, 87. Directed-complete posets, 88.

Chapter 7. Well ordered sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Transfinite induction, 94. Transfinite recursion, 95. Iteration Lemma, 96. Comparability

of well ordered sets, 99. Wellfoundedness of ≤o, 100. Hartogs’ Theorem, 100.

Fixed Point Theorem, 102. Least Fixed Point Theorem, 102. Problems for Chapter 7,

104.

xi

xii CONTENTS

Chapter 8. Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Axiom of Choice, 109. Equivalents of AC, 112. Maximal Chain Principle, 114.

Zorn’s Lemma, 114. Countable Principle of Choice, ACN, 114. Axiom (VII) of

Dependent Choices, DC, 114. The axiomatic theory ZDC, 117. Consistency and

independence results, 117. Problems for Chapter 8, 119.

Chapter 9. Choice’s consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Trees, 122. K¨ onig’s Lemma, 123. Fan Theorem, 123. Well foundedness of ≤c ,

124. Best wellorderings, 124. K¨ onig’s Theorem, 128. Cofinality, regular and singular

cardinals, 129. Problems for Chapter 9, 130.

Chapter 10. Baire space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Cardinality of perfect pointsets, 138. Cantor-Bendixson Theorem, 139. Property

P, 140. Analytic pointsets, 141. Perfect Set Theorem, 144. Borel sets, 147. The

Separation Theorem, 149. Suslin’s Theorem, 150. Counterexample to the general

property P, 150. Consistency and independence results, 152. Problems for Chapter

10, 153. Borel isomorphisms, 154.

Chapter 11. Replacement and other axioms . . . . . . . . . . . . . . . . . . . . . . . 157

Replacement Axiom (VIII), 158. The theory ZFDC, 158. Grounded Recursion

Theorem, 159. Transitive classes, 161. Basic Closure Lemma, 162. The grounded,

pure, hereditarily finite sets, 163. Zermelo universes, 164. The least Zermelo universe,

165. Grounded sets, 166. Principle of Foundation, 167. The theory ZFC (Zermelo-

Fraenkel with choice), 167. ZFDC-universes, 169. von Neumann’s class V, 169.

Mostowski Collapsing Lemma, 170. Consistency and independence results, 171.

Problems for Chapter 11, 171.

Chapter 12. Ordinal numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

Ordinal numbers, 176. The least infinite ordinal, 177. Characterization of ordinal

numbers, 179. Ordinal recursion, 182. Ordinal addition and multiplication, 183. von

Neumann cardinals, 184. The operation ℵα, 186. The cumulative rank hierarchy, 187.

Problems for Chapter 12, 190. The operation α, 194. Strongly inaccessible cardinals,

195. Frege cardinals, 196. Quotients of equivalence conditions, 197.

Appendix A. The real numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

Congruences, 199. Fields, 201. Ordered fields, 202. Existence of the rationals,

204. Countable, dense, linear orderings, 208. The archimedean property, 210. Nested

interval property, 213. Dedekind cuts, 216. Existence of the real numbers, 217.

Uniqueness of the real numbers, 220. Problems for Appendix A, 222.

Appendix B. Axioms and universes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

Set universes, 228. Propositions and relativizations, 229. Rieger universes, 232.

Rieger’s Theorem, 233. Antifoundation Principle, AFA, 238. Bisimulations, 239. The

antifounded universe, 242. Aczel’s Theorem, 243. Problems for Appendix B, 245.

Solutions to the exercises in Chapters 1 – 12 . . . . . . . . . . . . . . . . . . . . . . . . 249

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271