5
$\begingroup$

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...!!!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dave L. Renfro May 21 '14 at 14:02
  • $\begingroup$ 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. $\endgroup$ – FWE Aug 22 '14 at 14:33
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.