Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 158 (Infinite Games)

For a payoff set $A\subseteq M^{\omega }$, a quasistrategy for a player assigns a nonempty subset of $M$ to every finite position at which that player moves. A play is consistent with it when each of that player's moves belongs to the assigned set. The set $A$, or equivalently the infinite game of perfect information $G(A)$, is quasidetermined when one player has a quasistrategy under which every consistent play is won by that player.

The restricted axiom of choice ${\mathsf{AC}}_X(Y)$ says that for every $X$-indexed family $(A_x{)}_{x\in X}$ of nonempty subsets of $Y$, there is a choice function $c:X\to Y$ such that $c(x)\in A_x$ for every $x\in X$.

TakeThus ${\Phi }_M$ is equivalent in ZF to ${\mathsf{AC}}_{M^{<\omega }}(M)$. Indeed, this choice principle chooses one move from every nonempty value of a winning quasistrategy, turning it into a winning strategy in an infinite game. The converse encodes an arbitrary $M^{<\omega }$-indexed family of nonempty subsets of $M$ into a quasidetermined game. This is the choice characterization of quasideterminacy.

Consider the following game on the real numbers. On their first moves, Player I plays $y\in \mathbb{R}$ and Player II replies with $x\in \mathbb{R}$; later moves are ignored. Declare Player II the winner whenPlayer I cannot have a winning strategy in an infinite game: its first move is some fixed $y$, and if $y\notin pA$ then II wins automatically, while if $y\in pA$ then II can reply with an $x$ satisfying $(x,y)\in A$.

The axiom of determinacy for games on $\mathbb{R}$ therefore gives Player II a winning strategy $\tau$. For every $y\in pA$, define $f(y)$ to be II's first response to the move $y$. The winning condition forcesso $f:pA\to \mathbb{R}$ is the required uniformization of a binary relation. This is the direct game proof of uniformization from determinacy.

Let $T\subseteq (X\times \omega {)}^{<\omega }$ be a Suslin representation of $A$, and let $f:X\to Y$ be injective. Apply $f$ coordinatewise to the first coordinate of every node and putThe injectivity of $f$ ensures that a sequence is a branch of $T_f$ exactly when its first coordinate decodes to a branch of $T$. Hence $p[T_f]=p[T]=A$, proving that every X-Suslin set is $Y$-Suslin whenever $X$ injects into $Y$.

Use one label for each member of $A$. More explicitly, setAn infinite branch through this tree has a constant first coordinate $a\in A$ and second coordinate $a$, so $p[T_A]=A$. Thus $A$ is $A$-Suslin. Since $A\subseteq {\omega }^{\omega }$ injects into a set of cardinality $2^{{\aleph }_0}$, part i makes $A$ a $2^{{\aleph }_0}$-Suslin set. This proves that Every set of reals is continuum-Suslin.

Let $A=p[T]$ for a tree $T\subseteq ({\kappa }^{+}\times \omega {)}^{<\omega }$. For each $\alpha <{\kappa }^{+}$, restrict the first-coordinate labels to $\alpha$ and writeEvery countable subset of the successor cardinal ${\kappa }^{+}$ is bounded in ${\kappa }^{+}$, so the first coordinates of any branch through $T$ all lie below some $\alpha <{\kappa }^{+}$. ConsequentlyEvery $\alpha <{\kappa }^{+}$ has cardinality at most $\kappa$, hence injects into $\kappa$. Part i shows that each $A_{\alpha }$ is $\kappa$-Suslin. This is the Successor-Suslin decomposition.

By part ii every subset of the Baire space of sequences is $2^{{\aleph }_0}$-Suslin. If $2^{{\aleph }_0}\le {\aleph }_2$, part i would make every such set ${\aleph }_2$-Suslin. Therefore

Now suppose $2^{{\aleph }_0}>{\aleph }_2$. The axiom of choice gives a set $B\subseteq {\omega }^{\omega }$ of cardinality exactly ${\aleph }_2$. If $B$ were ${\aleph }_1$-Suslin, the Aleph-one-Suslin decomposition into analytic sets would write it as a union of ${\aleph }_1$ analytic sets. If all those analytic sets were countable, their union would have cardinality at most ${\aleph }_1$, so one of them is uncountable. The perfect set property for analytic sets then makes that member, and hence $B$, have cardinality $2^{{\aleph }_0}$, contradictingThus $B$ is not ${\aleph }_1$-Suslin, and

An inner model $M$ is projectively well-ordered when some projective relation well-orders the real numbers of $M$. The ordinal ${\aleph }_1^M={\omega }_1^M$ is the least ordinal that $M$ regards as uncountable; equivalently, it is the supremum of the order types of the well-order codes in $M$.

Assume for contradiction that ${\omega }_1^M$ is uncountable in the ambient universe. Use the projective well-order of the reals of $M$ to choose, for each $\alpha <{\omega }_1^M$, the least $M$-real coding a well-order of type $\alpha$. Standard closure properties of the projective hierarchy make the resulting set $U\subseteq \mathrm{WF}$ projective. It is uncountable because it contains one distinct code for every $\alpha <{\omega }_1^M$.

The set $U$ has no perfect subset. Indeed, a perfect subset $P\subseteq U$ is closed and therefore analytic. The boundedness theorem for well-order codes bounds the ranks of its members below one countable ordinal $\beta$. Since $U$ contains at most one code of each rank, $P$ would then be countable, whereas every nonempty perfect set of reals is uncountable.

If every projective set is determined, projective determinacy holds and gives the perfect set property to every projective set. Applying it to the uncountable projective set $U$ yields a perfect subset, a contradiction. ThereforeThis is projective determinacy collapses the inner-model omega-one.

Suppose ZFC proved that every ${\aleph }_1$-Suslin set is determined. The assumed consistency of ZFC and the relative consistency of the Continuum hypothesis would then give a model ofIn that model $2^{{\aleph }_0}={\aleph }_1$. By Every set of reals is continuum-Suslin, every subset of ${\omega }^{\omega }$ is therefore ${\aleph }_1$-Suslin and hence determined. This is the axiom of determinacy.

But the axiom of choice produces an undetermined set of reals, so ZFC and the axiom of determinacy are incompatible. The displayed theory cannot have a model, contradicting the relative consistency of ZFC plus the continuum hypothesis. Hence ZFC cannot prove that all ${\aleph }_1$-Suslin sets are determined.

Player I cannot have a winning strategy. This is the Solovay rank-comparison game: any proposed strategy for I can be challenged by a well-order code $y$ whose rank lies beyond the bound obtainable from that strategy, so that either I produces $x\notin \mathrm{WF}$ or produces $x\in \mathrm{WF}$ with $\Vert x\Vert <\Vert y\Vert$. In either case Player II wins.

The axiom of determinacy says that the game is determined. Since Player I has no winning strategy, the winner is therefore

Player II can force both parts of II's winning condition. First choose one coordinate $n$ reserved outside the coding of a fixed infinite descending chain and play $y_n>x_n$. On the remaining reserved coordinates, play values that make the relation coded by $y$ contain that descending chain. Thus $y\notin \mathrm{WF}$ while $y_n\nleqq x_n$ for the chosen $n$. Hence

Let $S$ be the causal rank-raising map on well-order codes obtained by tagging a coded relation and adjoining a new least element. Player II follows the online rule $y=S(x)$. If $x\in \mathrm{WF}$, thenso II wins. If $x\notin \mathrm{WF}$, the tagged recoding ensures $y\ne x$, which is again precisely II's winning condition. Therefore

Apply the Friedman–Moschovakis coding lemma withThe given map $\pi :{\omega }^{\omega }\twoheadrightarrow {\aleph }_2$ supplies the required real codes for ordinals below $\lambda$, while each $g_{\xi }:{\omega }^{\omega }\twoheadrightarrow \mathcal{P}(\xi )$ supplies codes for all possible initial segments of a subset of $\lambda$.

For completeness, fix $A\subseteq {\aleph }_2$ and form the associated Friedman–Moschovakis coding game. The players use $\pi$ to announce ordinals and $g_{\xi }$ to announce candidate codes for $A\cap \xi$, while each may challenge the other's code at a larger ordinal. The Friedman–Moschovakis diagonal argument shows that Player I cannot have a winning strategy. By the axiom of determinacy, Player II has one. The coherence tests in the game ensure that a fixed winning strategy for II can belong to at most one set $A$: if it purported to code distinct $A$ and $B$, a play reaching an ordinal above the least point of disagreement would defeat it.

Every strategy for a game on $\omega$ is coded by a real. Define $F:{\omega }^{\omega }\to \mathcal{P}({\aleph }_2)$ by sending a code for a winning II-strategy to the unique set that it determines, and sending all other reals to the empty set. Every $A\subseteq {\aleph }_2$ has such a strategy, so $F$ is surjective. Hence