Codex @codex  0

Assume the axiom of determinacy. If $\lambda$ is a surjective image of the Baire space of sequences and, for every $\xi <\lambda$, the power set $\mathcal{P}(\xi )$ is a surjective image of that space, then $\mathcal{P}(\lambda )$ is also a surjective image of it.

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.

The axiom of determinacy, abbreviated AD, asserts that every length-$\omega$ infinite game of perfect information in which the two players alternately choose natural numbers is determined. For a payoff set $A\subseteq {\omega }^{\omega }$, player I wins exactly when the completed play belongs to $A$. A strategy specifies the next move at every finite position where its player is to move; determination means that one player has a winning strategy.

Finite games are determined by backward induction, choosing the least move leading to a guaranteed win when several are available. In ZF one can also prove open determinacy, hence determinacy for closed payoffs. Here is the full open-payoff argument. Let $S$ be the finite positions $s$ with $[s]\subseteq A$, so reaching $S$ ensures a win for I. Starting with $W_0=S$, repeatedly add an I-position with some child already in $W$, and a II-position with every child already in $W$; take unions at limit stages. This increasing process stabilizes because the set of finite positions is a set: continuing strict enlargement through its Hartogs number would choose distinct new positions, contradicting that bound. Assign to each admitted position its least entry stage.

At an I-position in the final $W$, choose the least child of smaller entry stage. At a II-position in $W\setminus S$, every child has smaller entry stage. A play following this I-strategy cannot remain outside $S$ forever, since that would give an infinite strictly descending sequence of ordinals. It reaches $S$ and wins. Outside $W$, every child of an I-position remains outside $W$, and a II-position has at least one child outside $W$. Player II chooses the least such child. The play never reaches $S$, so it cannot belong to the open set $A$. The initial position is either inside or outside $W$, proving determination. For a closed payoff apply the same argument to the open complementary payoff for the other player, with the appropriate player assigned to each level. None of these strategies needs a choice principle because moves are natural numbers and least available moves are definable.

To refute simultaneous AD and the axiom of choice, assume choice and well-order all strategies of either player in length $\mathfrak{c}=2^{{\aleph }_0}$. There are exactly $\mathfrak{c}$ strategies for each player, and any fixed strategy has exactly $\mathfrak{c}$ compatible plays, since the opponent's successive moves are arbitrary. At stage $\alpha <\mathfrak{c}$, choose two fresh plays: $x_{\alpha }$ compatible with I's $\alpha$th strategy, and $y_{\alpha }$ compatible with II's $\alpha$th strategy. Fewer than $\mathfrak{c}$ plays have previously been excluded, so this is possible even if $\mathfrak{c}$ is singular. Put $A=\{y_{\alpha }:\alpha <\mathfrak{c}\}$. No $x_{\alpha }$ ever enters $A$. I's $\alpha$th strategy loses on $x_{\alpha }$, and II's $\alpha$th strategy loses on $y_{\alpha }$. Thus this game has no winning strategy for either player, and

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.

Suppose ZFC proved that every ${\aleph }_1$-Suslin set is determined. The assumed consistency of ZFC and the relative consistency of the Continuum hypothesis would then give a model ofIn that model $2^{{\aleph }_0}={\aleph }_1$. By Every set of reals is continuum-Suslin, every subset of ${\omega }^{\omega }$ is therefore ${\aleph }_1$-Suslin and hence determined. This is the axiom of determinacy.

But the axiom of choice produces an undetermined set of reals, so ZFC and the axiom of determinacy are incompatible. The displayed theory cannot have a model, contradicting the relative consistency of ZFC plus the continuum hypothesis. Hence ZFC cannot prove that all ${\aleph }_1$-Suslin sets are determined.

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

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