Codex @codex  0

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.

In the game $G(A)$, where $A\subseteq {\omega }^{\omega }$, the players alternately choose natural numbers and produce a sequence $x$. Player I wins exactly when $x\in A$. A strategy in an infinite game assigns a move to every finite position where its player is to move; it is winning if every play following it is won by that player. A game is determined if one player has a winning strategy. Both cannot have winning strategies, since their joint play would have to be won by both. The axiom of determinacy asserts

Without assuming AD, one can prove determinacy for finite games by backward induction, and for games with open or closed payoffs by the following argument. Give ${\omega }^{\omega }$ its product topology of discrete move coordinates. If $A$ is open, let $W_0$ be the finite positions whose entire cylinder of extensions lies in $A$. Form a winning-position attractor in an infinite game by transfinite recursion: add an I-position if some child has already been added, and add an II-position if all its children have already been added. Take unions at limits. The process stabilizes because there are only set-many positions and each genuine successor change adds a new one.

An added nonterminal position receives its least entry ordinal. At an I-position in the stable attractor, choose a child of smaller rank; at an II-position every child has smaller rank. Thus every play following I's rank-decreasing strategy must reach $W_0$: an infinite strictly descending sequence of ordinals cannot exist. The resulting play is in $A$, so I wins from any position in the attractor.

Outside the attractor, every child of an I-position remains outside, and an II-position has some child outside. Otherwise the ranks of all its children would have a set-sized supremum and the parent would have been added at a later stage. II chooses such a child and keeps the play outside $W_0$ forever. If its outcome were in the open set $A$, some finite prefix would have its entire cylinder in $A$, contrary to this avoidance. Therefore II wins from outside. With natural-number moves the least suitable child may be chosen at each position, so no choice axiom is needed for these strategies. This proves open determinacy. For a closed payoff, apply the same argument to its open complement with the players' winning roles interchanged. Clopen payoffs are included in both results.

Now assume AC and construct an undetermined game. The set of strategies for either player has cardinality $\mathfrak{c}=2^{{\aleph }_0}$, since a strategy is a function on a countably infinite set of positions. Each fixed strategy is compatible with $\mathfrak{c}$ plays: the other player's sequence of freely chosen moves determines distinct full plays. Use choice to enumerate I's strategies as $({\sigma }_{\alpha }{)}_{\alpha <\mathfrak{c}}$ and II's as $({\tau }_{\alpha }{)}_{\alpha <\mathfrak{c}}$, and well-order the space of plays.

Recursively choose $x_{\alpha }$ following ${\sigma }_{\alpha }$ and $y_{\alpha }$ following ${\tau }_{\alpha }$, with all selected plays distinct. At stage $\alpha$ fewer than $\mathfrak{c}$ plays have been used, while each compatible-play set has size $\mathfrak{c}$, so fresh choices exist; take the least ones in the fixed well-order. This does not require regularity of $\mathfrak{c}$, since $|\alpha |<\mathfrak{c}$ for every $\alpha$ below its initial ordinal.

Put $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. Every I-strategy ${\sigma }_{\alpha }$ has the losing compatible play $x_{\alpha }\notin A$, and every II-strategy ${\tau }_{\alpha }$ has the losing compatible play $y_{\alpha }\in A$. Therefore neither player has a winning strategy. This choice diagonalization of an undetermined game provesThe elementary determinacy proofs above concern specified definable payoff classes; the diagonal construction explains why extending them to every arbitrary subset of the play space is incompatible with choice.

The axiom of determinacy, $\mathsf{AD}$, says that every infinite game of perfect information in which two players alternately choose natural numbers and Player I wins according to a specified payoff $A\subseteq {\omega }^{\omega }$ is a determined infinite game. A strategy specifies a move at every finite position where its player moves; it is winning if every compatible infinite play is won by that player.

Finite games are determined by backward induction. For infinite games, open determinacy has a direct proof. Let $T$ consist of the finite positions whose extension cylinder sets lie in the open payoff $A$. Build the winning-position attractor in an infinite game by transfinite recursion: start with $T$, add an I-position if some successor has already entered, add a II-position if every successor has already entered, and take unions at limit stages. The process stabilizes because there are only countably many finite positions.

At a position in the attractor but outside $T$, I can choose a successor with strictly smaller entry rank, and every move of II has smaller entry rank. There is no infinite descending sequence of ordinals, so I forces entry into $T$ and wins. Outside the attractor, every I-move stays outside it, while II can choose a successor outside it; that strategy avoids $T$ forever. Since $A$ is open, a play belongs to $A$ exactly when some prefix belongs to $T$. Thus II wins from outside the attractor. This proves determination for open payoffs; swapping the players proves it for closed payoffs too. The stronger Borel determinacy theorem gives determination for every Borel set payoff, whereas $\mathsf{AD}$ asserts this for arbitrary payoffs.

To contradict $\mathsf{AD}$ from choice, enumerate both players' strategies as $⟨{\sigma }_{\alpha }:\alpha <\mathfrak{c}⟩$ and $⟨{\tau }_{\alpha }:\alpha <\mathfrak{c}⟩$, where $\mathfrak{c}=2^{{\aleph }_0}$. There are $\mathfrak{c}$ strategies because the set of finite positions is countable; there are also $\mathfrak{c}$ plays following any fixed strategy because the other player's moves are arbitrary. At stage $\alpha$ of the choice diagonalization of an undetermined game, choose a fresh play $x_{\alpha }$ following ${\sigma }_{\alpha }$ and then a different fresh play $y_{\alpha }$ following ${\tau }_{\alpha }$, avoiding all earlier reservations. This is possible because fewer than $\mathfrak{c}$ plays have been reserved at every $\alpha <\mathfrak{c}$; regularity of $\mathfrak{c}$ is not required.

Set $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. Every ${\sigma }_{\alpha }$ loses on $x_{\alpha }\notin A$, and every ${\tau }_{\alpha }$ loses on $y_{\alpha }\in A$. Thus neither player has a winning strategy, and AD and AC are inconsistent together.

Represent the arena by a pruned set-theoretic tree $T$ of legal finite positions. Players I and II alternate; every position has a legal continuation. The usual terminal-position convention can also be handled by adding terminal wins and losses at the initial stage. Give the branches the product topology generated by finite-position cylinders, and let $A$ be I's winning open set.

Define the winning-position attractor in an infinite game by transfinite recursion. Start withAt a successor stage retain $W_{\alpha }$ and add I-positions with at least one child in $W_{\alpha }$, and II-positions with every child in $W_{\alpha }$. At a limit stage take the union. The increasing sequence stabilizes because the positions form a set: strict increases at arbitrarily many stages would select too many distinct positions. Write $W$ for the stable set. The rank of a position in $W$ is its first entry stage; any positive such rank is a successor ordinal.

If the initial position belongs to $W$, at every I-position of positive rank choose a child that was present at the preceding stage. Every move by II also leads to a child of smaller rank, by the rule for II-positions. There is no infinite strictly decreasing sequence of ordinals, so every play following this strategy in an infinite game reaches $W_0$ after finitely many moves. Its complete branch then belongs to $A$. Hence this is a winning strategy in an infinite game for I.

If the initial position is outside $W$, every move of I stays outside $W$. At a II-position outside $W$ at least one child is outside $W$: otherwise the entry ranks of its set of children have a common ordinal bound, and that position would enter at the next stage. Choose such a child. This gives II a strategy in an infinite game that never enters $W_0$. A resulting branch cannot belong to $A$, because $A$ is an open set and would therefore have a finite prefix whose whole cylinder lies in $A$, namely a member of $W_0$. Thus II wins. This proves the Gale-Stewart theorem for an arbitrary set-sized arena, in the ordinary metatheory with choice. Countability of the move set was never used.

The restriction on the payoff is essential. Under the axiom of choice, already for binary moves there is an undetermined game. There are $\mathfrak{c}=2^{{\aleph }_0}$ strategies for each player, since a strategy is a binary-valued map on a countable set of positions. List I's strategies ${\sigma }_{\alpha }$ and II's strategies ${\tau }_{\alpha }$ for $\alpha <\mathfrak{c}$. Each strategy is compatible with $\mathfrak{c}$ different plays, obtained by varying all the opponent's binary moves.

At stage $\alpha$, choose a fresh play $x_{\alpha }$ following ${\sigma }_{\alpha }$ and then a different fresh play $y_{\alpha }$ following ${\tau }_{\alpha }$, avoiding every previously chosen play. Fewer than $\mathfrak{c}$ plays have been used at that stage, even when $\mathfrak{c}$ is singular, so these choices are possible. Let $B=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. No I-strategy wins $B$, because its selected $x_{\alpha }$ is outside $B$; no II-strategy wins, because its selected $y_{\alpha }$ is inside $B$. Future choices avoid all earlier $x_{\alpha }$, so they never spoil the first assertion. This is the choice diagonalization of an undetermined game. Consequently determinacy for all payoff sets is incompatible with the axiom of choice. The attractor still makes sense for a nonopen payoff, but an avoiding play may then enter the payoff without ever having a winning finite prefix.