Infinite Games
Part III of the Mathematical Tripos
Lent Term 2020

Lecturer: Professor Benedikt Löwe, email:
Schedule: Lectures: Monday, Wednesday, Friday, 11–12, MR13.

Example Classes:
#1: Monday 3 February 2020, 3:30–5, MR14. Example Sheet #1.
#2: Monday 17 February 2020, 5–6:30, MR14. Example Sheet #2.
#3: Monday 2 March 2020, 3:30–5, MR14. Example Sheet #3
#4: Friday 1 May 2020, 1:30–3, Zoom. Example Sheet #4
Revision Session: Friday 22 May 2020, 1:30–3, Zoom.

Friday, 17 January 2020 First Lecture. Infinite length, two player, zero-sum, perfect information and perfect recall games. Discussion of the types of games that will not be covered in the lecture course: more than two players, cooperative games, imperfect information. A brief historical overview: Zermelo (1913), the Polish school and the Scottish book (Banach, Mazur, Ulam), Gale & Stewart (1953), Blackwell and the Californian stochasticians, Mycielski's Axiom of Determinateness, Solovay. Games, positions, plays, strategies, the result of two strategies playing against each other. The notion of a winning strategy.
Monday, 20 January 2020 Second Lecture. Guest Lecture Imre Leader (non-examinable). Positional games. Examples. Proof of determinacy of positional games with finite winning lines. Strategy-stealing. Examples of player I not winning in bounded time. Open problem: could 5-in-a-row be a win but not in bounded time? Open problems concerning Ramsey games.
Wednesday, 22 January 2020 Third Lecture. Notation and concepts: sequences, trees, branches of a tree, concatenation, the I-part of a sequence and the II-part of a sequence. Strategic trees and re-formulation of being a winning strategy in terms of strategic trees. Necessary criterion for being a win for player I or player II in terms of the cardinality of the set.
Friday, 24 January 2020 Fourth Lecture. Sufficient criterion for being a win for player I or player II: countability. Finite games. Zermelo's Theorem. Backwards induction and construction of labellings. Finitary games. The Gale-Stewart Theorem: finitary games are determined. First half of the proof: transfinite recursive definition of the partial labelling.
Monday, 27 January 2020 Fifth Lecture. Wellfounded trees and their height function. Continuation of the Gale-Stewart proof: proof that the transfinite recursion terminates; proof that the labelling gives winning strategies. The axiom of choice implies the existence of non-determined sets.
Wednesday, 29 January 2020 Sixth Lecture. Baire space and its topology: zero-dimensional, totally disconnected, metric. The Gale-Stewart theorem in its topological formulation: all open sets are determined. Intuitive understanding of convergence. Tree representation of closed sets. Cardinality of the set of open and closed sets. The Borel \(\sigma\)-algebra. The Borel hierarchy.
Friday, 31 January 2020 Seventh Lecture. The Borel hierarchy is a semi-linearly ordered wellfounded hierarchy. On countable topological spaces, it has height at most two; in general, it has height at most \(\aleph_1\). A \(\boldsymbol{\Sigma}^0_2\) set and its determinacy: in general, \(\boldsymbol{\Sigma}^0_2\) sets do not admit constructive labellings (cf. Löwe & Semmes 2007). A brief overview of determinacy in the Borel hierarchy (without proofs): \(\boldsymbol{\Sigma}^0_2\) determinacy (Wolfe 1955), \(\boldsymbol{\Sigma}^0_3\) determinacy (Davis 1963), \(\boldsymbol{\Sigma}^0_4\) determinacy (Paris 1972), Borel determinacy (Martin 1975). Universal sets.

Further literature: B. Löwe, B. Semmes, The extent of constructive labellings, J. Log. Comput. 17(2), 2007, 285–298.
Monday, 3 February 2020 Eighth Lecture. Pointclasses: boldface, coherent, closure properties. Excursion on the use of the Axiom of Choice: closure of \(\boldsymbol{\Sigma}^0_2\) under countable unions uses countable choice; in the Feferman-Lévy model, every set is \(\boldsymbol{\Sigma}^0_4\). Universal sets. The Universal Set Lemma. The Universal Set Theorem: first half of the proof (construction of a universal open set).

Further literature: A. W. Miller, On the length of Borel hierarchies, Ann. Math. Log. 16, 1979, 233–267. A. W. Miller, Long Borel hierarchies, Math. Log. Q. 54(3), 2008, 307–322.

Example Class #1. Example Sheet #1.
Wednesday, 5 February 2020 Ninth Lecture. Proof of the Universal Set Theorem (including coding infinite sequences of elements of Baire space in an element of Baire space). Lebesgue's error: the claim that the Borel sets are closed under continuous images. Suslin's counterexample (without proof). Intuitive definition of the projective hierarchy. In the early 1970s, it was known that determinacy in the projective hierarchy needed to rely on strong axioms of infinity (cannot be proved in \(\mathsf{ZFC}\) alone).
Friday, 7 February 2020 Tenth Lecture. Finite products of Baire space. Characterisation of continuity in terms of coherent functions (no proof). Discussion of game representations of continuity. Analytic sets and equivalent characterisations. Closure properties of analytic sets: countable unions and intersections, continuous images. The projective hierarchy. Discussion of first-order definability and the projective hierarchy. Suslin's Theorem: the projective hierarchy does not collapse (start of proof).
Monday, 10 February 2020 Eleventh Lecture. Proof of Suslin's theorem finished. Regularity properties: Lebesgue measurability on Baire space; the Baire property (Baire Category Theorem mentioned); the perfect set property (PSP). Cantor-Bendixson Theorem (proof idea), perfect sets and perfect trees, cardinality of non-empty perfect sets. Cantor-Bendixson as a definable version of the Continuum Hypothesis. PSP and the Continuum Hypothesis. Sketch of the proof that the Axiom of Choice implies that there is a set without the perfect set property.
Wednesday, 12 February 2020 Twelfth Lecture. Definability of the Axiom of Choice: wellorderings of the Baire space as subsets of the \(\omega^\omega\times\omega^\omega\); projective well-orderings and their consequence for regularity of projective sets. Coding of countable ordinals as elements of Baire space: \(\mathrm{WO}_\alpha\) and \(\mathrm{WO}\). Choice functions for \(\{\mathrm{WO}_\alpha\,;\,\alpha<\aleph_1\}\) and the regularity of \(\aleph_1\). Choice functions for families of closed sets: the left-most branch in a tree. The set \(\mathrm{WO}\) is \(\boldsymbol{\Pi}^1_1\).
Friday, 14 February 2020 Thirteenth Lecture. Tree representation of \(\boldsymbol{\Pi}^1_1\) sets. Every \(\boldsymbol{\Pi}^1_1\) set is a union of \(\aleph_1\) many Borel sets. Boundedness theorem for \(\mathrm{WF}\). Construction of a subset of \(\mathrm{WF}\) that does not have the perfect set property. If there is a project wellordering of the reals, then there is a projective set without the perfect set property. Goal: if every projective set is determined, then every projective set has the perfect set property. Perfect game: coding the perfect game \(\mathrm{G}^*(A)\) as a game \(\mathrm{G}(A^*)\); if \(\boldsymbol{\Gamma}\) is a boldface pointclass, then \(\boldsymbol{\Gamma}\)-determinacy implies \(\boldsymbol{\Gamma}\)-perfect set property. Game characterisation of the perfect set property (no proof yet).
Monday, 17 February 2020 Fourteenth Lecture. Proof of the game characterisation of the perfect set property. Relationship between projective regularity properties and large cardinals. Regular and singular cardinals. Weakly and strongly inaccessible cardinals. Basic model theory of set theory: transitive submodels and absoluteness of some properties (without any proofs).

Further literature: Kenneth Kunen, Set Theory, An Introduction to Independence Proofs. (Elsevier, 1980). Studies in Logic and the Foundations of Mathematics Vol. 102. Section IV.3.

Example Class #2. Example Sheet #2. [In Example (18), assume that \(X\) is a Hausdorff space. In Example (27), the pointclass \(\boldsymbol{\Gamma}\) should contain all closed sets instead of all open sets.]
Wednesday, 19 February 2020 Fifteenth Lecture. Examples of statements upwards absolute, downwards absolute, and absolute between transitive models of \(\mathsf{ZFC}\): ordinal, cardinal, regular, strong limit. The von Neumann hierarchy: if \(\lambda\) is a limit ordinal, then \(\mathbf{V}_\lambda\) is a model of Zermelo set theory with choice (no proof). Absoluteness of properties between \(\mathbf{V}_\lambda\) and the universe. If \(\kappa\) is strongly inaccessible, then \(\mathbf{V}_\kappa\) is a model of \(\mathsf{ZFC}\) (no proof yet). Corollary: the existence of a strongly inaccessible cardinal cannot be proved in \(\mathsf{ZFC}\).
Friday, 21 February 2020 Sixteenth Lecture. Proof that for strongly inaccessible \(\kappa\), \(\mathbf{V}_\kappa\models\mathsf{ZFC}\). Real model families: satisfying \(\mathsf{CH}\), projectively wellordered. \(\aleph_1\) is inaccessible by reals for a real model family. If \(\aleph_1\) is inaccessible by reals for a real model family, then the base model of that family has an inaccessible cardinal.
Monday, 24 February 2020 Seventeenth Lecture. Sets of unique codes and their sizes: if a set of unique codes has the perfect set property, then it must be countable. If the projective PSP holds, then for every projectively wellordered real model family, \(\aleph_1\) is inaccessible by reals. Black box: Gödel (1938) showed that there is a projectively wellordered real model family satisfying \(\mathsf{CH}\). The projective PSP and projective determinacy cannot be provable in \(\mathsf{ZFC}\). Filters, ultrafilters, and \(\kappa\)-completeness.
Wednesday, 26 February 2020 Eighteenth Lecture. If there is a \(\kappa\)-complete non-principal ultrafilter on \(\kappa\), then \(\kappa\) is strongly inaccessible. Normal ultrafilters, measurable cardinals. Remark that \(\mathsf{AC}\) implies that a \(\kappa\)-complete non-principal ultrafilter on \(\kappa\) can be normalised (without proof). Auxiliary games for sets that are projections of sets of branches through trees: if player I wins the auxiliary game, then player I wins the original game.
Friday, 28 February 2020 Nineteenth Lecture. Suslin sets (cf. also Examples 40 and 41 on Example Sheet #3). Shoenfield's Theorem: every \(\boldsymbol{\Pi}^1_1\) set is \(\aleph_1\)-Suslin. Martin's Theorem: if there is a measurable cardinal, then every \(\boldsymbol{\Pi}^1_1\) set is determined (first half of the proof: linearising the orders occurring in the Shoenfield tree via the Kleene-Brouwer order).
Monday, 2 March 2020 Twentieth Lecture. Conclusion of the proof of Martin's theorem. The Axiom of Determinacy. Use of the Axiom of Choice in the development of descriptive set theory: \(\mathsf{AC}_\omega(\mathbb{R})\). Proof that \(\mathsf{AD}\) implies \(\mathsf{AC}_\omega(\mathbb{R})\).

Example Class #3. Example Sheet #3. [In Examples 33 & 38, typos on the paper sheet were corrected in the online sheet: in 33, it's player I who cannot have a winning strategy; in 38, the regressive function in (ii) lives on \(S\).]
Comments on Example 34.
Wednesday, 4 March 2020 Twenty-first Lecture. Brief discussion of mathematics in the absence of \(\mathsf{AC}_\omega(\mathbb{R})\). In general, \(\mathsf{AD}_X\) implies \(\mathsf{AC}_X(X^\omega)\). Inconsistency of \(\mathsf{AD}_{\aleph_1}\). Statement of Solovay's Theorem: \(\mathsf{AD}\) implies that there is a non-principal \(\aleph_1\)-complete ultrafilter on \(\aleph_1\). If there is an ultrafilter that is not \(\aleph_1\)-complete, then there is a non-principal ultrafilter on \(\mathbb{N}\). \(\mathsf{AD}\) implies that there is no non-principal ultrafilter on \(\mathbb{N}\) (not proved yet).
Friday, 6 March 2020 Twenty-second Lecture. Proof that \(\mathsf{AD}\) implies that there is no non-principal ultrafilter on \(\mathbb{N}\) (strategy stealing). Discussion about the number of ultrafilters on \(\kappa\) under \(\mathsf{ZFC}\) and under \(\mathsf{ZF}+\mathsf{AD}\). The structure \(\mathcal{R} := (\mathbf{V}_{\omega+1},\in)\) and what is in it. \(\mathcal{R}\)-absolute formulae. The partial preorder of \(\mathcal{R}\)-absolute definability \(\leq_\mathrm{D}\) and its properties.
Monday, 9 March 2020 Twenty-third Lecture. Cones and the Martin measure on \(\omega^\omega\). The quotient structure \(\mathcal{D}_\mathrm{D}\) and Martin's Lemma: \(\mathsf{AD}\) implies that the Martin measure is an ultrafilter on \(\mathcal{D}_\mathrm{D}\). Gödel's real model family \(\vec{\mathbf{L}}\): if \(x\equiv_\mathrm{D} y\), then \(\mathbf{L}(x) = \mathbf{L}(y)\). Remarks about cardinals in \(\mathbf{L}(x)\). Construction of an \(\aleph_1\)-complete non-principal ultrafilter on \(\aleph_1\) from the Martin measure under \(\mathsf{AD}\).
Wednesday, 11 March 2020 Twenty-fourth Lecture. Lecture cancelled due to illness: Lecture Notes.
Friday, 1 May 2020 Example Class #4. Example Sheet #4
Friday, 22 May 2020 Revision Session.

Last changed: 30 April 2020