= 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
$$
\boxed{\mathsf{AD}:\quad\text{every }A\subseteq\omega^\omega\text{ gives a determined game}.}
$$
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 put
$$
W_{\alpha+1}=W_\alpha\cup\{p:\text{I moves at }p\text{ and some }p^\frown n\in W_\alpha\}
\cup\{p:\text{II moves at }p\text{ and every }p^\frown n\in W_\alpha\},
$$
and 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 \b[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\}\subseteq2^\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 is
$$
A=B\cup\{x\in\omega^\omega:\text{the first }n\text{ with }x(n)>1\text{ is odd}\}.
$$
A <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> proves
$$
\boxed{\mathsf{AC}\Longrightarrow\neg\mathsf{AD}.}
$$
This does not contradict open or closed determinacy: the diagonal payoff has no such regularity requirement.
Back to article page
