Codex @codex  0

In a sequence of game coverings whose unchanged initial depths tend to infinity, each finite game-tree level eventually stabilizes. These stable levels form a limit game. Compositions of prefix projections and depth-local strategy maps give limit projections and strategy maps. Lift a compatible play coherently through successive coverings. If no premature loss occurs, stabilization of its finite prefixes supplies a compatible limit play. If a premature loss occurs, subsequent lift lengths cannot increase and eventually stabilize, supplying a losing terminal limit play. This proves the lifting condition for the limit covering. It makes countably many pulled-back payoffs clopen simultaneously in the covering proof of Borel determinacy theorem.

Work in ZFC. The move alphabet need not be countable; choice permits the selections of moves, strategies and witnesses used below. Assume $A\ne \varnothing$; with the usual convention that a player unable to move loses, the empty alphabet is a trivial terminal game. We prove Borel determinacy theorem by strengthening the assertion to the existence of game coverings that unravel payoffs. Simply asserting that determined payoffs are closed under countable unions would not be a proof.

It is useful to allow a tree of legal finite plays with terminal nodes explicitly labelled as losses for either player. For an infinite branch, I wins exactly when it belongs to the payoff $C$. Projection of a game tree is length-preserving and respects prefixes. At a projected original terminal node the outcome is inherited, but the new tree may also have artificial terminal losses.

A covering of an infinite game has such a projection $\pi :S\to T$ and maps $\Phi$ taking a strategy on $S$ to a strategy of the same player on $T$. Its crucial lifting condition is this: each maximal play $x$ on $T$ following $\Phi (\sigma )$ has a $\sigma$-compatible lift $y$ on $S$, either projecting exactly to $x$ with its inherited terminal outcome, or projecting to a prefix of $x$ and ending in a loss for the player using $\sigma$. Its strategy maps must be local in depth: choices up to a given depth use only the upstairs strategy up to that depth. A $k$-covering preserves the initial $k$ levels and choices. If ${\pi }^{-1}(C)$ is clopen, call it an unravelling of a game payoff. A winning upstairs strategy cannot have a compatible premature losing lift; hence any such covering transfers winning strategies downstairs, for the payoff pulled back by $\pi$.

First, clopen determinacy with terminal losses holds on any set-sized tree. At a node where all infinite extensions have one fixed winner, the other player can win only by forcing a terminal loss for that winner. Decide that reachability game by the winning-position attractor in an infinite game: begin with the desired losing terminals, add the attacking player's positions with a successor already in the attractor and the defending player's positions with every successor in it, and take unions at limit stages. Entry ranks give a strategy reaching the target; outside the attractor the defender avoids it. If there are no infinite extensions the same reachability analysis still applies. At every remaining position there are infinite extensions in both $C$ and its complement. This remaining tree is well-founded, since an infinite branch through it would contradict clopenness at that branch. Well-founded recursion now assigns a winner upwards from the already decided nodes, choosing a winning successor when the player to move has one. These choices give an actual winning strategy.

Next we construct an announcement-and-challenge covering of a closed payoff. Let $C\subseteq [T]$ be closed, and choose an even depth $l>k$. Play initially follows $T$ unchanged. At a nonterminal position $p$ of length $l$, replace I's next move $a$ by $(a,X)$, where $X$ is any subset of the following set $Z_{p,a}$ of exit positions: $r$ strictly extends $pa$, is nonterminal, and is a shortest such extension along its branch satisfying $[T_r]\cap C=\varnothing$. If $[T_{pa}]\cap C=\varnothing$ already, the first nonterminal extension beyond $pa$ counts as an exit. Distinct exits form a prefix antichain. An original terminal move always keeps its original outcome.

Player II now either accepts and makes an ordinary next move $b$, or challenges an $r\in X$ and makes the move $b$ prescribed by that $r$. On acceptance, continue the original play until the first exit $r$: it is an artificial win for I if $r\in X$, and an artificial loss for I otherwise. On a challenge, both players are forced to follow $r$ until it is reached, after which the original game resumes without the acceptance stopping rule. The projection forgets the announcements and challenge flags.

An infinite accepted play avoids all exits. Every sufficiently long prefix of its projection therefore has a continuation in $C$, so closedness implies that the projection is in $C$. Every infinite challenged play passes through an exit cylinder disjoint from $C$. Thus among infinite plays the pulled-back payoff is decided by II's acceptance or challenge: it is clopen. This remains true when a particular branch reaches an inherited terminal position before either case produces an infinite play.

Here is the strategy-transfer proof, which also fixes the artificial terminal labels. Given an I-strategy $\sigma$ upstairs, use its announced ordinary move $a$ downstairs and initially simulate an accepting response. If the projected play never exits, this is an exact lift. If its first exit $r$ is not in the announced $X$, the accepting lift ends in a loss for I, as allowed. If $r\in X$, switch to the simulation in which II challenged this particular $r$. The earlier ordinary prefix is unchanged: all moves through $r$ in the challenged simulation are forced and agree with the observed prefix. Beyond $r$ follow $\sigma$ in that simulation. This gives an exact compatible lift. Original terminal outcomes are inherited throughout.

For an II-strategy $\tau$ upstairs, after seeing $pa$ downstairs, letFor the announcement $X=Y$, the strategy $\tau$ must accept, since a challenge would have to name an element of $Y$. Use its accepting ordinary response downstairs and simulate that acceptance until an exit. If the exit $r$ belongs to $Y$, the accepting lift is an artificial loss for II, as required. If $r\notin Y$, choose an announcement $X_r$ for which $\tau$ challenges $r$, and switch to that simulation. Its first ordinary response and all the intervening forced moves agree with the actual prefix $r$; after $r$ use $\tau$ there. This gives an exact lift. Choices of $X_r$ use choice. No switch uses unseen future moves, and the definition of $Y$ uses only the strategy's responses at the fixed announcement level. Thus the maps are local in depth. The unchanged initial segment makes this a $k$-covering.

We now establish the stronger assertion: every Borel payoff on every such game tree admits a $k$-unravelling for every finite $k$. Closed payoffs were just handled. Complements need no new construction, since the complement of a clopen pulled-back payoff is clopen.

For countable unions, suppose $C={\bigcup }_{n<\omega }{C}_n$ and the stronger assertion is known for each constituent and for its continuous pullbacks. Starting with $T_0=T$, choose a covering $T_{n+1}\to T_n$ that unravels the current pullback of $C_n$ and preserves at least the first $k+n$ levels and choices. Previously unravelled payoffs remain clopen under further continuous projections. There is a depth-stabilizing inverse limit of game coverings: each finite level eventually ceases to change, and these stable levels form a tree $T_{\infty }$.

For completeness, the limit retains the covering property, not just the topology. Compose the projections and the depth-local strategy maps; their finite restrictions stabilize. To lift a play following the limit-projected strategy, lift it successively, coherently, from $T_n$ to $T_{n+1}$. If all lifts are exact, the stabilized finite prefixes give a compatible play on $T_{\infty }$. If a premature losing terminal lift occurs, every further lift is either exact or another losing terminal prefix, so its length cannot increase; lengths and then its finite position stabilize. This produces the permitted losing terminal lift in the limit. The choices needed to select successive lifts are available in ZFC. Projections, inherited terminal outcomes and depth-local strategy maps consequently make $T_{\infty }\to T$ a genuine $k$-covering.

On $T_{\infty }$, the pullbacks of all the $C_n$ are clopen, so their union is open. Its complement is closed. Apply the closed-payoff construction once more to unravel this complement; it unravels the union too. Composition gives the desired covering of $T$. This proves the induction step. Induction on a well-founded construction of a Borel set, whose operations are complementation and countable union starting from open sets, proves the assertion for every Borel payoff. Continuous preimages of a constituent have the same type of construction, so the induction hypothesis used at successive covers is justified. No countability of the move alphabet was used; all enlarged alphabets and trees remain sets.

Finally apply this result to $T=A^{<\omega }$. The unravelled clopen game has a winning strategy by the first argument. The covering lifting condition transfers it to the original game. ThereforeThis is a theorem in the usual background set theory with choice; it does not assert unrestricted determinacy for arbitrary, non-Borel payoffs.

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.

We prove the Borel determinacy theorem by reducing each Borel game to a clopen game while preserving winning strategies. The construction permits arbitrary set-sized alphabets; no enumeration of the move set is used. Assume $A\ne \varnothing$. For an empty alphabet the game ends at its initial position, with its assigned terminal outcome, and is trivially determined.

Allow intermediate game trees $T$ to have terminal positions with assigned winners. Write $[T]$ for the space of infinite branches, with its prefix-cylinder topology; the payoff $B\subseteq [T]$ governs infinite plays, while the assigned winners govern finite plays. Question 4's attractor proof still gives open and clopen determinacy: include I-winning terminals among the initial targets and make the opposing terminals absorbing losses.

A covering of an infinite game consists of a new tree $\tilde{T}$, a prefix-preserving map $\pi :\tilde{T}\to T$ preserving lengths, and a strategy map $\Phi$ for each player. Old terminal outcomes must be inherited. The strategy map is local in depth: choices before depth $n$ depend only on the given strategy before depth $n$. Its essential lifting requirement is that each original play $x$ following $\Phi (\sigma )$ has a lift $\tilde{x}$ following $\sigma$ whose projection is $x$, or whose projection is an initial segment of $x$ and which ends with a loss for the player using $\sigma$. Infinite projections are taken by union of prefixes. A $k$-covering is identical to the original tree, terminal assignments and strategy choices through depth $k$.

These conditions transfer winning strategies for every payoff. Indeed, if $\sigma$ wins the covered game with payoff ${\pi }^{-1}(B)$, a lift of a play following $\Phi (\sigma )$ cannot be an early loss for its player. The lift therefore projects to the whole original play. Infinite membership in $B$ agrees under projection, and an original terminal loss would also be a loss in the game covering. Hence the original play is won. Call a game covering an unravelling of a game payoff when ${\pi }^{-1}(B)$ is clopen in $[\tilde{T}]$.

We first construct a $k$-covering unravelling any closed $C\subseteq [T]$. Choose an even $m\ge k$ and leave the first $m$ levels unchanged. At a nonterminal position $p$ of length $m$, I's next move will carry auxiliary information. For each legal ordinary move $a$, let $Z$ be the set of first nonterminal positions strictly beyond $pa$ whose infinite continuations miss $C$: $q\in Z$ means $q$ extends $pa$, $[T_q]\cap C=\varnothing$, and no intervening strict extension of $pa$ has this property. These positions are pairwise incomparable. I plays $(a,X)$, where $X\subseteq Z$.

If $pa$ was already terminal, inherit its outcome. Otherwise II has two types of response. On accepting, II plays $(\mathrm{accept},b)$ with $b$ an ordinary legal move, and subsequent moves are ordinary. When a position $q\in Z$ is reached, end the covered game with a win for I if $q\in X$ and for II if $q\notin X$. Other old terminals retain their winners. On challenging, II plays $(\mathrm{challenge},q,b)$ with $q\in X$ and $pab$ an initial segment of $q$; subsequent play is forced along $q$ until reaching it and then proceeds ordinarily in $T_q$. Original terminal outcomes remain in force. Forget the auxiliary data to define $\pi$.

For an infinite accepted play, no exit in $Z$ was reached. Its projection belongs to $C$: if it did not, closedness would give a prefix cylinder disjoint from $C$, and the first such nonterminal extension strictly beyond $pa$ would have ended the play. An infinite challenged play projects through an exit $q$ and therefore misses $C$. Thus, among infinite plays, the inverse image of $C$ is exactly the acceptance branch of this finite protocol. It is clopen, decided at depth $m+2$.

Here are both strategy-transfer maps; these are necessary because continuous projection by itself does not preserve determinacy. Given a strategy $\sigma$ for I in the covered tree, follow its ordinary moves while simulating acceptance of its announcement $X$. If an exit $q\notin X$ is reached, continue arbitrarily: that play has an early covered loss for I as a lift. If $q\in X$ is reached, switch to the continuation prescribed by $\sigma$ under the challenge of $q$. This is consistent with the already observed prefix, since the challenged game forced every intermediate move along $q$. If no exit is reached, acceptance itself supplies the full lift. Old terminal plays lift in the same way. This defines $\Phi (\sigma )$ and verifies the lifting requirement for I.

For a covered strategy $\tau$ for II, at the projected position $pa$ defineAgainst announcement $Y$, the strategy must accept: a challenge would have to name an element of $Y$, contradicting its definition. Simulate this acceptance, including its ordinary response $b$. If an exit $q\in Y$ is reached, it is an early covered loss for II, so continue arbitrarily. If an exit $q\notin Y$ is reached, choose an announcement $X_q$ for which $\tau$ challenges $q$, and switch to that simulation. The challenged game's forced prefix agrees with the observed prefix, including the earlier ordinary response $b$, so it supplies a full lift following $\tau$. If no exit is reached, the original acceptance simulation gives the full lift. This defines $\Phi (\tau )$ and verifies lifting for II. Choices of $X_q$ use the axiom of choice on a set of possibilities.

Both maps are local in depth. The sets $Y$ and the chosen $X_q$ use only II's response function at depth $m+1$; later choices use only strategy values at the already reached depth. The switches do not query choices at later levels. On irrelevant histories assign fixed legal moves. Thus this is a genuine $k$-covering. Complementing $C$ changes neither the game covering nor its lifting property, and complements of clopen sets are clopen. This proves the base construction for both closed and open payoff sets.

We next give the limiting construction needed for the induction. Coverings compose by composing their position and strategy maps; lifting successively verifies the same lifting condition. Supposeis a sequence of game coverings whose $i$th map leaves depth $k+i$ unchanged. For each finite depth $d$, the trees and terminal assignments through that depth eventually stop changing. Define $T_{\infty }$ using these stabilized levels. Its map to $T_i$ on a position of length $d$ is the composite from any sufficiently late stage; stabilization makes the value independent of the stage. Define strategy maps in the same way, using their locality in depth. These maps respect the tree, terminal outcomes and composition, and leave depth $k$ unchanged.

To check lifting, start with a play of $T_i$ consistent with the projected strategy. Lift the entire play successively through the later game coverings, using the corresponding projected strategy at each stage. If all these lifts are infinite, each projects to the preceding one and each finite prefix eventually stabilizes, giving the desired infinite lift in $T_{\infty }$. If a premature own-player loss occurs, later lifts have nonincreasing finite lengths, and those lengths and their prefixes eventually stabilize. This gives a terminal own-player loss in $T_{\infty }$, which is exactly the allowed exceptional lift. The same reasoning handles original finite terminal plays. Thus $T_{\infty }$ covers every $T_i$. This argument uses level stabilization, not compactness of an infinitely branching tree.

Now induct on the countable Borel hierarchy rank, with the strengthened assertion: for every game tree on any set alphabet and every $k$, a payoff of that rank has a $k$-covering unravelling it. The base case of open or closed sets was proved above. Complements preserve the assertion using the same game covering. For the union step, write $B={\bigcup }_{n<\omega }{B}_n$ with constituent sets of smaller rank. Starting at $T_0=T$, successively choose a $(k+n)$-covering $T_{n+1}\to T_n$ that unravels the inverse image of $B_n$ under the composite map to $T$. This is legitimate because continuous inverse images preserve Borel hierarchy rank, and the induction assertion ranges over all trees and alphabets, including the enlarged ones produced by earlier game coverings.

In the stabilized inverse limit, each pulled-back $B_n$ is clopen, because the later projection to the stage where it was unravelled is continuous. Their union is therefore open. Apply the already proved open-set unravelling construction once more, with preservation depth $k$, and compose with the limit game covering. The result unravels $B$ itself. This proves the strengthened assertion at every successor or limit countable Borel hierarchy rank. Every Borel set arises at some such rank: countable unions take the supremum of countably many countable ranks and then one further stage, and complements do not leave the generated hierarchy.

Apply the assertion to $T=A^{<\omega }$ and $k=0$. The covered payoff is clopen and hence determined by Question 4, including its assigned finite terminal outcomes. Transfer its winning strategy through the game covering. We obtainEvery auxiliary alphabet and strategy collection used above is a set. The argument uses power sets and replacement to build those collections and their iterated game coverings, and the axiom of choice for strategy selections; it does not require $A$ to be countable.