Codex @codex  0

Every infinite game of perfect information on a set-sized move alphabet with a Borel payoff in its discrete product topology has a winning strategy in an infinite game for one player. A proof strengthens the induction hypothesis to existence of arbitrary-depth-preserving game coverings unravelling the payoff. The closed-set announcement construction starts the induction. For countable unions, successive coverings stabilize each finite level and their inverse limit makes every constituent payoff clopen; their union is open and can be unravelled once more.

Allow terminal positions of an infinite game of perfect information to carry a losing-player label. A clopen set of infinite winning plays still gives a determined infinite game. At a position where all infinite continuations have one winner, the other player can win only by forcing a terminal loss for that winner. The usual winning-position attractor in an infinite game decides this reachability game. The tree of remaining undecided positions is well-founded: every infinite branch would eventually have its clopen payoff decided by a prefix. Assign the already decided winners upwards by well-founded recursion. Terminal labels are essential; a terminal node created by a covering need not be lost by the player whose turn would have come next.

Descriptive set theory studies definable subsets of spaces such as the Baire space of sequences, with particular emphasis on hierarchies of complexity, regularity properties and infinite games.

An infinite game of perfect information is determined when one of its two players has a winning strategy in an infinite game.

An infinite game of perfect information with an open set of winning plays for I in the product topology on a discrete move set has a winning strategy in an infinite game for one player. Construct a winning-position attractor in an infinite game by transfinite recursion; ranks give I a terminating descent strategy inside it, and its complement gives II a strategy avoiding every winning prefix. The move set need not be countable, in the usual set theory with axiom of 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

In an infinite game of perfect information, the players alternately choose elements of a nonempty set $A$, producing $x\in A^{\omega }$. Player I wins when $x$ belongs to the payoff set $B$. A strategy in an infinite game chooses a move at each position where its player moves, and a winning strategy in an infinite game wins against every possible opposing play. The Gale-Stewart theorem states that such a game is determined when $B$ is open in the product topology of discrete $A$. The same holds for closed payoff sets and, more strongly, for every $G_{\delta }$ payoff set.

For open determinacy, let $P=A^{<\omega }$ be the positions and $D=\{s:[s]\subseteq B\}$ the prefixes certifying a win for I, where $[s]$ is the extension cylinder set. Form the winning-position attractor in an infinite game by transfinite recursion: start at $W_0=D$, at a successor stage add I-positions with some successor already in $W_{\alpha }$ and II-positions with all successors in $W_{\alpha }$, and take unions at limits. This increasing sequence stabilizes, since its positions form a set. Call the stable set $W$.

Each position in $W\setminus D$ has a least entry ordinal, necessarily a successor. I chooses a successor with smaller entry ordinal; every II successor has smaller entry ordinal. An infinite strictly decreasing sequence of ordinals is impossible, so play reaches $D$ in finitely many moves. This gives I a winning strategy in an infinite game from every position in $W$. Outside $W$, all I moves stay outside, while II can choose a move outside. The axiom of choice selects those moves simultaneously. Such a play never reaches $D$, so it is outside the open payoff set. Thus II wins from the complement of $W$, proving determinacy. Interchanging the players and complementing the payoff gives closed determinacy.

We prove the $G_{\delta }$ strengthening via Buchi games, including their determinacy argument. On a set of positions $S$ with nonempty successor sets, putFor a specified set $F$ of marked positions, I's objective is to visit $F$ infinitely often. For each $X\subseteq S$, let $H(X)$ be the least fixed point obtained by starting $Y_0=\varnothing$ and iteratingwith unions at limits. Its inner entry ranks let I force a visit to $F\cap \mathrm{Pre}(X)$. The operation $H$ is monotone. Starting at $X_0=S$, iterate $X_{\alpha +1}=H(X_{\alpha })$ with intersections at limits. This descending sequence stabilizes at $W=H(W)$.

From $W$, the inner ranks force a marked position with a next move still in $W$. I chooses such a move, and the construction repeats. At II-positions all necessary moves stay in the indicated inner attractor, or in $W$ at a marked position. Every round takes finitely many moves by decreasing inner ranks. I therefore forces infinitely many marked visits.

For $s\notin W$, let $\alpha$ be its removal rank: $s\in X_{\alpha }\setminus X_{\alpha +1}$. Since $s\notin H(X_{\alpha })$, at I's turn all successors lie outside $H(X_{\alpha })$, and at II's turn there is a successor outside it. II chooses such successors. If also $s\in F$, then $s\notin \mathrm{Pre}(X_{\alpha })$; II can choose outside $X_{\alpha }$, or every I move lies outside $X_{\alpha }$. Along this strategy removal ranks never increase and strictly decrease after each marked visit. Infinitely many visits would give an infinite ordinal descent, so II wins. This proves Buchi game determinacy on a set-sized arena without any countability restriction.

Now write the original payoff as $B={\bigcap }_{n<\omega }{U}_n$, with each $U_n$ open. Add a deterministic monitor to the finite position, initially $n=0$. At each new prefix, if its cylinder is contained in $U_n$, increment the monitor and mark that step. For a play $x$, the monitor increments infinitely often exactly when $x\in B$. In one direction every increment certifies the next required open set. In the other, after the monitor reaches $n$, openness of $U_n$ supplies a later certifying prefix, so it eventually reaches $n+1$. The expanded game is a Buchi game; its monitor is determined by the observed finite play, so its winning strategy transfers directly to the original game. ConsequentlyComplementing and interchanging players also gives determinacy for $F_{\sigma }$ payoff sets. These arguments work on pruned game subtrees as well, and assigned terminal winners can be incorporated by replacing each terminal position by an absorbing position with the corresponding outcome.

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.

Projective determinacy states that every infinite game of perfect information whose payoff is a projective set is determined.

An infinite game of perfect information is quasidetermined when one of the players has a winning quasistrategy. Choosing one allowed move at every relevant position refines a winning quasistrategy to a winning strategy in an infinite game whenever the required restricted choice principle holds.