|Lecturer.||Professor Benedikt Löwe, e-mail: b(dot)loewe(at)dpmms(dot)cam(dot)ac(dot)uk|
|Examples Classes.||Luke Gardiner, e-mail: lag44(at)cam(dot)ac(dot)uk|
|L E C T U R E S.|
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.
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.
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.
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 ωω).
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.
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.
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
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 ω1. In ZFC, the height is
ω1 (no proof yet). Pointclasses, dual and ambiguous pointclasses, closure properties of
pointclasses. Universal sets: existence of universal sets implies non-selfduality.
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).
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.
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
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 Δ12
and a Π11 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.
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 ℵ1 many Borel
sets. Hardness and completeness for a boldface pointclass. WF is
Π11-complete. Consequences: WF is not analytic and every co-analytic set
is the union of ℵ1 many Borel sets.
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.
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.
|Week 6.|| |
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 ℵ1.
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).
Wednesday 3 March 2021. Eighteenth lecture. The cardinal
ℵ1 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.
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 ℵ1-Suslin.
Shoenfield's Theorem. The Kleene-Brouwer order. Finite sets of codes approximating the tree
Tx. Coherent sequences. The Shoenfield tree. Proof that the Shoenfield tree is a
representation of the co-analytic set (first half).
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.
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.
Friday 12 March 2021. Twenty-second lecture.
Image filters and their properties.
ℵ1-incomplete ultrafilters and non-principal ultrafilters on the natural numbers.
AD implies that all ultrafilters on the natural numbers are principal: strategy stealing argument.
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.
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.
|Example Sheets & Examples Classes.||
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.
Second Examples Class: 26 February 2021, 15:30-17:00.
Third Examples Class: 12 March 2021, 15:30-17:00.
Fourth Example Class: 30 April 2021, 15:30-17:00.