Borel determinacy: a streamlined proof

In one direction, if $G(A;T)$ is an infinite game without taboos, i.e. $\lceil T\rceil=[T]$, then we can consider $T$ as a game tree with taboos, and the resulting game with taboos is completely identical. Hence the determinacy of games with taboos implies that of infinite games without taboos. The other direction is less trivial:

Let $G(A;\mathbf{T})$ be a game with taboos with Borel payoff set $A\subseteq[T]$. We call a strategy a taboo-strategy if every play consistent with it is taboo for the opposite player, and we call a position $p\in T$ taboo-determined for player I (resp. II) if I (resp. II) has a taboo-strategy for $\mathbf{T}_{p}$. Let $T^{*}$ denote the set of positions in $\mathbf{T}$ that are taboo-determined for either player, and let $T^{\prime}:=T\setminus T^{*}$.

First, we claim that $T^{\prime}$ a pruned game tree, i.e. $\lceil T^{\prime}\rceil=[T^{\prime}]$. Indeed, the children of a taboo-determined position are also taboo-determined, so $T^{\prime}$ is closed downward under $\subseteq$ and thus a game tree. Suppose toward a contradiction that $p\in\lceil T^{\prime}\rceil$ is a finite play. Then every position extending $p$ in $T$ must be taboo-determined and so $p$ must be taboo-determined, a contradiction since $p\in T\setminus T^{*}$.

We’ll show that the determinacy of $G(A\cap[T^{\prime}];T^{\prime})$ implies that of $G(A;\mathbf{T})$. Since $A\cap[T^{\prime}]$ is as simple, topologically, as $A$, this will give our sought after level-by-level equivalence.

Let $\sigma^{\prime}\in\mathcal{S}_{\text{I}}(T^{\prime})$ be a strategy for player I. We use $\sigma^{\prime}$ to construct to a strategy $\sigma\in\mathcal{S}_{\text{I}}(T)$. There are two cases to consider: (a) player II moves to a position $p\in T^{\prime}$ or (b) player II moves to some $q\in T^{*}$ for the first time. In (a), $\sigma$ will follow the strategy defined by $\sigma^{\prime}$. In (b) there are two further sub-cases: if $q$ is taboo-determined for I, then $\sigma$ follows the taboo-strategy defined for $\mathbf{T}_{q}$. If $q$ is taboo-determined for II, then the parent of $q$ must also be taboo-determined for II. This contradicts the minimality of $q$ in $T^{*}$, so this sub-case never happens.

It follows that if player I has a winning strategy $\sigma^{\prime}$ in $G(A\cap[T^{\prime}];T^{\prime})$, then $\sigma$ is winning strategy in $G(A;\mathbf{T})$. Finally, an identical argument shows the same thing for player II. ∎

Assume that $\tilde{\sigma}$ is a winning strategy for player I (the argument for II is identical). Let $x$ be a play in $T$ consistent with $\sigma$. We must show that $x$ is a win for I in $G(A;\mathbf{T})$, i.e. either $x$ is taboo for II, or $x\in A$.

Let $\tilde{x}\in\lceil\tilde{T}\rceil$ be the lift of $x$ along $\tilde{\sigma}$. Then $\tilde{x}$ is consistent with $\tilde{\sigma}$, so it is a win for I in $G(\pi^{-1}(A);\tilde{\mathbf{T}})$. In particular, $\tilde{x}$ is not taboo for I, hence by (iii) of the lifting condition, $\pi(\tilde{x})=x$. Then either $\tilde{x}$ is taboo for II, and so $x$ is as well, or $\tilde{x}\in\pi^{-1}(A)$, in which case $x\in A$. ∎

Follows from Lemma 2, and Lemma 1 applied to clopen determinacy for infinite games (see e.g. [2, Theorem 13.17]). ∎

Let ${}_{n}\mathbf{T}_{j}$ denote the restriction of $\mathbf{T}_{j}$ to its first $n$ levels, and let $i_{n}$ be as above. For all $n$, we set ${}_{n}\mathbf{T}_{\infty}:={{}_{n}\mathbf{T}_{i_{n}}}$. Thus we identify positions (and strategies) up to level $n$ in $\mathbf{T}_{\infty}$ with those in $\mathbf{T}_{i_{n}}$. This is well-defined and independent of choice of $i_{n}$ by assumption.

We define $\pi_{\infty,j}$ and $\phi_{\infty,j}$ by their restrictions to the first $n$ levels of $\mathbf{T}_{\infty}$. Specifically, for $x\in{{}_{n}\mathbf{T}_{\infty}}$, we set $\pi_{\infty,j}(x):=x$ if $j\geqslant i_{n}$, and otherwise set $\pi_{\infty,j}(x)=\pi_{i_{n},j}(x)$. Similarly, for a strategy $\sigma$ in ${}_{n}\mathbf{T}_{\infty}$, set $\phi_{\infty,j}(\sigma)=\sigma$ if $j\geqslant i_{n}$, and set $\phi_{\infty,j}(\sigma)=\phi_{i_{n},j}(\sigma)$ otherwise. Since, by assumption, $i_{k}=0$, $\pi_{\infty,j}$ and $\phi_{\infty,j}$ both satisfy the conditions of a $k$-covering. It is also clear that $\pi_{\infty,i}=\pi_{j,i}\circ\pi_{\infty,j}$ and $\sigma_{\infty,i}=\sigma_{j,i}\circ\sigma_{\infty,j}$ for all $i\leqslant j$. It remains to show that $\mathcal{C}_{\infty,j}$ satisfies the lifting condition:

Let $\tilde{\sigma}$ be a strategy in $\mathbf{T}_{\infty}$, and let $x\in\lceil T_{j}\rceil$ be consistent with $\phi_{\infty,j}(\tilde{\sigma})$. We define $\tilde{x}$, the lift of $x$ along $\tilde{\sigma}$, by its restriction to the first $n$ levels of $\mathbf{T}_{\infty}$, for all $n\in\mathbb{N}$. First, if $j\geqslant i_{n}$, then $\pi_{\infty,j}|_{n}$ and $\phi_{\infty,j}|_{n}$ are the identity, so we can set $\tilde{x}|_{n}=x|_{n}$. Next, if $j<i_{n}$, let $y\in\lceil T_{i_{n}}\rceil$ be the lift of $x$ along $\phi_{\infty,i_{n}}(\tilde{\sigma})$, via the covering $\mathcal{C}_{i_{n},j}$. Again, $\pi_{\infty,i_{n}}|_{n}$ and $\phi_{\infty,i_{n}}|_{n}$ are the identity by assumption, so we set $\tilde{x}|_{n}=y|_{n}$. It now follows from the lifting condition for $\mathcal{C}_{i_{n},j}$ that $\tilde{x}$ is a valid lift of $x$. ∎

We prove the following by induction on countable ordinals $\alpha\geqslant 1$:

$(\dagger)_{\alpha}$ For all $A\subseteq[T]$ such that $A\in\mathbf{\Sigma}_{\alpha}^{0}$, and for all $k\in\mathbb{N}$, there is a $k$-covering of $\mathbf{T}$ that unravels $A$.

We postpone the proof of $(\dagger)_{1}$ to Lemma 7. Now let $\alpha>1$ and assume by induction that $(\dagger)_{\beta}$ holds for all $1\leqslant\beta<\alpha$. Let $A\subseteq[T]$ with $A\in\mathbf{\Sigma}_{\alpha}^{0}$. Then $A=\bigcup_{i\in\mathbb{N}}B_{i}$ where $B_{i}\in\mathbf{\Pi}_{\beta_{i}}^{0}$ for some $\beta_{i}<\alpha$. We define an inverse system $((\mathbf{T}_{i})_{i\in\mathbb{N}},(\mathcal{C}_{j,i})_{i\leqslant j\in\mathbb{N}})$ of trees and coverings that successively unravels the sets $B_{i}$:

Let $\mathbf{T}_{0}:=\mathbf{T}$, with $\mathcal{C}_{0,0}$ the identity. For $n\in\mathbb{N}$ suppose that we have defined $\mathbf{T}_{j}$ and $\mathcal{C}_{j,i}$ for all $i\leqslant j\leqslant n$. By $(\dagger)_{\beta_{n}}$, let $\mathcal{C}_{n+1,n}=\langle\mathbf{T}_{n+1},\pi_{n+1,n},\phi_{n+1,n}\rangle$ be a $(k+n)$-covering of $\mathbf{T}_{n}$ that unravels $\pi^{-1}_{n,0}(B_{n})$. We let $\mathcal{C}_{n+1,n+1}$ be the identity, and for $j<n+1$ we set $\mathcal{C}_{n+1,j}=\mathcal{C}_{n,j}\circ\mathcal{C}_{n+1,n}$.

By construction, each $\mathcal{C}_{j,i}$ is a $(k+i)$-covering of $\mathbf{T}_{i}$. Hence the conditions of Lemma 4 are satisfied, so we let $\mathbf{T}_{\infty}$ and $(\mathcal{C}_{\infty,i})_{i\in\mathbb{N}}$ be the inverse limit constructed by that lemma. By continuity, $\pi_{\infty,0}^{-1}(B_{n})$ is clopen for all $n$, and thus $\pi_{\infty,0}^{-1}(A)$ is open. Finally, Lemma 7 grants us a $k$-covering $\tilde{\mathcal{C}}$ of $\mathbf{T}_{\infty}$ that unravels $\pi_{\infty,0}^{-1}(A)$, and we conclude that $\mathcal{C}_{\infty,0}\circ\tilde{\mathcal{C}}$ is a $k$-covering of $\mathbf{T}$ that unravels $A$. ∎

We define a $k$-covering $\mathcal{C}:=\langle\tilde{\mathbf{T}},\pi,\phi\rangle$ of $\mathbf{T}$ and show that it unravels $A$. It suffices to assume that $A$ is closed since any cover that unravels $A$ also unravels its complement. Increasing $k$ if necessary, we also assume that $k$ is even.

First, we define $\tilde{\mathbf{T}}$. Since $\mathcal{C}$ should be a $k$-covering, we make the first $k$ levels of $\tilde{\mathbf{T}}$ identical to those of $\mathbf{T}$, including taboos. As $k$ is even, player I makes the $(k+1)$’th move. Let $p\in\tilde{\mathbf{T}}$ with $|p|=k$, so we identify $p$ with a position in $\mathbf{T}$. Position $p$ is terminal (hence taboo) in $\tilde{\mathbf{T}}$ if and only if $p$ is terminal $\mathbf{T}$, so we assume that $p$ is not terminal. Let $a$ be a move for I in $\mathbf{T}$ at $p$. Let $Z$ be the set of positions $q\in\mathbf{T}$ such that:

1. (i)

   $p^{\frown}\langle a\rangle\subsetneq q$,

2. (ii)

   $q$ is not terminal in $\mathbf{T}$,

3. (iii)

   $[\mathbf{T}_{q}]\cap A=\mathbb{\emptyset}$,

4. (iv)

   $(\forall r)(p^{\frown}\langle a\rangle\subsetneq r\subsetneq q\rightarrow[\mathbf{T}_{r}]\cap A\neq\mathbb{\emptyset})$.

That is, $q\in Z$ is a non-terminal extension of $p^{\frown}\langle a\rangle$ such that I can only win in the game subtree at $q$ by reaching a taboo. Condition (iv) states that $q$ is a minimal such position.

Then in $\tilde{\mathbf{T}}$, I plays a move of the form

where $a$ is a move for I in $T$ at $p$, and $X$ is a subset of $Z$ (where $Z$ depends on $a$ as above).

The idea is that by playing this move, I is claiming that for every $q\in X$ they have a winning strategy for $G(A;\mathbf{T}_{q})$, and conceding that II can win $G(A;\mathbf{T}_{q})$ for $q\in Z\setminus X$ (note that I can only win in such a $\mathbf{T}_{q}$ by reaching a taboo). Hence I is claiming that the game should be over whenever a position in $Z$ is reached, with I the winner if said position is in $X$ and II the winner otherwise.

If $p^{\frown}\langle a\rangle$ is taboo in $\mathbf{T}$, we declare $p^{\frown}\langle\langle a,X\rangle\rangle$ to be taboo for the same player in $\tilde{\mathbf{T}}$. Otherwise, $p^{\frown}\langle\langle a,X\rangle\rangle$ is not taboo in $\tilde{\mathbf{T}}$, and player II has two options: (1) accept or (2) challenge I’s claim.

Option (1): If II accepts the set $X$, they must play a move of the form

where $b$ is a legal move for II in $\mathbf{T}$ at position $p^{\frown}\langle a\rangle$. The game now proceeds just as in $\mathbf{T}$ from the position $p^{\frown}\langle a\rangle^{\frown}\langle b\rangle$, unless a position in $Z$ is reached. Specifically, let $\tilde{q}:=p^{\frown}\langle\langle a,X\rangle\rangle^{\frown}\langle\langle 1,b\rangle\rangle^{\frown}s$ be a position in $\tilde{\mathbf{T}}$, so that $q:=p^{\frown}\langle a\rangle^{\frown}\langle b\rangle^{\frown}s$ is the corresponding position in $\mathbf{T}$. In accordance with our explanation above, if $q\in X$, we let $\tilde{q}$ be taboo for II in $\tilde{\mathbf{T}}$, otherwise if $q\in Z\setminus X$, we let $\tilde{q}$ be taboo for I.

Option (2): If II challenges I’s claim, they want to show that they can with the game $G(A;\mathbf{T}_{r})$ for some $r\in X$. Specifically, they play a move of the form

where $r\in X$ and $p^{\frown}\langle a\rangle^{\frown}\langle b\rangle\in\mathbf{T}_{r}$. In this case we say that II has challenged position $r$. Then the game is played just as in $\mathbf{T}$, but where all the moves must be played in the game subtree $\mathbf{T}_{r}$.

We can now define $\pi$ as the map sending each position in $\tilde{\mathbf{T}}$ to the corresponding one in $\mathbf{T}$ by forgetting the extra information ($1$, $2$, $X$, and $r$) in moves $k+1$ and $k+2$. It is clear that this satisfies the conditions for a position map.

We check that $\pi^{-1}(A)$ is clopen, as is required for unraveling: Let $\tilde{x}$ be an infinite play in $\tilde{\mathbf{T}}$. If II accepted, then no subsequence of $\pi(\tilde{x})$ belongs to the associated $Z$. Thus $[T_{q}]\cap A\neq\mathbb{\emptyset}$ for all finite $q\subsetneq\pi(\tilde{x})$, but $A$ is closed, so $\pi(\tilde{x})\in A$. On the other hand, if II challenged, then $\pi(\tilde{x})$ extends some position in $Z$, so $\pi(\tilde{x})\not\in A$. Thus $\pi^{-1}(A)$ is exactly the set of infinite plays in $\tilde{\mathbf{T}}$ where II accepts, which is clopen as it is decided after move $k+1$.

It remains to define the strategy map $\phi$ and show that it satisfies the lifting property. We first consider a strategy $\tilde{\sigma}$ for player I in $\tilde{\mathbf{T}}$. We define $\phi(\tilde{\sigma})$ by describing a play of $\mathbf{T}$ from the point of view of player I. In doing so we omit the definition of the strategy for positions in $\mathbf{T}$ not consistent with $\phi(\tilde{\sigma})$—these can be assigned arbitrarily as long as they satisfy the conditions of a strategy map.

For the first $k$ moves, the games $\mathbf{T}$ and $\tilde{\mathbf{T}}$ are identical so I can just follow the moves dictated by $\tilde{\sigma}$ up to this point. If the game reaches a non terminal position of length $k$, $\tilde{\sigma}$ provides a move $a$ for I and a set of positions $X$, and we dictate that I play the move $a$ in $\mathbf{T}$.

From this point, I plays according to $\tilde{\sigma}$ under the assumption that II has accepted the set $X$. This gives I a move to play unless a position in $p\in Z$ is reached, since then the corresponding position in $\tilde{\mathbf{T}}$ is terminal, and $\tilde{\sigma}$ does not give a move. Suppose such a position $p\in Z$ has been reached. If $p\in Z\setminus X$, then I follows an arbitrary strategy in $\mathbf{T}_{p}$ from this point on, since they are effectively conceding a loss here. On the other hand, if $p\in X$, then I follows $\tilde{\sigma}$ according to the assumption that II challenged position $p$, i.e. that II played the move $\langle 2,p,b\rangle$ where $b$ is the $(k+2)$’th move of $p$.

To verify the lifting condition, let $x$ be a play of $\mathbf{T}$ that is consistent with $\phi(\tilde{\sigma})$ as described above. We will define the lift $\tilde{x}$ of $x$ along $\tilde{\sigma}$. If $x$ does not extend any position in $Z$, we let $\tilde{x}$ be the corresponding play in $\tilde{\mathbf{T}}$ with the assumption that II accepted. If $x$ extends a position in $p\in Z\setminus X$, we let $\tilde{x}$ be the (taboo for I) position in $\tilde{\mathbf{T}}$ corresponding to $p$, under the assumption that II accepted. Finally, if $x$ extends a position in $p\in X$, we let $\tilde{x}$ be the corresponding play in $\tilde{\mathbf{T}}$ under the assumption that II challenged $p$. It is easily seen in each case that $\tilde{x}$ is a valid lift.

Now, we do the same for player II by fixing a strategy $\tilde{\tau}\in\mathcal{S}_{\text{II}}(\tilde{T})$ and describing a play in $\mathbf{T}$ from II’s perspective. Again, II follows $\tilde{\tau}$ for the first $k$ moves.

Suppose then that a nonterminal position $q^{\frown}\langle a\rangle$ in $\mathbf{T}$ of length $k+1$ has been reached, i.e. I played $a$ for their $(k+1)$’th move. Let $Z$ be the set of positions as above (recall that this set depends on $q$ and $a$). Let $Y$ be the set of positions $r\in Z$ that are never challenged by $\tilde{\tau}$, meaning that for any $X\subseteq Z$, $\tilde{\tau}$ will never respond to the move $\langle a,X\rangle$ by challenging $r$. Then II plays their $(k+2)$’th move in $\mathbf{T}$ according to $\tilde{\tau}$ under the assumption that I played $\langle a,Y\rangle$ for move $k+1$. Note that by definition of $Y$, $\tilde{\tau}$ will always have II accept here.

From this point, II continues to play according to $\tilde{\tau}$ under the assumption that I has played the set $Y$. This provides II a strategy, unless a position in $Z$ is reached, for then the corresponding position in $\tilde{\mathbf{T}}$ is terminal. Suppose a position $p\in Z$ has been reached. If $p\in Y$, then II follows an arbitrary strategy in $\mathbf{T}_{p}$ from this point on, as they are effectively conceding a loss. If $p\in Z\setminus Y$, then by definition of $Y$ there is a subset $X\subseteq Z$ such that if I plays $X$, then II rejects $p$. Then II follows $\tilde{\tau}$, but now under the assumption that I played the set $X$, and consequently that II challenged the position $p$.

Finally, we let $x$ be a play of $\mathbf{T}$, consistent with $\phi(\tilde{\tau})$, and define a lift $\tilde{x}$ of $x$ along $\tilde{\tau}$. If $x$ does not extend a position in $Z$, we let $\tilde{x}$ be the corresponding position in $\tilde{\mathbf{T}}$ with the assumption that I played the set $Y$. If $x$ extends a position $p\in Y$, we let $\tilde{x}$ be the (taboo for II) position in $\tilde{\mathbf{T}}$ corresponding to $p$, under the assumption that I played $Y$. Finally, if $x$ extends a position $p\in Z\setminus Y$, we let $\tilde{x}$ be the corresponding play in $\tilde{\mathbf{T}}$ under the assumption that I played the set $X$ as in the previous paragraph (recall that this $X$ depends on $p$), and so II challenged $p$. Again, it is easily seen that these define valid lifts. ∎