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

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.