# Banach-Mazur Game: Proof about winning strategies

I have to hold a presentation about the Banach-Mazur-Game to undergraduates this week. It should all stay very simple, so I will mainly only talk about the "original" Banach-Mazur Game on $\mathbb{R}$. So we play for the set $A \in \mathbb{R}$. Player I and II alternate choose arbitrary intervals $I_{0} \supseteq I_{1} \supseteq \dots \supseteq I_{2n-1}$, where player I is choosing the intervals with even index, and player II is choosing the intervalls with odd index.

Player I wins, when $\bigcap_{i \in \mathbb{N}} I_{i} \cap A \neq \emptyset$, otherwise player II wins.

I now want to proof, that there exists a winning strategy for player II (that means, a "rule" by which player II has to choose her/his intervals) iff A is meager.

meager $\Rightarrow$ winning strategy for II is pretty easy

winning strategy $\Rightarrow$ meager is giving me troubles:

The proofs in the books are all very long and technical. My advisor gave me the following proof, which I think is either wrong or which I don't understand yet:

Let player I choose the first interval $I_{0}$. Then play the game with changed roles for $A^c$. It follows, that player I has a winning strategy, if $A^c$ is meager in $I_0$.

(i) My advisor kept claiming, the Banach-Mazur game is symmetric (not quite sure I know what that means), thats why this changing roles works (also not sure what that means, is it just, that player I now plays for empty intersection, and player II for nonempty?)

(ii) Maybe this is a really easy thing, but I don't see where I'm using, that player II has a winning strategy and how it follows, that A has to be meager??

I would be really thankful for some thought here before I go bother my advisor again...!!!

• If you don't know about the chapter on this in Oxtoby's book Measure and Category, you will want to look at that. Also, a very elementary survey that I suspect not many people know about is the following: Don Lane Hancock, Using the Banach-Mazur game to introduce different sizes of infinite sets, Mathematics and Computer Education 32 #1 (February 1998), 44-50. – Dave L. Renfro May 21 '14 at 14:02
• Informally: If II has a winning strategy $\tau$ then by that for any game run leading to $A$ there is some game situation $u$ where II can prevent following further that game run. Then covering $A$ by a union of sets that is indexed by these game situations (guaranteed by $\tau$) leads to a countable coverage of $A$. The sets of that coverage can be chosen such that they are nowhere dense and therefor proof $A$ to be meager. – FWE Aug 22 '14 at 14:33

This may be long and technical, like the book proofs you complained about, but it's the easiest proof I know.

Assume $\sigma$ is a winning strategy for Player II, and consider all the finite partial plays $p$ of the game where (1) it is I's turn to move next, (2) all of the intervals chosen by I have rational endpoints, and (3) II has played in accordance with $\sigma$. Notice that the rationality requirement (2) combined with (3) ensures that there are only countably many such positions $p$.

Say that a point $a\in A$ is "out" at such a position $p$ if it is in the last interval $I$ that II played in $p$ but, no matter what rational subinterval $J$ of $I$ player I plays next, player II's response, using $\sigma$, will not contain $a$. [If $p$ is the initial position of the game, so nobody has played any interval yet, then interpret "the last interval that II played" as meaning $\mathbb R$.]

Claim 1: For each $p$ as above, the set of points $a$ that are out at $p$ is nowhere dense.
Proof: Suppose not, so there's an interval $K$ in which the out-at-$p$ points are dense. Since all out-at-$p$ points are in the last interval $I$ that player $II$ played in $p$, $K$ must be a sub-interval of $I$. Consider what happens if player I plays, as the next move after $p$, a rational sub-interval $J$ of $K$. Then player II, using $\sigma$ responds with a sub-interval of $J$, all of whose points are, by definition, not out at $p$. That contradicts the assumption that the out-at-$p$ points are dense in $K$. So Claim 1 is proved.

Claim 2: Every point $a$ in $A$ is out at some $p$.
Proof: Suppose $a$ were a counterexample. In particular, $a$ is not out at the initial position of the game, so player I can make an opening move $I_0$ such that II's reply $I_1$, using $\sigma$, contains $a$. Since $a$ is not out at $p=(I_0,I_1)$, player $I$ can make a move $I_2$ such that II's reply $I_3$ using $\sigma$ still contains $a$. Continuing in this fashion, we produce a play of the game such that $a$ is in all of the chosen intervals. So player I wins this play even though II used $\sigma$. That contradicts the assumption that $\sigma$ s a winning strategy for II. So Claim 2 is proved.

The two claims together show that $A$ is covered by countably many nowhere dense sets, namely the sets of out-at-$p$ points for the countably many positions $p$. So $A$ is meager.

Say $A\subset \omega^\omega$ (the latter representing the real numbers $R$). Then the game $G^{**}(A)$ is defined by players I and II playing natural numbers $s_0,s_1,s_2,..\in \omega$ - player I the even times and II the odd, I wins if the resulting $f:=(s_0,s_1,s_2..)\in \omega^\omega$ is in $A$ otherwise II wins (this game is essentially the same as the one u describe).

Say II has a winning strategy $\tau$, then $A$ being meager is seen like this:

For every $f\in A$ there must be some finite start sequence $u\prec f$ (with $u\in \omega^{<\omega}$) which is played according to player IIs winning strategy $\tau$ and after which $\tau$ enables player II to force that $f$ is not further followed in the game run (otherwise I would be able to win and $\tau$ would not be a winning startegy for II).

Define for each $u\in \omega^{<\omega}$ played by $\tau$ the set of all $f\in \omega^\omega$ that II can prevent after $u$: $$K_u:=\{f\in \omega^\omega| u\prec f\text{ and after } u \text{ II can force by } \tau \text{ to leave } f\}$$

Then because of what we said first $$A\subset\bigcup_{u\text{ by }\tau}K_u$$

That covering is countable since all $u\in\omega^{<\omega}$ and $\omega^{<\omega}$ is countable. The rest is to show that any such $K_u$ is nowhere dense (show that each $K_u$ is closed and contains no open subset).