Banach–Mazur game
Banach–Mazur game
In general topology, set theory and game-theory, a Banach–Mazur game is a topological-game played by two players, trying to pin down elements in a set (space). The concept of a Banach–Mazur game is closely related to the concept of Baire spaces. This game was the first infinite positional-game of perfect-information to be studied. It was introduced by Stanisław Mazur as problem 43 in the Scottish book, and Mazur's questions about it were answered by Banach.
Definition Let <math>Y</math> be a non-empty topological space, <math>X</math> a fixed subset of <math>Y</math> and <math>\mathcal{W}</math> a family of subsets of <math>Y</math> that have the following properties:
- Each member of <math>\mathcal{W}</math> has non-empty interior.
- Each non-empty open subset of <math>Y</math> contains a member of <math>\mathcal{W}</math>.
Players, <math>P_1</math> and <math>P_2</math> alternately choose elements from <math>\mathcal{W}</math> to form a sequence <math>W_0 \supseteq W_1 \supseteq \cdots.</math>
<math>P_1</math> wins if and only if
:<math>X \cap \left (\bigcap_{n<\omega} W_n \right ) \neq \emptyset.</math> Otherwise, <math>P_2</math> wins. This is called a general Banach–Mazur game and denoted by <math>MB(X,Y, \mathcal{W}).</math>
Properties <math>P_2</math> has a winning strategy if and only if <math>X</math> is of the first category* in <math>Y</math> (a set is of the first category or meagre if it is the countable union of nowhere-dense sets). * If <math>Y</math> is a complete metric space, <math>P_1</math> has a winning strategy if and only if <math>X</math> is comeager in some non-empty open subset of <math>Y.</math> * If <math>X</math> has the Baire property in <math>Y</math>, then <math>MB(X,Y,\mathcal{W})</math> is determined. * The siftable and strongly-siftable spaces introduced by Choquet can be defined in terms of stationary strategies in suitable modifications of the game. Let <math>BM(X)</math> denote a modification of <math>MB(X,Y,\mathcal{W})</math> where <math>X=Y, \mathcal{W}</math> is the family of all non-empty open sets in <math>X</math> and <math>P_2</math> wins a play <math>(W_0, W_1, \cdots)</math> if and only if ::<math>\bigcap_{n<\omega} W_n \neq \emptyset.</math> :Then <math>X</math> is siftable if and only if <math>P_2</math> has a stationary winning strategy in <math>BM(X).</math>
- A Markov winning strategy for <math>P_2</math> in <math>BM(X)</math> can be reduced to a stationary winning strategy. Furthermore, if <math>P_2</math> has a winning strategy in <math>BM(X)</math>, then <math>P_2</math> has a winning strategy depending only on two preceding moves. It is still an unsettled question whether a winning strategy for <math>P_2</math> can be reduced to a winning strategy that depends only on the last two moves of <math>P_1</math>.
- <math>X</math> is called weakly <math>\alpha</math>-favorable if <math>P_2</math> has a winning strategy in <math>BM(X)</math>. Then, <math>X</math> is a Baire space if and only if <math>P_1</math> has no winning strategy in <math>BM(X)</math>. It follows that each weakly <math>\alpha</math>-favorable space is a Baire space.
Many other modifications and specializations of the basic game have been proposed: for a thorough account of these, refer to [1987].
The most common special case arises when <math>Y = J = [0, 1]</math> and <math>\mathcal{W}</math> consist of all closed intervals in the unit interval. Then <math>P_1</math> wins if and only if <math>X \cap (\cap_{n<\omega} J_n) \neq \emptyset</math> and <math>P_2</math> wins if and only if <math>X\cap (\cap_{n<\omega} J_n) = \emptyset</math>. This game is denoted by <math>MB(X, J).</math>
A simple proof: winning strategies It is natural to ask for what sets <math>X</math> does <math>P_2</math> have a winning strategy in <math>MB(X,Y,\mathcal W)</math>. Clearly, if <math>X</math> is empty, <math>P_2</math> has a winning strategy, therefore the question can be informally rephrased as how "small" (respectively, "big") does <math>X</math> (respectively, the complement of <math>X</math> in <math>Y</math>) have to be to ensure that <math>P_2</math> has a winning strategy. The following result gives a flavor of how the proofs used to derive the properties in the previous section work:
:Proposition. <math>P_2</math> has a winning strategy in <math>MB(X,Y,\mathcal W)</math> if <math>X</math> is countable, <math>Y</math> is T1, and <math>Y</math> has no isolated points.
:Proof. Index the elements of X as a sequence: <math>x_1, x_2, \cdots.</math> Suppose <math>P_1</math> has chosen <math>W_1,</math> if <math>U_1</math> is the non-empty interior of <math>W_1</math> then <math>U_1 \setminus \{x_1\}</math> is a non-empty open set in <math>Y,</math> so <math>P_2</math> can choose <math>\mathcal{W} \ni W_2 \subset U_1 \setminus \{x_1\}.</math> Then <math>P_1</math> chooses <math>W_3 \subset W_2</math> and, in a similar fashion, <math>P_2</math> can choose <math>W_4 \subset W_3</math> that excludes <math>x_2</math>. Continuing in this way, each point <math>x_n</math> will be excluded by the set <math>W_{2n},</math> so that the intersection of all <math>W_n</math> will not intersect <math>X</math>.
The assumptions on <math>Y</math> are key to the proof: for instance, if <math>Y=\{a,b,c\}</math> is equipped with the discrete topology and <math>\mathcal{W}</math> consists of all non-empty subsets of <math>Y</math>, then <math>P_2</math> has no winning strategy if <math>X=\{a\}</math> (as a matter of fact, her opponent has a winning strategy). Similar effects happen if <math>Y</math> is equipped with indiscrete topology and <math>\mathcal{W}=\{Y\}.</math>
A stronger result relates <math>X</math> to first-order sets.
:Proposition. <math>P_2</math> has a winning strategy in <math>MB(X,Y,\mathcal W)</math> if and only if <math>X</math> is meagre.
This does not imply that <math>P_1</math> has a winning strategy if <math>X</math> is not meagre. In fact, if <math>Y</math> is a complete metric space, then <math>P_1</math> has a winning strategy if and only if there is some <math>W_i \in \mathcal{W}</math> such that <math>X \cap W_i</math> is a comeagre subset of <math>W_i.</math> It may be the case that neither player has a winning strategy: let <math>Y</math> be the unit interval and <math>\mathcal{W}</math> be the family of closed intervals in the unit interval. The game is determined if the target set has the property-of-baire, i.e. if it differs from an open set by a meagre set (but the converse is not true). Assuming the axiom of choice, there are subsets of the unit interval for which the Banach–Mazur game is not determined.