MasterMath Set Theory 2018

The MasterMath course Set Theory was taught at the Universiteit van Amsterdam during the 1st Semester 2018/19 by K P Hart and Benedikt Löwe, assisted by Robert Paßmann. 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 2019. (See here for the legacy page of the 2017 version of the course.)



Set Theory - 8EC

Aim. To provide the students with a basic knowledge of axiomatic, combinatorial, and descriptive 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.

Description. 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, a major focus will be descriptive set theory, the study of definable subsets of the real line and their relation to concepts from topology and measure theory (cf. Prerequisites below).

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

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.

The advanced part of the course will focus on descriptive set theory, and for this we expect the students to be familiar with the basics of pointset topology of Euclidean and metric spaces, as well as of the Lebesgue measure of the real line.

First lecture.
10 September 2018.

Lecturer. Benedikt Löwe.

Content. Chapter 0: Metamathematical remarks. The hybrid nature of set theory as a mathematical research area and the foundations of mathematics. The language of set theory. Directed graphs as models of the language of set theory. Examples of interpretations of graphs. Subsets in graph models. Chapter 1: Basic axioms of set theory. Extensionality. Frege's comprehension axiom (scheme) and its inconsistency (Russell's paradox). Models of finite set theory: Pairing, Union, Power set, Separation. Non-existence of universal sets. Every model of finite set theory is infinite.

Homework set #1. pdf file (due on 17 September 2018, 2pm).

Second lecture.
17 September 2018.

Lecturer. Benedikt Löwe.

Content. Axioms of Set Theory, Part II. Chapter 1: Basic axioms of set theory (continued). Definitional expansions of languages using constant and function symbols. The Kuratowski ordered pair. The cartesian product. Relations, functions, injectivity, surjectivity. Inductive sets and the construction of the least inductive set. Induction proofs on the least inductive set. The axiom of Infinity. Models of Zermelo set theory. Chapter 2: Reconstruction of mathematics. The natural numbers as the least inductive set with the inclusion order. Inductive proofs of properties of the natural numbers: all natural numbers are transitive; all elements of natural numbers are natural numbers; every natural number consists of the set of all strictly smaller natural numbers; the natural numbers are totally ordered by inclusion. The recursion theorem for functions on the natural numbers. Recursive definitions of addition and multiplication on the natural numbers via the Grassmann equalities. Definitions of the integers and the rational numbers as equivalence classes of pairs of simpler numbers.

Homework set #2. pdf file (due on 24 September 2018, 2pm).

Third lecture.
24 September 2018.

Lecturer. Benedikt Löwe.

Content. Axioms of Set Theory, Part III. Chapter 2: Reconstruction of mathematics (continued). Dedekind completion of a linear order. Definition of the real numbers. Completeness of the real numbers. Addition on the real numbers. Alternative constructions: Cauchy sequences or decimal expansions. Chapter 3: Further axioms of set theory. 2nd version of the Recursion Theorem: functions from the natural numbers into a given set Z. The Replacement Axiom Scheme. ZF0: Zermelo-Fraenkel without Foundation. 3rd version of the Recursion Theorem: functions from the natural numbers without co-domain given a priori. Applications: iterated power sets and transitive closure. The sum of two orders; example: the sum of two copies of the natural numbers. The principle of order induction: the sum of two copies of the natural numbers satisfies the principle of order induction, but not the principle of complete induction. Wellorders. Every wellorder satisfies the principle of order induction. 4th version of the Recursion Theorem: functions from wellorders without domain given a priori (proof on HW set #3).

Homework set #3. pdf file (due on 1 October 2018, 2pm).

Fourth lecture.
1 October 2018.

Lecturer. Benedikt Löwe.

Content. Axioms of Set Theory, Part IV & Ordinals, Part I. Chapter 3: Further axioms of set theory (continued). Recursive constructions of a model of finite set theory and a model of Z in Zermelo-Fraenkel set theory; cf. Homework exercise (15) & (16). Axiom of Regularity / Foundation. Non-existence of loops. Axiom Scheme of Regularity. Proof that in ZF0, the Axiom of Regularity and the Axiom Scheme of Regularity are equivalent. Epsilon-induction. Chapter 4: Wellorders & Ordinals. Wellorders are preserved by order sums and (linear) order products. Examples of long well-orders (and their embedding in the rational numbers). Non-commutativity of sum and product operation for linear orders. Hartogs's Theorem (without proof). Ordinals. Examples: natural numbers, the set of natural numbers; ordinals are closed under successor.

Homework set #4. pdf file (due on 8 October 2018, 2pm).

Fifth lecture.
8 October 2018.

Lecturer. Benedikt Löwe.

Content. Ordinals, Part II. Chapter 4: Wellorders & Ordinals (continued). Properties of ordinals: irreflexivity, elements of ordinals are ordinals, trichotomy law for ordinals. Initial segments. The Rigidity Theorem for Wellorders (without proof); cf. Homework exercise (22). Isomorphic ordinals are equal. Representation theorem for wellorders: every wellorder is isomorphic to an ordinal. Proof of Hartogs's Theorem. Existence of uncountable ordinals.

Homework set #5. pdf file (due on 15 October 2018, 2pm).

Sixth lecture.
15 October 2018.

Lecturer. Benedikt Löwe.

Content. Ordinals, Part III & The Axiom of Choice, Part I. Chapter 4: Wellorders & Ordinals (continued). Induction and recursion on the ordinals. Transfinite induction and transfinite recursion. Addition, multiplication, and exponentiation of ordinals. Some properties of these operations: subtraction. The von Neumann hierarchy. The axiom of regularity implies that every set lies in the von Neumann hierarchy (proof sketch). Chapter 5: The Axiom of Choice. Choice functions. Existence of choice functions for finite sets. The Axiom of Choice. Wellorderability. Zermelo's wellordering theorem. Proof of the wellordering theorem from the Axiom of Choice.

Homework set #6. pdf file (due on 22 October 2018, 2pm).

Seventh lecture.
22 October 2018.

Lecturer. Benedikt Löwe.

Content. The Axiom of Choice, Part II & Cardinals. Chapter 5: The Axiom of Choice (continued). Brief historical overview of the history of the independence of the Axiom of Choice. Fragments and Equivalents of the Axiom of Choice; examples (without proof): "every vector space has a basis" (equivalent), "there is a non-measurable set" (proper fragment). Zermelo's wellordering theorem is an equivalent of the Axiom of Choice. Chapter 6: Cardinals. The relations \(\sim\) and \(\preccurlyeq\). Cardinal numbers. The Axiom of Choice implies that every \(\sim\)-equivalence class contains a cardinal number. Cardinal comparability theorem. Cardinal comparability is an equivalent of the Axiom of Choice. The Cantor-Schr÷der-Bernstein Theorem (without proof, cf. Homework exercises (31) and (32)). The \(\aleph\) sequence: proof that every cardinal number is an aleph. Successor and limit cardinals. Cofinal subsets of limit ordinals. Regular and singular cardinals. Examples of singular limit cardinals: \(\aleph_\omega\). Hessenberg's Theorem (without proof): for infinite sets \(X\), we have \(X\times X\sim X\). Proof (using the Axiom of Choice) that \(\aleph_\alpha\)-unions of sets of size \(\aleph_\alpha\) have size \(\aleph_\alpha\). Successor cardinals are regular. Question about the existence of regular limit cardinals. Cardinal exponentiation and the continuum problem. Brief discussion of the history of the continuum problem.

Ioanna Dimitriou's Choiceless Grapher.

Homework set #7. pdf file (due on 29 October 2018, 2pm).

Eighth lecture.
29 October 2018.

Lecturer. K. P. Hart.

Content. Definition and characterization of the cofinality function. Definition of infinite sums and products of cardinals. Konig's inequality and Hausdorff's formula plus a few elementary properties of the continuum function and exponentiation. Colsed unbounded (cub) and stationary subsets of regular uncountable cardinals: Many intersections of families of cub sets are again cub; the diagonal intersection of kappa many cub subsets of kappa is cub. Fodor's Pressing-Down Lemma.

Homework set #8 pdf file (due on 5 November 2018, 2pm).

Ninth lecture.
5 November 2018.

Lecturer. K. P. Hart.

Content. A proof of Solovay's theorem that ever stationary subset of a regular uncountable cardinal \(\kappa\) can be decomposed into \(\kappa\) many disjoint stationary sets. Some comments/remarks about closed unbounded sets and normal functions. Foreshadowing the role of cub sets in Model Theory: the family of submodels of a given model is often a cub set. A start with Combinatorial Set Theory: Ramsey's Theorem. Two examples that block obvious generalizations are in the homework.

Homework set #9 pdf file (due on 12 November 2018, 2pm).

Tenth lecture.
12 November 2018.

Lecturer. K. P. Hart.

Content. Comments on the finite versions of Ramsey's theorem (here is some information about Ramsey numbers and the Erdos-Szekeres paper). General versions of the counterexamples from the homework: \(2^\kappa\not\to(3)^2_\kappa\) and \(2^\kappa\not\to(\kappa^+)^2_2\), with a treatement of the lexicographic order on \(2^\kappa\). This shows that \(\kappa\to(\kappa)^2_2\) (weak compactness) implies that \(\kappa\) is (at least) inaccessible. The basic version of the Erdos-Rado theorem: \((2^{\aleph_0})^+\to(\aleph_1)^2_{\aleph_0}\). The Erdos-Dushnik-Miller theorem: \(\kappa\to(\kappa,\aleph_0)^2\).

Homework set #10 pdf file (due on 19 November 2018, 2pm).

Eleventh lecture.
19 November 2018.

Lecturer. K. P. Hart.

Content. Descriptive Set Theory.

Closed and perfect sets in the real line. Uncountable closed sets contain perfect sets; perfect sets have cardinality continuum. Thus: "CH holds for closed sets." The Baire Category theorem. Meager or First Category sets, Second Category sets. Generic or Resudial sets. Definition of Borel sets, \(G_\delta\)-sets and \(F_\sigma\)-sets. The Baire space of sequences of natural numbers. Representation of closed sets as sets of branches through trees. Parallels between Cantor-Bendixson for closed sets in \(\mathbb{R}\) and for trees.

Homework set #11 pdf file (due on 24 November 2018, 2pm).

Twelfth lecture.
26 November 2018.

Lecturer. K. P. Hart.

Content. Descriptive Set Theory.

Polish spaces are continuous images of the Baire space \(\mathcal{N}\). Building the Borel \(\sigma\)-algebra from the inside: the hierarchies of \(\Sigma^0_\alpha\)- and \(\Pi^0_\alpha\)-sets. Existence of universal sets and as a consequence: the hierarchies are strictly increasing. Definition and characterizations of analytic sets.

Homework set #12 pdf file (due on 03 December 2018, 2pm).

Thirteenth lecture.
3 December 2018.

Lecturer. K. P. Hart.

Content. Descriptive Set Theory.

Suslin's \(\mathcal{A}\)-operation: analytic sets are exactly the sets obtained by applying this operation to closed sets. Definition of projective sets; example: the set of nowhere differentiable functions is co-analytic (or simpler) in the space of continuous functions on \([0,1]\) (a proof that it is exactly co-analytic is given here). Universal sets for the projective classes. The Lusin separation theorem and Suslin's theorem that the Borel sets are exactly the sets that are analytic and co-analytic. A short discussion of Lebesgue-measure and sets with the Baire property.

Homework set #13 pdf file (due on 10 December 2018, 2pm).

Fourteenth lecture.
10 December 2018.

Lecturer. K. P. Hart.

Content. Descriptive Set Theory.

Analytic sets are Lebesgue-measurable, have the Baire property and the perfect set property. The perfect set property for Borel sets was proven by Alexandroff and Hausdorff, using quite different methods. Tree representations for \(\Sigma^1_1\)- and \(\Pi^1_1\)-sets. A short discussion of recursive functions and sets.

Homework set #14 pdf file (due on 17 December 2018, 2pm).

Fifteenth lecture.
17 December 2018.

Lecturer. K. P. Hart.

Content. Descriptive Set Theory.

Logical analysis of \(\Sigma^1_n\)- and \(\Pi^1_n\)-sets. Well-founded trees and their rank functions. The sets of well-founded relations and well-orders are both `natural' examples of co-analytic sets that are not analytic. Every co-analytic set is the union of \(\aleph_1\) many Borel sets, hence the cardinality of a co-analytic set can be: at most \(\aleph_0\), exactly \(\aleph_1\) or exactly \(2^{\aleph_0}\).