Capita Selecta: Set Theory2020/2021; 1st SemesterInstitute for Logic, Language & ComputationUniversiteit van Amsterdam |
||||||
The original course pages were hosted on Moodle and were only
available to registered students of this course. This is a legacy
website with the information from the moodle page, extracted in October
2020.
Instructors: Dr. Lorenzo Galeotti &
Prof. Dr. Benedikt
Löwe 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. 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. 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.)
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). 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). 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). 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). 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). 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. 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) . 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). 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. 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). 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. 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. |