Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 158 / 4

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