Friday 22 January 2021. First lecture. Our infinite games: two-player, length ω, win-lose, perfect information, perfect recall games. Discussion of what this course is not about: games with more than two players, asymptotic or evolutionary behaviour of finite games, pay-off functions, games with hidden information, games with forgetful players.
Lecture Notes.

Monday 25 January 2021. Second lecture. Set-theoretic notions for functions. Moves, positions, runs, payoff sets, interleaving. The game G(A). Strategies, winning strategies, and determinacy. Trees, branches, games with rules G(A;T). Describing variant games in the form G(A) by providing rules.
Lecture Notes.

Wednesday 27 January 2021. Third lecture. Strategic trees, perfect trees, perfect sets. Strategic trees are perfect trees. Cardinality of perfect sets (Cantor schemes). Necessary criteria for player I or II having a winning strategy in G(A) in terms of the cardinalities of A and M^ω\A.
Lecture Notes.

Friday 29 January 2021. Fourth lecture. Sufficient conditions for determinacy: if a set or its complement has size less than continuum, then it is determined. Blindfolded strategies. Construction of a non-determined set from the Axiom of Choice (more precisely: from the existence of a wellordering of the set ω^ω).
Lecture Notes.

Monday 1 February 2021. Fifth lecture. Zermelo's Theorem: example of backwards induction for finite games. Quasi-strategies, quasistrategic trees, quasi-determinacy. Proof that quasi-determinacy implies determinacy if the move set is wellorderable. Closed sets. The Gale-Stewart Theorem. First part of proof: transfinite recursive definition of the labelling.
Lecture Notes.

Wednesday 3 February 2021. Sixth lecture. The Gale-Stewart Theorem. Continuation of the proof: sets of positions with the correct label are quasi-strategies; the age function and proof that the quasi-strategies are winning. Baire space and Cantor space: their metrics, open balls, and basic open sets. Baire and Cantor space as product spaces. Baire space is not compact and not connected.
Lecture Notes.

Friday 5 February 2021. Seventh lecture. Convergence in Baire and Cantor space. The tree representation theorem for closed sets. Continuity of functions in Baire space (cf. also Example Sheet #2). Baire space is zero-dimensional and finite products of Baire space are homeomorphic to Baire space. Baire space is homeomorphic to the irrationals (no proof, brief mention to continued fractions). Invariance of set-theoretic properties under bijections. The Borel hierarchy.
Lecture Notes.

Monday 8 February 2021. Eighth lecture. G_δ spaces; spaces with a countable clopen topology base are G_δ. The height of the Borel hierarchy: sometimes 1, sometimes 2, upper bound ω₁. In ZFC, the height is ω₁ (no proof yet). Pointclasses, dual and ambiguous pointclasses, closure properties of pointclasses. Universal sets: existence of universal sets implies non-selfduality.
Lecture Notes.

Wednesday 10 February 2021. Ninth lecture. Proof of the Borel Hierarchy Theorem. Discussion of the use of the Axiom of Choice in the proof. Determinacy in the Borel hierarchy (without proofs): Wolfe (1955), Davis (1964), Paris (1972), Martin (1975).
Lecture Notes.

Friday 12 February 2021. Tenth lecture. Cardinality of the set of Borel sets in ZFC. Borel sets in the Feferman-Lévy model: all sets are Borel. Lebesgue's error & Suslin's Theorem: the Borel sets are not closed under continuous images. Projection, the pointclass of projections, the projective hierarchy, analytic & co-analytic sets. The projective hierarchy does not collapse.
Lecture Notes.

Monday 15 February 2021. Eleventh lecture. The Continuum Problem: version that implies the wellorderability of the reals vs the choice-free version. Perfect set property and the Theorem of Cantor & Bendixson (proof sketch). Hausdorff's perfect set theorem for Borel sets. The asymmetric game: determinacy implies the perfect set property (first part of the proof).
Lecture Notes.

Wednesday 17 February 2021. Twelfth lecture. Asymmetric game theorem: second part of the proof. Consequences: necessary conditions for determinacy of projective pointclasses. Gödel-Addison Theorem (without proof). There is a model with a Δ¹₂ wellorder and a Π¹₁ set without the perfect set property. Definable wellorders of Baire space. Relationship between definable wellorders of Baire space and definable sets without the perfect set property. Tree representations of analytic and co-analytic sets: illfounded and wellfounded trees, coding of trees as orders on ω, coding of orders on ω as elements of Baire space.
Lecture Notes.

Friday 19 February 2021. Thirteenth lecture. The set WF and its stratification. WF is co-analytic. The levels of WF are Borel, so WF is a union of ℵ₁ many Borel sets. Hardness and completeness for a boldface pointclass. WF is Π¹₁-complete. Consequences: WF is not analytic and every co-analytic set is the union of ℵ₁ many Borel sets.
Lecture Notes.

Monday 22 February 2021. Fourteenth lecture. Weak Continuum Hypothesis for co-analytic sets. The Boundedness Lemma. Sets of unique codes. Sets of unique codes can be obtained by the axiom of choice and never have the perfect set property. Complexity of a set of unique codes under the assumption that there is a projective wellorder. Discussion of the relationship between large cardinals, determinacy, and the existence of definable wellorders (no definitions, no proofs) and the Martin-Steel theorem.
Lecture Notes.

Wednesday 24 February 2021. Fifteenth lecture. Large cardinal properties, large cardinal axioms. Inaccessible cardinals: inaccessible cardinals give a model of ZFC. Canonical model families and wellordered canonical model families.
Lecture Notes.

Friday 26 February 2021. Sixteenth lecture. Preservation of properties between a universe and its inner models: functions, surjectivity, cofinality, being a cardinal, being regular, WF. Models with different versions of the first uncountable cardinal and the extent of their WF hierarchy. Determinacy plus the existence of a wellordered canonical model family implies the existence of an inner model with an inaccessible cardinal. Preview: Martin's Theorem on analytic determinacy and Solovay's Theorem on the measurability of ℵ₁.
Lecture Notes.

Monday 1 March 2021. Seventeenth lecture. Filters, ultrafilters, κ-completeness. Measurable cardinals. Every measurable cardinal is inaccessible. Partition relations and the Erdős-Rado arrow notation. Weakly compact cardinals. Facts about weakly compact cardinals (without proof). Rowbottom's Theorem (without proof).
Lecture Notes.

Wednesday 3 March 2021. Eighteenth lecture. The cardinal ℵ₁ is not weakly compact. Normal ultrafilters; normal ultrafilters are κ-complete. Measurable cardinals have a normal ultrafilter (without proof). Every measurable cardinal is weakly compact (proof using normal ultrafilters). Tree representations and determinacy (via Gale-Stewart). The property of being κ-Suslin. The auxiliary game for κ-Suslin sets. Player I wins G(A) if he wins the auxiliary game. Problem for player II.
Lecture Notes.

Friday 5 March 2021. Nineteenth lecture. The proof of analytic determinacy cannot be a soft proof, but must use a particular Suslin representation. Idea for constructing a tree to witness that a co-analytic set is ℵ₁-Suslin. Shoenfield's Theorem. The Kleene-Brouwer order. Finite sets of codes approximating the tree T_x. Coherent sequences. The Shoenfield tree. Proof that the Shoenfield tree is a representation of the co-analytic set (first half).
Lecture Notes.

Monday 8 March 2021. Twentieth lecture. Proof that the Shoenfield tree is a representation of the co-analytic set (second half). Reminder: measurable cardinals, normal ultrafilters, Rowbottom's theorem. Martin's Theorem: co-analytic determinacy. Proof: construction of the translation of a strategy for player II in the auxiliary game into a strategy for player II in the original game.
Lecture Notes.

Wednesday 10 March 2021. Twenty-first lecture. Proof of Martin's Theorem: the constructed strategy is winning. The Axiom of Determinacy AD and choice. Fragment needed to develop the basic theory of descriptive set theory: countable choice for reals. AD implies countable choice for reals. (Relation to the uniformisation principle from Example Sheet #1.) Existence of ultrafilters without the axiom of choice.
Lecture Notes.

Friday 12 March 2021. Twenty-second lecture. Image filters and their properties. ℵ₁-incomplete ultrafilters and non-principal ultrafilters on the natural numbers. AD implies that all ultrafilters on the natural numbers are principal: strategy stealing argument.
Lecture Notes.

Monday 15 March 2021. Twenty-third lecture. Sets contained in V_ω+1. The relation "x is definable from y" and its properties. Preorders, their induced equivalence relation, and their degree structure. The partial order of definability degrees. Cones. The cone filter. Proof that the cone filter is a filter.
Lecture Notes.

Wednesday 17 March 2021. Twenty-fourth lecture. Coding strategies as elements of Baire space: relationship between the definability degree of a strategy and that of its results. Invariant sets and sets of degrees. Martin's Lemma. The Martin measure on the set of definability degrees. Proof of Solovay's Theorem.
Lecture Notes.

Remote student interaction & presentations. In the new world of online university teaching, many of us miss the informal discussions about mathematics that we used to have at the CMS. Chatting before or after lectures, listening to someone else speaking at the blackboard, chance conversations during lunch or dinner are all missing in our current university experience.

In an attempt to encourage the creation of virtual informal discussions, we ask you to arrange mathematical discussions about the material of Infinite Games in pairs: please arrange virtual meetings with one of the other students taking this course and work on two examples together, preparing a brief online presentation of these examples for the first Examples Class. (If you do not know how to find a partner for these meetings, do not hesitate to contact us by e-mail and we shall arrange some pairs.) A positive side effect is that these meetings allow you to discuss online presentations of mathematics with your fellow students. We expect that online presentations will be a crucial skill for many of us in the future and getting experience with them is very important. Mathematical online presentations would be done either by sharing the screen (e.g., the Zoom whiteboard or some other writing software) and writing on it (e.g., with a pen on a tablet) or by writing on a piece of paper with a camera set up to point to the paper (i.e., a visualiser). Your pair meetings can and should be about both the mathematical content of the two examples and about the practicalities of the presentation. The Examples Class will then start with student presentations of the two Presentation Examples. However, active student presentation of examples is not restricted to these two examples: we greatly encourage if students present their solutions (or partial solutions, solution ideas, failed attempts of solutions etc.) to all examples during the Examples Class.

Marking. You can submit your work as a single pdf file below (at the bottom of this section). Feel free to submit all of your work; two examples will be marked. Please submit your work by Thursday noon before the Examples Class.

First Examples Class: 12 February 2021, 15:30-17:00.
Example Sheet #1: pdf file.

Second Examples Class: 26 February 2021, 15:30-17:00.
Example Sheet #2: pdf file.

Third Examples Class: 12 March 2021, 15:30-17:00.
Example Sheet #3: pdf file.

Fourth Example Class: 30 April 2021, 15:30-17:00.
Example Sheet #4: pdf file.