8. banach–mazur game

problem

Fix a set $A⊆𝒞$. Alice and Bob are playing the following game, called the Banach–Mazur game $\mathsf{BM}(A)$. Alice takes the first turn. On their turn, each player picks an arbitrary nonempty finite sequence of $0$s and $1$s. This produces sequences $s_0,s_1,s_2,…$ as shown below:

$$\begin{array}{c|c} \text{Alice} & s_0 && s_2 && … & s_{2k} && … \\ \hline \text{Bob} && s_1 && s_3 & … && s_{2k+1} & … \end{array}$$

The game continues indefinitely and yields an infinite string $x≔s_0 s_1 s_2 …$. Alice wins if and only if $x∈A$. Show that Bob has a winning strategy in this game if and only if $A$ is meager.

proof

For each $p∈\{0,1\}^*$ let $B_p=\{x∈𝒞:\text{\(x\) has prefix \(p\)}\}$, and recall that $\{B_p:p∈\{0,1\}^*\}$ forms a basis of the topology of $𝒞$.

• (⟹) Suppose $A$ is meager. Then $A^∁$ contains a countable intersection of open dense sets, so let $\{U_n\}_{n∈ℕ}$ be a collection of open sets so that $⋂_{n∈ℕ}U_n⊆A^∁$.

  Define a strategy for Bob as follows. Fix $k∈ℕ$, and assume turns $0,…,2k$ have already been played, resulting in a prefix $p≔s_0 s_1 … s_{2k}$. Note that $B_p$ is open and non-empty, so $S∩U_k$ is open as well, and non-empty since $U_k$ is dense. In particular, there exists another basic open set $B_{p'}⊆B_p∩U_k$ for some $p'$ extending $p$. Then let Bob’s next move be the suffix $s_{2k+1}$ so that

  $$p' = p s_{2k+1}.$$

  We check that this is a winning strategy for Bob. In particular, on the $k$-th round, Bob’s forces the to be in $U_k$. Thus the limiting sequence $x∈U_k$ for all $k$, i.e. $x∈⋂_{k∈ℕ}U_k⊆A^∁$, so Bob wins.

• (⟸) Suppose Bob has a winning strategy.