Capita Selecta: Set Theory

2020/2021; 1st Semester

Instructors: Dr. Lorenzo Galeotti & Prof. Dr. Benedikt Löwe
ECTS: 6

General. In the tradition of "capita selecta", the course will build on a firm knowledge of basic set theory and discuss some of the major topics of modern set theory, such as the large cardinals, descriptive set theory, inner models, infinite games, or forcing. The choice of topic changes each year and the course can be taken multiple times for credit.

2020 topic. The topic of this year's course Capita Selecta: Set Theory is descriptive set theory and infinite games. We shall be following an unfinished textbook manuscript by Alessandro Andretta entitled Notes on Descriptive Set Theory: a pdf file was made available on the canvas page. For the first two lectures, we shall also use lecture notes by Yurii Khomskii entitled Infinite Games, provided on the canvas page.

Prerequisites. Capita Selecta: Set Theory is an advanced set theory course and assumes familiarity with the basics of axiomatic set theory, i.e., the axioms of ZFC, ordinals and cardinals, transfinite recursion and induction, and the basic theory of the axiom of choice. This material corresponds to the contents of the UvA courses Axiomatische Verzamelingentheorie (B.Sc. Wiskunde) or Rudiments of Axiomatic Set Theory (M.Sc. Logic).

Lecture organisation. All lectures will be given virtually via Zoom:

The Zoom links were published on Canvas. A brief summary of each lecture (including the pages of Andretta's manuscript covered) will be published there as well.

Assessment. The assessment will be based on course work (10%) and an online exam sat on 23 October 2020 from 13:00 to 15:00 (90%). Details about the form of the exam will be given in early October.

Course work. Course work consists of seven weekly multiple choice quizzes due on Monday 6pm arranged via this Canvas page and six weekly homework assignments due on Friday at 1pm. Each correct MC answer gives one point, each incorrect MC answer gives zero points. All homework assignments handed in will give one point (regardless of whether they are correct and regardless of their quality). The course work score will be based on the percentage of the total points available.

2 September 2020: First Lecture. Lecturer: Benedikt Löwe. History of games in set theory: Zermelo's theorem, Blackwell, Mycielski, Solovay, Martin-Steel (without mathematical details). Our types of games: two player, infinite length, win/lose, perfect information, and perfect recall. Brief discussion of other games. Positions, moves, payoff sets. Trees. Games with rules and recapturing rules in ordinary games. Strategies, playing strategies against each other, winning strategies.
Lecture Notes.

4 September 2020: Second Lecture. Lecturer: Benedikt Löwe. Determinacy of a set. Ulam's question: characterisation of the sets won by player I / II. Sufficient conditions for winning (countability). Strategic trees and their size. Necessary conditions for winning (at least as big as a strategic tree). Blindfolded strategies. It's enough to win against all blindfolded strategies. The Axiom of Choice implies the existence of a non-determined set.
Lecture Notes.
Homework Assignment #1.

9 September 2020: Third Lecture. Lecturer: Benedikt Löwe. The Axiom of Determinacy. Implications between Axioms of Determinacy for different move sets (the method of auxiliary games). Theorem of Gale and Stewart (closed determinacy). Fragments of the Axiom of Choice. Development of the theory of cardinals without choice: cardinalities, finiteness and Dedekind-finiteness. Continuum Hypothesis and weak Continuum Hypothesis. Existence of a surjection from \(\wp\left(\kappa\right)\) to \(\kappa^+\). Axiom of Choice for indexed families of sets and relationship between these fragments. (Andretta, Sections 1A and 1B.)
Lecture Notes.

11 September 2020: Fourth Lecture. Lecturer: Lorenzo Galeotti. Short discussion on pathological models of ZF. Definition of \(\mathsf{AC}_\omega\) and \(\mathsf{DC}\). \(\mathsf{AC}\) implies \(\mathsf{DC}\) without proof. Proof that \(\mathsf{DC}\) implies \(\mathsf{AC}_\omega\). If there is a surjection from \(X\) to \(Y\), then \(\mathsf{DC}(X)\) implies \(\mathsf{DC}(Y)\). Proof sketch of Proposition 1.20 (Andretta p. 14). Proof sketch of Lemma 1.22 (Andretta p. 15). Equivalence of \(\mathsf{DC}(X^{<\omega})\) with "every non-empty pruned tree on \(X\) has a branch". (Andretta, Sections 1.B.2-1C).
Lecture Notes.
Homework Assignment #2.

16 September 2020: Fifth Lecture. Lecturer: Lorenzo Galeotti. Product topologies. Basic properties, statement of Exercise 2.2 in Andretta. Complete metrisability of product spaces without proof. Definition of Polish space. If \(X\) is a non-empty countable set then \(X^\omega\) is Polish. Intuition behind continuity of functions between product spaces. Definition of Cantor and Baire space and short discussion about their relationship with \(\mathbb{R}\). Proof of the equivalence of the topological and the tree-theoretical definition of closed set. Definition of perfect trees. Statement of Lemma 2.18 (Andretta p. 40). Definition of Cantor-Bendixson derivative. Proof that fixed points of the Cantor-Bendixson derivative are perfect sets. Proof of "Every closed subset of Cantor space is either countable of of cardinality \(2^{\aleph_0}\). (Andretta, Section 2).
Lecture Notes.

18 September 2020: Sixth Lecture. Lecturer: Lorenzo Galeotti. Introduction to Borel sets and Borel hierarchy. Basic properties of the Borel hierarchy (without proof). If \(\omega_1\) is regular, then the Borel hierarchy has height at most \(\omega_1\). Discussion on the length of the Borel hierarchy without \(\mathsf{AC}\). Definition of pointclass and boldface pointclass. Definition of universal sets. Proof that self-dual classes have no universal set. There is a \(\boldsymbol{\Sigma}^0_1\)-universal set (proof sketch). \(\mathsf{AC}_\omega(\mathbb{R})\) implies that the height of the Borel hierarchy is \(\omega_1\) (proof idea). (Andretta, Section 3).
Lecture Notes.
Homework Assignment #3.

23 September 2020: Seventh Lecture. Lecturer: Benedikt Löwe. Syntax of second order arithmetic: first and second order quantifiers. The arithmetical hierarchy. Purely syntactically defined classes of formulas vs. closure under logical equivalence. Normal form for arithmetical formulas. Addison's Theorem for the arithmetical hierarchy (without proof). History of determinacy in the low levels of the Borel hierarchy: Wolfe, Davis, Friedman, Paris, Martin. Lebesgue's error about the closure of the Borel sets under projections. Preview of the projective hierarchy (Andretta, Section 4).
Lecture Notes.

25 September 2020: Eighth Lecture. Lecturer: Benedikt Löwe. The projective hierarchy. Closure properties of the analytic sets. Universal sets for the projective hierarchy. Brief discussion of the connection between large cardinals and determinacy in the projective hierarchy. Definability in the analytical hierarchy (including quantifier exchange lemma and Addison's Theorem for the analytical hierarchy). Concrete sets: \(\mathrm{LO}\) is Borel, \(\mathrm{WO}\) is co-analytic. Tree representations for analytic and co-analytic sets. Splitting \(\mathrm{WO}\) into its levels: the levels of \(\mathrm{WO}\) are Borel (Andretta, Section 5).
Lecture Notes. Correction of the quantifier exchange rules.
Homework Assignment #4.

30 September 2020: Ninth Lecture. Part 1. Lecturer: Benedikt Löwe. \(\boldsymbol{\Gamma}\)-hardness, \(\boldsymbol{\Gamma}\)-completeness, and their consequences. \(\mathrm{WO}\), \(\mathrm{WO}^*\), and \(\mathrm{WF}\) are \(\boldsymbol{\Pi}^1_1\)-hard. The Boundedness Lemma.
Lecture Notes.
Part 2. Lecturer: Lorenzo Galeotti. Introduction of \(\mathsf{PSP}\) and of determinacy restricted to pointclasses. Structure of the proof that \(\boldsymbol{\Gamma}\)-determinacy implies the \(\mathsf{PSP}(\boldsymbol{\Gamma})\). Proof that \(\mathsf{PSP}\) implies that there is no well-ordering of the reals.
Lecture Notes.

2 October 2020: Tenth Lecture. Part 1. Lecturer: Lorenzo Galeotti. Discussion on the definition of bolfacepointclasses. Definition of the *-game and proof that \(\boldsymbol{\Gamma}\)-determinacy implies \(\mathsf{PSP}(\boldsymbol{\Gamma})\). Consequences: \(\mathsf{AD}\) implies \(\mathsf{PSP}\) and every Borel set has the perfect set property in \(\mathsf{ZFC}\). Brief discussion of the perfect set property of the analytic sets (Homework question 16 on Sheet #5). (Andretta, Section 22) .
Lecture Notes.
Part 2. Lecturer: Benedikt Löwe. Co-analytic sets are unions of \(\aleph_1\) many Borel sets. Co-analytic sets and the Continuum Hypothesis.
Lecture Notes.
Homework Assignment #5.

7 October 2020: Eleventh Lecture. Lecturer: Benedikt Löwe. Determinacy and complements for boldface pointclasses. Brief introduction to large cardinal axioms: worldly cardinals and measurable cardinals. Filters, ultrafilters, completeness. Ramsey's theory and Ramsey's theorem (without proof, but proof for the case of hexagons and triangles). Rowbottom's theorem for measurable cardinals (no proof). Re-formulation of the characterisation of co-analytic sets by trees via the Brouwer-Kleene order. BK-codes. Shoenfield's Theorem (no proof yet).
Lecture Notes.
Typed notes on Analytic Determinacy.

9 October 2020: Twelfth Lecture.  Lecturer: Benedikt Löwe. The Shoenfield Tree. Proof of Shoenfield's Theorem. Martin's Theorem on Analytic Determinacy. Proof of Analytic Determinacy from a measurable cardinal.
Lecture Notes.
Homework Assignment #6.

14 October 2020: Thirteenth Lecture. Lecturer: Lorenzo Galeotti. Under the Axiom of Determinacy there is no non-principal ultrafilter on \(\omega\). Introduction of degrees of definability and of the Martin filter \(\mathrm{M}_\mathrm{A}\). generated by cones. Proof that the Martin filter is an ultrafilter. Martin's proof that Axiom of Determinacy implies that \(\aleph_1\) is measurable. Brief discussion on the situation for cardinals bigger than \(\aleph_1\). (Andretta, Section 19).
Lecture Notes.

16 October 2020: Fourteenth Lecture. Lecturer: Benedikt Löwe. Wadge reducibility. Relationship with boldface pointclasses. The Wadge game and connection to Wadge reducibility. Wadge's Lemma. The Semi-Linear Ordering Principle. Analysis of the first few levels of the Wadge hierarchy. Every set that is open and not closed is complete for the open sets. The Martin-Monk Theorem.
Lecture Notes.

23 October 2020: Exam. The exam is a timed, open book, online exam, held from 13:00 to 15:00. There is a scheduled re-sit on Wednesday 27 January 2021, from 17:00 to 19:00. On 9 October, we made a Canvas announcement with information about the practical arrangements and some practical (non-mathematical) recommendations for preparing for taking the exam. We encourage all students to (re-)read it.

The exam will be downloaded and uploaded via Canvas and will be found at the bottom of the Assignments page. You will not need an internet connection during the exam, but you will need one for downloading and uploading the exam.

Students can find a Template Exam on canvas. The Template Exam gives the structure and an indication of the level of difficulty of the exam. We also provide a file with comments on the Template Exam that explains how Part I (the mandatory part of the exam) will be marked and gives template solutions that would count as good for the two Part I questions in the Template Exam. If you wish to do the template exam to train for the exam, then you might wish to avoid looking at the comments before you finished the training run.