MasterMath Set Theory 2019

The MasterMath course Set Theory was taught at the Universiteit van Amsterdam during the 1st Semester 2019/20 by K P Hart and Benedikt Löwe, assisted by Ned Wontner. The course website was hosted on the MasterMath website and was only available to registered students of this course. This is a legacy website with the information from that webpage, extracted in May 2020. (See here and here for the legacy pages of the 2017 and 2018 versions of the course, respectively.)



Set Theory - 8EC

Prerequisites. The course is a combination of an introductory and an advanced course in set theory. As a consequence, no prior knowledge of axiomatic set theory is assumed. We shall, however, assume mathematical maturity, including the naïve use of sets that is very common in mathematics.

Furthermore, in this course, we shall use basic notions and results from Mathematical Logic and Model Theory and we expect students to be familiar with this material. Students who did not take an introductory course on mathematical logic can find the material in, e.g.,

  • Chapters II-VI of Mathematical Logic by Ebbinghaus, Flum, and Thomas,
  • Chapter Two of A mathematical introduction to logic by Enderton,
  • Chapter 2 of Introduction to Mathematical Logic by Mendelson,
  • Chapters 3 and 4 of Logic & Structure by van Dalen,
  • or in any other introductory textbook on mathematical logic.

Aim of the course. The aim is to provide the students with a basic knowledge of axiomatic and combinatorial set theory, to prepare the students for research in set theory and for using set theory as a tool in mathematical areas such as general topology, algebra and functional analysis.

The course will start with a brief introduction to axiomatic set theory, the model theory of set theory (including simple independence results), and the basic theory of ordinals and cardinals. The second part of the course will be devoted to more advanced topics in set theory.

This year, the focus of the advanced topics will be the use of permutation models in independence proofs in Set Theory, in particular in proofs of the unprovability of the Axiom of Choice and its consequences.

The three-hour period will generally be divided into 120 minutes of lectures and a short exercise class.

Rules about Homework/Exam. Written exam and homework assignments; the final grade will be the weighted average of the exam (weight 90 %) and homework grade (weight 10%), rounded to full numbers.

Grading policy for re-sits. Final grades will be computed separately for the first exam (.1 x homework + .9 x exam) and the re-sit (.1 x homework + .9 x re-sit) and then submitted separately to the local administrations. The local administrations then apply the re-sit grading rules relevant for the individual student: in some programmes, this will be the maximum of the two grades, in others it will be the later of the two grades, even if that is lower than the earlier one. Students are advised to check their own rules before deciding whether to take the re-sit exam or not.

Literature. We shall be using different standard textbooks in set theory for the various parts of the course, e.g.,

First lecture.
9 September 2019.

Lecturer. Benedikt Löwe.

Room. G2.03.

Content. Metamathematical remarks. The dual nature of set theory: mathematical research area and foundations of mathematics. Historical overview: Cantor, Hilbert, Zermelo. The two protagonists of set theory: ordinals and cardinals. Paradoxes of the infinite and their resolution by Cantor. Cantor's theorem of the uncountability of the set of infinite binary sequences. Axioms of Set Theory, Part I. The language of set theory. Structures of the language of set theory (directed graphs). The notion of a subset in directed graphs. Extensionality. The axioms of empty set, singleton, pairing, binary union, union, and power set. Models of extensionality, empty set, and singleton must be infinite. The axiom scheme of comprehension. Russell's theorem: no directed graph satisfies comprehension. The axiom scheme of Separation. No graph satisfying Separation has a universal vertex. The axioms of FST.

Homework: Homework sheet #1 (due 16 September 2019).

Second lecture.
16 September 2019.

Lecturer. Benedikt Löwe.

Room. G2.10.

Content. Axioms of Set Theory, Part II. Locally finite graphs. Construction of a locally finite graph model of FST. Ordered pairs: the Kuratowski pair. Existence of the cartesian product. Relations, functions, injections, bijections, and the notion of equinumerosity. Equivalence relations and equivalence classes. Dedekind-infinity. Inductive sets. The axiom of Infinity. Zermelo set theory Z. Construction of the natural numbers. Induction principle for the natural numbers. Examples of properties to be proved by induction: natural numbers do not contain themselves as elements, natural numbers are transitive sets, total ordering of the natural numbers (without proof).

Homework: Homework sheet #2 (due 23 September 2019).

Third lecture.
23 September 2019.

Lecturer. Benedikt Löwe.

Room. D1.111.

Content. Axioms of Set Theory, Part III. Different forms of induction on the natural numbers: complete induction, order induction, the least number principle. The Recursion Theorem. Recursive definition of addition and multiplication of natural numbers and their properties. Transfinite continuation of the natural numbers: the successor of the set of natural numbers satisfies the least number principle. The axiom scheme of Replacement and Zermelo-Fraenkel set theory without Foundation ZF0. Wellfoundedness, wellorders. The order sum; order sums of wellorders are wellorders.

Homework: Homework sheet #3 (due 30 September 2019).

Fourth lecture.
30 September 2019.

Lecturer. Benedikt Löwe.

Room. F1.02.

Content. Ordinals, Part I. Wellorders, embeddings, isomorphisms. Examples of linear orders that are isomorphic to their proper initial segments. Cantor's back-and-forth method for proving that all countable dense linear orders without endpoints are isomorphic. Initial segments. Characterisation of proper initial segments in wellorders. No wellorder is isomorphic to one of its proper initial segments. Fundamental Theorem on wellorders. The epsilon image of a wellorder. Representation Theorem for wellorders and uniqueness of the epsilon image. Ordinals and some basic closure properties: successor of an ordinal is an ordinal, union of a set of ordinals is an ordinal.

Homework: Homework sheet #4 (due 7 October 2019).

Fifth lecture.
7 October 2019.

Lecturer. Benedikt Löwe.

Room. F1.02.

Content. Ordinals, Part II. Successor ordinals and limit ordinals. Transfinite induction and transfinite recursion. Existence of uncountable ordinals. Hartogs's Theorem. Initial ordinals and the recursive definition of the aleph operation: alephs. Ordinal arithmetic: recursive definitions of addition and multiplication. Example of non-commutativity of addition. Synthetic definition of addition. Proof of the equivalence of the recursive and the synthetic definitions of addition.

Homework: Homework sheet #5 (due 14 October 2019).

Sixth lecture.
14 October 2019.

Lecturer. Benedikt Löwe.

Room. F1.02.

Content. Ordinals, Part III. Ordinal subtraction and division with remainder. Axioms of Set Theory, Part IV. Self-loops in models of set theory. The axiom of foundation. Foundation implies that there are no self-loops. The axiom scheme of foundation. ZF. The transitive closure of a set. The axiom of foundation implies the axiom scheme of foundation. Epsilon-induction. The cumulative hierarchy or von Neumann hierarchy. Foundation implies that every set lies in the cumulative hierarchy. Choice functions and the axiom of choice.

Homework: Homework sheet #6 (due 21 October 2019).

Seventh lecture.
21 October 2019.

Lecturer. Benedikt Löwe.

Room. C1.112.

Content. Axioms of Set Theory, Part V. ZFC. Wellorderability. Equivalence between "\(X\) is wellorderable" and "\(X\) can be injected into an ordinal". Zermelo's Well-Ordering Theorem (ZWOT). ZWOT implies AC. Dedekind-infinity and infinity. Even and odd ordinals. Infinite ordinals are Dedekind-infinite. Proof of the equivalence of infinity and Dedekind-infinity in ZFC. Examples of statements in mathematics that cannot be proved in ZF, but can be proved in ZFC. Cardinals. Cardinality of a set in ZFC. Cantor-Schröder-Bernstein Theorem (without proof). Union preserves size. Product preserves size: Hessenberg Theorem (without proof). Successor and limit cardinals. Regular and singular cardinals. Successor cardinals are regular. Some limit cardinals are singular. The question whether regular limit cardinals exist: weakly inaccessible cardinals.

Homework: Homework sheet #7 (due 28 October 2019).

Eighth lecture.
28 October 2019.

Lecturer. K. P. Hart.

Content. Cardinal arithmetic, Part I. Cofinality of linearly ordered sets, in particular of limit ordinals. Definitions of sums, products and powers of cardinals. A first investigation of what can and cannot be said about the values \(2^\kappa\) and \(\kappa^\lambda\).

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #8 (due 4 November 2019).

Ninth lecture.
4 November 2019.

Lecturer. K. P. Hart.

Content. Cardinal arithmetic, Part II. Kőnig's Theorem and its consequences. The provable properties of the continuum function and of exponentiation. The effect of the Gimel function. A teaser trailer for next time. Here is the Wikipedia page for the Happy Ending Problem, with plenty of references.

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #9 (due 11 November 2019).

Tenth lecture.
11 November 2019.

Lecturer: K. P. Hart.

Content. Combinatorics. Three partition theorems: Ramsey's theorem; the Erdős-Rado theorem and the Erdős-Dushnik-Miller theorem plus counterexamples to possible generalizations of Ramsey's theorem.

Here is a link to a page about Ramsey numbers, for pairs only

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #10 (due 18 November 2019).

Eleventh lecture.
18 November 2019.

Lecturer. K. P. Hart.

Content. Permutation models, Part I. We follow Chapter 4 of Jech's Axiom of Choice. We discussed set theory with atoms, permutations of atoms and the their action on the universe, (hereditarily symmetric objects and permutation models. We looked at a very simple permutation model, the basic Fraenkel model and showed that the set of atoms is not well-orderable in that model.

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #11 (due 25 November 2019).

The permutation lectures are being recorded and can be watched here; the secret word is rjhc

Twelfth lecture.
25 November 2019.

Lecturer: K. P. Hart.

Content. Permutation models, Part II. Normal ideals and supports; symmetric classes. The Second Fraenkel Model: a sequence of pairs without choice function. The Ordered Mostowski Model in which every set has a linear order but \(\mathsf{AC}\) fails, to be finished next time.

Here is Russell's paper, which contains his "Paradox" (p. 32) and the example of the pairs of boots (p. 47).

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #12 (due 2 December 2019).

Thirteenth lecture.
2 December 2019.

Lecturer: K. P. Hart.

Content. Permutation models, Part III. Finished the explanation of the ordered Mostowski model. Showed how to prove the consistency of \(\mathsf{ZFA}\), given that of \(\mathsf{ZFC}\). Indicated an alternative approach where atoms are replaced by sets that satisfy \(x=\{x\}\).

Here are blogposts on the Cantor's first letter and Cantor's second letter to Dedekind on the uncountability of the reals.

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #13 (due 9 December 2019).

Fourteenth lecture.
9 December 2019.

Lecturer: K. P. Hart.

Content. Permutation models, Part IV. A sketch of the Jech-Sochor Embedding Theorem, which allows one to translate results obtained from permutation models to models of ZF. A description of the model that results when this is applied to the Ordered Mostowski model and a the initial stages of a proof that in the resulting model there is no cardinality function as possibly meant by Cantor on the first page of this article (a translation can be found here)

My preparation; the lecture does not always strictly follow this.

Homework: Homework sheet #14 (due 16 December 2019).

Fifteenth lecture.
16 December 2019.

Lecturer: K. P. Hart.

Content. Permutation models, Part V. Finishing the proof of the non-existence of a Cantorian cardinality function.

My preparation; the lecture does not always strictly follow this.