Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 21 / 6 / b / Solution

For $A\subseteq {\omega }^{\omega }$, let the players alternately choose natural numbers, producing $x\in {\omega }^{\omega }$; I wins exactly when $x\in A$. A strategy assigns a move to each finite position at which its player moves. It is winning if every compatible completed play is won by that player. A game is determined when one player has a winning strategy. The axiom of determinacy is

We can prove determinacy for open and closed payoffs, including clopen payoffs; finite games are covered by backward induction. Here is the full open-payoff argument. For an open $A$, let $W_0$ consist of finite positions whose entire cylinder of continuations is contained in $A$. Recursively putand take unions at limits. Since positions form a set, this process reaches a fixed point $W$. More explicitly, a strict increase at each stage would assign a distinct position to each stage beyond the Hartogs bound of the position set, which is impossible; for natural-number moves the least newly added position in a fixed enumeration makes that assignment explicit.

If the initial position belongs to $W$, I can win. At an I-position first added at a successor stage, choose the least move to a position of smaller first-entry rank. At an II-position first added at a successor stage, every successor already has smaller rank. A play following this strategy cannot have an infinite strictly descending sequence of ordinal ranks, so reaches $W_0$ in finitely many steps; all its further continuations lie in $A$. If the initial position is outside $W$, II keeps the play outside $W$: at an I-position no successor is in $W$, and at an II-position at least one successor is outside $W$, so II chooses the least such move. The play never reaches a winning prefix. Since $A$ is open, membership in $A$ would have been certified by some finite prefix, so the resulting play is outside $A$. Thus every open game is determined. Applying this argument to the open complement of a closed payoff, with the players' objectives interchanged, proves closed determinacy too. The argument needs no choice of moves beyond taking the least available natural number.

To refute AD under AC, first use binary moves. There are $\mathfrak{c}=2^{{\aleph }_0}$ strategies for each player, since its positions form a countable set. Enumerate them as $({\sigma }_{\alpha }{)}_{\alpha <\mathfrak{c}}$ and $({\tau }_{\alpha }{)}_{\alpha <\mathfrak{c}}$. Each fixed strategy admits exactly $\mathfrak{c}$ compatible plays: the other player's arbitrary binary sequence determines the completed play injectively. Recursively choose a play $u_{\alpha }$ following ${\sigma }_{\alpha }$ and a play $v_{\alpha }$ following ${\tau }_{\alpha }$, each different from all earlier reservations and from each other. This is possible because at stage $\alpha$ fewer than $\mathfrak{c}$ plays have been reserved. No regularity assumption on $\mathfrak{c}$ is used: every ordinal $\alpha <\mathfrak{c}$ has cardinality below $\mathfrak{c}$, and doubling an infinite smaller cardinal does not reach $\mathfrak{c}$.

Set $B=\{v_{\alpha }:\alpha <\mathfrak{c}\}\subseteq 2^{\omega }$. Strategy ${\sigma }_{\alpha }$ loses on $u_{\alpha }\notin B$, while ${\tau }_{\alpha }$ loses on $v_{\alpha }\in B$. Thus this binary game is undetermined. Turn it into a natural-number game by declaring that the first player to play a number outside $\{0,1\}$ loses. Formally its I-payoff isA winning strategy in this game could not prescribe an illegal move after a compatible legal history, since the opponent could thereby win. Its restriction to legal histories would therefore give a winning binary strategy, contradicting the construction. Hence the choice diagonalization of an undetermined game provesThis does not contradict open or closed determinacy: the diagonal payoff has no such regularity requirement.