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

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

____________________________________________________________________

Revised 4/4/2014. \copyright \ 2014 \text{ by Dan Ma}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s