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