The Banach-Mazur Game

A topological space $X$ is said to be a Baire space if for every countable family $\left\{U_0,U_1,U_2,\cdots \right\}$ of open and dense subsets of $X$ , the intersection $\bigcap \limits_{n=0}^\infty U_n$ is dense in $X$ (equivalently if every nonempty open subset of $X$ is of second category in $X$ ). By the Baire category theorem, every complete metric space is a Baire space. The Baire property (i.e. being a Baire space) can be characterized using the Banach-Mazur game, which is the focus of this post.

Baire category theorem and Baire spaces are discussed in this previous post. We define the Banach-Mazur game and show how this game is related to the Baire property. We also define some completeness properties stronger than the Baire property using this game. For a survey on Baire spaces, see [4]. For more information about the Banach-Mazur game, see [1]. Good references for basic topological terms are [3] and [5]. All topological spaces are assumed to be at least Hausdorff.

__________________________________________________________________________

The Banach-Mazur Game

The Banach-Mazur game is a two-person game played on a topological space. Let $X$ be a space. There are two players, $\alpha$ and $\beta$ . They take turn choosing nested decreasing nonempty open subsets of $X$ as follows. The player $\beta$ goes first by choosing a nonempty open subset $U_0$ of $X$ . The player $\alpha$ then chooses a nonempty open subset $V_0 \subset U_0$ . At the nth play where $n \ge 1$ , $\beta$ chooses an open set $U_n \subset V_{n-1}$ and $\alpha$ chooses an open set $V_n \subset U_n$ . The player $\alpha$ wins if $\bigcap \limits_{n=0}^\infty V_n \ne \varnothing$ . Otherwise the player $\beta$ wins.

If the players in the game described above make the moves $U_0,V_0,U_1,V_1,U_2,V_2,\cdots$ , then this sequence of open sets is said to be a play of the game.

The Banach-Mazur game, as described above, is denoted by $BM(X,\beta)$ . In this game, the player $\beta$ makes the first move. If we modify the game by letting $\alpha$ making the first move, we denote this new game by $BM(X,\alpha)$ . In either version, the goal of player $\beta$ is to reach an empty intersection of the chosen open sets while player $\alpha$ wants the chosen open sets to have nonempty intersection.

A Remark About Topological Games

Before relating the Banach-Mazur game to Baire spaces, we give a remark about topological games. For any two-person game played on a topological space, we are interested in the following question.

Can a player, by making his/her moves judiciously, insure that he/she will always win no matter what moves the other player makes?

If the answer to this question is yes, then the player in question is said to have a winning strategy. For an illustration, consider a space $X$ that is of first category in itself, so that $X=\bigcup \limits_{n=0}^\infty X_n$ where each $X_n$ is nowhere dense in $X$ . Then player $\beta$ has a winning strategy in the Banach-Mazur game $BM(X,\beta)$ . The player $\beta$ always wins the game by making his/her nth play $U_n \subset V_{n-1} - \overline{X_n}$ .

In general, a strategy for a player in a game is a rule that specifies what moves he/she will make in every possible situation. In other words, a strategy for a player is a function whose domain is the set of all partial plays of the game, and this function tells the player what the next move should be. A winning strategy for a player is a strategy such that this player always wins if that player makes his/her moves using this strategy. A strategy for a player in a game is not a winning strategy if of all the plays of the game resulting from using this strategy, there is at least one specific play of the game resulting in a win for the other player.

__________________________________________________________________________

Strategies in the Banach-Mazur Game

With the above discussion in mind, let us discuss the strategies in the Banach-Mazur game. We show that the strategies in this game code a great amount of information about the topological space in which the game is played.

First we discuss strategies for player $\beta$ in the game $BM(X,\beta)$ . A strategy for player $\beta$ is a function $\sigma$ such that $U_0=\sigma(\varnothing)$ (the first move) and for each partial play of the game ( $n \ge 1$ )

$\displaystyle (*) \ \ \ \ \ \ U_0,V_0,U_1,V_1,\cdots,U_{n-1},V_{n-1}$ ,

$U_n=\sigma(U_0,V_0,U_1,V_1,\cdots,U_{n-1},V_{n-1})$ is a nonempty open set such that $U_n \subset V_{n-1}$ . If player $\beta$ makes all his/her moves using the strategy $\sigma$ , then the strategy $\sigma$ for player $\beta$ contains information on all moves of $\beta$ . We adopt the convention that a strategy for a player in a game depends only on the moves of the other player. Thus for the partial play of the Banach-Mazur game denoted by $(*)$ above, $U_n=\sigma(V_0,V_1,\cdots,V_{n-1})$ .

If $\sigma$ is a winning strategy for player $\beta$ in the game $BM(X,\beta)$ , then using this strategy will always result in a win for $\beta$ . On the other hand, if $\sigma$ is a not a winning strategy for player $\beta$ in the game $BM(X,\beta)$ , then there exists a specific play of the Banach-Mazur game

$\displaystyle . \ \ \ \ \ \ U_0,V_0,U_1,V_1,\cdots,U_{n-1},V_{n-1},\cdots$

such that $U_0=\sigma(\varnothing)$ , and for each $n \ge 1$ , $U_n=\sigma(V_0,\cdots,V_{n-1})$ and player $\alpha$ wins in this play of the game, that is, $\bigcap \limits_{n=0}^\infty V_n \ne \varnothing$ .

In the game $BM(X,\alpha)$ (player $\alpha$ making the first move), a strategy for player $\beta$ is a function $\gamma$ such that for each partial play of the game

$\displaystyle (**) \ \ \ \ \ V_0,U_1,V_1,\cdots,U_{n-1},V_{n-1}$ ,

$U_n=\gamma(V_0,V_1,\cdots,V_{n-1})$ is a nonempty open set such that $U_n \subset V_{n-1}$ .

We now present a lemma that helps translate game information into topological information.

Lemma 1
Let $X$ be a space. Let $O \subset X$ be a nonempty open set. Let $\tau$ be the set of all nonempty open subsets of $O$ . Let $f: \tau \longrightarrow \tau$ be a function such that for each $V \in \tau$ , $f(V) \subset V$ . Then there exists a disjoint collection $\mathcal{U}$ consisting of elements of $f(\tau)$ such that $\bigcup \mathcal{U}$ is dense in $O$ .

Proof
This is an argument using Zorn’s lemma. If the open set $O$ in the hypothesis has only one point, then the conclusion of the lemma holds. So assume that $O$ has at least two points.

Let $\mathcal{P}$ be the set consisting of all collections $\mathcal{F}$ such that each $\mathcal{F}$ is a disjoint collection consisting of elements of $f(\tau)$ . First $\mathcal{P} \ne \varnothing$ . To see this, let $V$ and $W$ be two disjoint open sets such that $V \subset O$ and $W \subset O$ . This is possible since $O$ has at least two points. Let $\mathcal{F^*}=\left\{ f(V),f(W)\right\}$ . Then we have $\mathcal{F^*} \in \mathcal{P}$ . Order $\mathcal{P}$ by set inclusion. It is straightforward to show that $(\mathcal{P}, \subset)$ is a partially ordered set.

Let $\mathcal{T} \subset \mathcal{P}$ be a chain (a totally ordered set). We wish to show that $\mathcal{T}$ has an upper bound in $\mathcal{P}$ . The candidate for an upper bound is $\bigcup \mathcal{T}$ since it is clear that for each $\mathcal{F} \in \mathcal{T}$ , $\mathcal{F} \subset \bigcup \mathcal{T}$ . We only need to show $\bigcup \mathcal{T} \in \mathcal{P}$ . To this end, we need to show that any two elements of $\bigcup \mathcal{T}$ are disjoint open sets.

Note that elements of $\bigcup \mathcal{T}$ are elements of $f(\tau)$ . Let $T_1,T_2 \in \bigcup \mathcal{T}$ . Then $T_1 \in \mathcal{F}_1$ and $T_2 \in \mathcal{F}_2$ for some $\mathcal{F}_1 \in \mathcal{T}$ and $\mathcal{F}_2 \in \mathcal{T}$ . Since $\mathcal{T}$ is a chain, either $\mathcal{F}_1 \subset \mathcal{F}_2$ or $\mathcal{F}_2 \subset \mathcal{F}_1$ . This means that $T_1$ and $T_2$ belong to the same disjoing collection in $\mathcal{T}$ . So they are disjoint open sets that are members of $f(\tau)$ .

By Zorn’s lemma, $(\mathcal{P}, \subset)$ has a maximal element $\mathcal{U}$ , which is a desired disjoint collection of sets in $f(\tau)$ . Since $\mathcal{U}$ is maximal with respect to $\subset$ , $\bigcup \mathcal{U}$ is dense in $O$ . $\blacksquare$

__________________________________________________________________________

Characterizing Baire Spaces using the Banach-Mazur Game

Lemma 1 is the linkage between the Baire property and the strategies in the Banach-Mazur game. The thickness in Baire spaces and spaces of second category allow us to extract a losing play in any strategy for player $\beta$ . The proofs for both Theorem 1 and Theorem 2 are very similar (after adjusting for differences in who makes the first move). Thus we only present the proof for Theorem 1.

Theorem 1
The space $X$ is a Baire space if and only if player $\beta$ has no winning strategy in the game $BM(X,\beta)$ .

Proof
$\Longleftarrow$ Suppose that $X$ is not a Baire space. We define a winning strategy in the game $BM(X,\beta)$ for player $\beta$ . The space $X$ not being a Baire space implies that there is some nonempty open set $U_0 \subset X$ such that $U_0$ is of first category in $X$ . Thus $U_0=\bigcup \limits_{n=1}^\infty F_n$ where each $F_n$ is nowhere dense in $X$ .

We now define a winning strategy for $\beta$ . Let $U_0$ be the first move of $\beta$ . For each $n \ge 1$ , let player $\beta$ make his/her move by letting $U_n \subset V_{n-1} - \overline{F_n}$ if $V_{n-1}$ is the last move by $\alpha$ . It is clear that whenever $\beta$ chooses his/her moves in this way, the intersection of the open sets has to be empty.

$\Longrightarrow$ Suppose that $X$ is a Baire space. Let $\sigma$ be a strategy for the player $\beta$ . We show that $\sigma$ cannot be a winning strategy for $\beta$ .

Let $U_0=\sigma(\varnothing)$ be the first move for $\beta$ . For each open $V_0 \subset U_0$ , $\sigma(V_0) \subset V_0$ . Apply Lemma 1 to obtain a disjoint collection $\mathcal{U}_0$ consisting of open sets of the form $\sigma(V_0)$ such that $\bigcup \mathcal{U}_0$ is dense in $U_0$ .

For each $W=\sigma(V_0) \in \mathcal{U}_0$ , we have $\sigma(V_0,V_1) \subset V_1$ for all open $V_1 \subset W$ . So the function $\sigma(V_0,\cdot)$ is like the function $f$ in Lemma 1. We can then apply Lemma 1 to obtain a disjoint collection $\mathcal{U}_1(W)$ consisting of open sets of the form $\sigma(V_0,V_1)$ such that $\bigcup \mathcal{U}_1(W)$ is dense in $W$ . Then let $\mathcal{U}_1=\bigcup_{W \in \mathcal{U}_0} \mathcal{U}_1(W)$ . Based on how $\mathcal{U}_1(W)$ are obtained, it follows that $\bigcup \mathcal{U}_1$ is dense in $U_0$ .

Continue the inductive process in the same manner, we can obtain, for each $n \ge 1$ , a disjoint collection $\mathcal{U}_n$ consisting of open sets of the form $\sigma(V_0,\dots,V_{n-1})$ (these are moves made by $\beta$ using the strategy $\sigma$ ) such that $\bigcup \mathcal{U}_n$ is dense in $U_0$ .

For each $n$ , let $O_n=\bigcup \mathcal{U}_n$ . Each $O_n$ is dense open in $U_0$ . Since $X$ is a Baire space, every nonempty open subset of $X$ is of second category in $X$ (including $U_0$ ). Thus $\bigcap \limits_{n=0}^\infty O_n \ne \varnothing$ . From this nonempty intersection, we can extract a play of the game such that the open sets in this play of the game have one point in common (i.e. player $\alpha$ wins). We can extract the play of the game because the collection $\mathcal{U}_n$ are disjoint. Thus the strategy $\sigma$ is not a winning strategy for $\beta$ . This completes the proof of Theorem 1. $\blacksquare$

Theorem 2
The space $X$ is of second category in itself if and only if player $\beta$ has no winning strategy in the game $BM(X,\alpha)$ .

__________________________________________________________________________

Some Completeness Properties

Theorem 1 shows that a Baire space is one in which the player $\beta$ has no winning strategy in the Banach-Mazur game (the version in which $\beta$ makes the first move). In such a space, no matter what strategy player $\beta$ wants to use, it can be foiled by player $\alpha$ by producing one specific play in which $\beta$ loses. We now consider spaces in which player $\alpha$ has a winning strategy. A space $X$ is said to be a weakly $\alpha$ -favorable if player $\alpha$ has a winning strategy in the game $BM(X,\beta)$ . If $\alpha$ always wins, then $\beta$ has no winning strategy. Thus the property of being a weakly $\alpha$ -favorable space is stronger than the Baire property.

In any complete metric space, the player $\alpha$ always has a winning strategy. The same idea used in proving the Baire category theorem can be used to establish this fact. By playing the game in a complete metric space, player $\alpha$ can ensure a win by making sure that the closure of his/her moves have diameters converge to zero (and the closure of his/her moves are subsets of the previous moves).

Based on Theorem 1, any Baire space is a space in which player $\beta$ of the Banach-Mazur game has no winning strategy. Any Baire space that is not weakly $\alpha$ -favorable is a space in which both players of the Banach-Mazur game have no winning strategy (i.e. the game is undecidable). Any subset of the real line $\mathbb{R}$ that is a Bernstein set is such a space. A subset $B$ of the real line is said to be a Bernstein set if $B$ and its complement intersect every uncountable closed subset of the real line. Bernstein sets are discussed here.

Suppose $\theta$ is a strategy for $\alpha$ in the game $BM(X,\beta)$ . If at each step, the strategy $\theta$ can provide a move based only on the other player’s last move, it is said to be a stationary strategy. For example, in the partial play $U_0,V_0,\cdots,U_{n-1},V_{n-1},U_n$ , the strategy $\theta$ can determine the next move for $\alpha$ by only knowing the last move of $\beta$ , i.e., $V_n=\theta(U_n)$ . A space $X$ is said to be $\alpha$ -favorable if player $\alpha$ has a stationary winning strategy in the game $BM(X,\beta)$ . Clearly, any $\alpha$ -favorable spaces are weakly $\alpha$ -favorable spaces. However, there are spaces in which player $\alpha$ has a winning strategy in the Banach-Mazur game and yet has no stationary winning strategy (see [2]). Stationary winning strategy for $\alpha$ is also called $\alpha$ -winning tactic (see [1]).

Reference

Choquet, G., Lectures on analysis, Vol I, Benjamin, New York and Amsterdam, 1969.
Deb, G., Stategies gagnantes dans certains jeux topologiques, Fund. Math. 126 (1985), 93-105.
Engelking, R., General Topology, Revised and Completed edition, 1989, Heldermann Verlag, Berlin.
Haworth, R. C., McCoy, R. A., Baire Spaces, Dissertations Math., 141 (1977), 1 – 73.
Willard, S., General Topology, 1970, Addison-Wesley Publishing Company.

____________________________________________________________________

Dan Ma's Topology Blog

Expository Articles In General Topology

The Banach-Mazur Game

Like this:

Related

Leave a Reply Cancel reply