Cambridge

Infinite Games
Part III of the Mathematical Tripos
Lent Term 2020

Lecturer: Professor Benedikt Löwe, email: bloewe@science.uva.nl
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.
#4: Monday 16 March 2020, 3:30–5, MR14.

Revision Session: TBA

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.]

Last changed: 17 February 2020