# Difference between revisions of "Banach-Mazur game"

(Importing text file) |
m (AUTOMATIC EDIT (latexlist): Replaced 126 formulas out of 126 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.) |
||

(3 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

− | + | <!--This article has been texified automatically. Since there was no Nroff source code for this article, | |

+ | the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist | ||

+ | was used. | ||

+ | If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category. | ||

− | + | Out of 126 formulas, 126 were replaced by TEX code.--> | |

− | + | {{TEX|semi-auto}}{{TEX|done}} | |

+ | A game that appeared in the famous Scottish Book [[#References|[a11]]], [[#References|[a6]]], where its initial version was formulated as Problem 43 by the Polish mathematician S. Mazur: Given the space of real numbers $\mathbf{R}$ and a non-empty subset $E$ of it, two players $A$ and $B$ play a game in the following way: $A$ starts by choosing a non-empty interval $I_{0}$ of $\mathbf{R}$ and then $B$ responds by choosing a non-empty subinterval $I _ { 1 }$ of $I_{0}$. Then player $A$ in turn selects a non-empty interval $I _ { 2 } \subset I _ { 1 }$ and $B$ continues by taking a non-empty subinterval $I_3$ of $I_2$. This procedure is iterated infinitely many times. The resulting infinite sequence of nested intervals $\{ I _ { n } \} _ { n = 0 } ^ { \infty }$ is called a play. By definition, the player $A$ wins this play if the intersection $\cap _ { n = 0 } ^ { \infty } I _ {n}$ has a common point with $E$. Otherwise $B$ wins. Mazur had observed two facts: | ||

− | More than 20 years later, in 1957, J. Oxtoby [[#References|[a8]]] published a proof for the validity of Mazur's conjecture. Oxtoby considered a much more general setting. The game was played in a general [[Topological space|topological space]] | + | a) if the complement of $E$ in some interval of $\mathbf{R}$ is of the first Baire category in this interval (equivalently, if $E$ is residual in some interval of $\mathbf{R}$, cf. also [[Category of a set|Category of a set]]; [[Baire classes|Baire classes]]), then player $A$ has a winning strategy (see below for the definition); and |

+ | |||

+ | b) if $E$ itself is of the first Baire category in $\mathbf{R}$, then $B$ has a winning strategy. The question originally posed by Mazur in Problem 43 of the Scottish Book (with as prize a bottle of wine!) was whether the inverse implications in the above two assertions hold. On August 4, 1935, S. Banach wrote in the same book that "Mazur's conjecture is true" . The proof of this statement of Banach however has never been published. The game subsequently became known as the Banach–Mazur game. | ||

+ | |||

+ | More than 20 years later, in 1957, J. Oxtoby [[#References|[a8]]] published a proof for the validity of Mazur's conjecture. Oxtoby considered a much more general setting. The game was played in a general [[Topological space|topological space]] $X$ with $\emptyset \neq E \subset X$ and the two players $A$ and $B$ were choosing alternatively sets $W _ { 0 } \supset W _ { 1 } \supset \ldots$ from an a priori prescribed family of sets $\mathcal{W}$ which has the property that every element of $\mathcal{W}$ contains a non-empty open subset of $X$ and every non-empty open subset of $X$ contains an element of $\mathcal{W}$. As above, $A$ wins if $( \cap _ { n = 0 } ^ { \infty } W _ { n } ) \cap E \neq \emptyset$, otherwise $B$ wins. Oxtoby's theorem says that $B$ has a winning strategy if and only if $E$ is of the first Baire category in $X$; also, if $X$ is a [[Complete metric space|complete metric space]], then $A$ has a winning strategy exactly when $E$ is residual in some non-empty open subset of $X$. | ||

Later, the game was subjected to different generalizations and modifications. | Later, the game was subjected to different generalizations and modifications. | ||

==Generalizations.== | ==Generalizations.== | ||

− | Only the most popular modification of this game will be considered. It has turned out to be useful not only in set-theoretic topology, but also in the geometry of Banach spaces, non-linear analysis, number theory, descriptive set theory, well-posedness in optimization, etc. This modification is the following: Given a topological space | + | Only the most popular modification of this game will be considered. It has turned out to be useful not only in set-theoretic topology, but also in the geometry of Banach spaces, non-linear analysis, number theory, descriptive set theory, well-posedness in optimization, etc. This modification is the following: Given a topological space $X$, two players (usually called $\alpha$ and $\beta$) alternatively choose non-empty open sets $U _ { 1 } \supset V _ { 1 } \supset U _ { 2 } \supset V _ { 2 } \supset \ldots$ (in this sequence the $U _ { n }$ are the choices of $\beta$ and the $V _ { n }$ are the choices of $\alpha$; thus, it is player $\beta$ who starts this game). Player $\alpha$ wins the play $\{ U _ { n } , V _ { n } \} _ { n = 1 } ^ { \infty }$ if $\cap _ { n = 1 } ^ { \infty } U _ { n } = \cap _ { n = 1 } ^ { \infty } V _ { n } \neq \emptyset$, otherwise $\beta$ wins. To be completely consistent with the general scheme described above, one may think that $E = X$ and $\alpha$ starts by always choosing the whole space $X$. This game is often denoted by $\operatorname{BM} ( X )$. |

− | A strategy | + | A strategy $s$ for the player $\alpha$ is a mapping which assigns to every finite sequence $( U _ { 1 } \supset V _ { 1 } \supset \ldots \supset U _ { n } )$ of legal moves in $\operatorname{BM} ( X )$ a non-empty open subset $V _ { n }$ of $X$ included in the last move of $\beta$ (i.e. $V _ { n } \subset U _ { n }$). A stationary strategy (called also a tactics) for $\alpha$ is a strategy for this player which depends only on the last move of the opponent. A winning strategy (a stationary winning strategy) $s$ for $\alpha$ is a strategy such that $\alpha$ wins every play in which his/her moves are obtained by $s$. Similarly one defines the (winning) strategies for $\beta$. |

− | A topological space | + | A topological space $X$ is called weakly $\alpha$-favourable if $\alpha$ has a winning strategy in $\operatorname{BM} ( X )$, while it is termed $\alpha$-favourable if there is a stationary winning strategy for $\alpha$ in $\operatorname{BM} ( X )$. It can be derived from the work of Oxtoby [[#References|[a8]]] (see also [[#References|[a4]]], [[#References|[a7]]] and [[#References|[a9]]]) that the space $X$ is a [[Baire space|Baire space]] exactly when player $\beta$ does not have a winning strategy in $\operatorname{BM} ( X )$. Hence, every weakly $\alpha$-favourable space is a Baire space. In the class of metric spaces $X$, a metric space is weakly $\alpha$-favourable if and only if it contains a dense and completely metrizable subspace. One can use these two results to see that the Banach–Mazur game is "not determined" . I.e. it could happen for some space $X$ that neither $\alpha$ nor $\beta$ has a winning strategy. For instance, the Bernstein set $X$ in the real line (cf. also [[Non-measurable set|Non-measurable set]]) is a Baire space which does not contain a dense completely metrizable subspace (consequently $X$ does not admit a winning strategy for either $\alpha$ or $\beta$). |

− | The above characterization of weak | + | The above characterization of weak $\alpha$-favourability for metric spaces has been extended for some non-metrizable spaces in [[#References|[a10]]]. |

− | A characterization of | + | A characterization of $\alpha$-favourability of a given [[Completely-regular space|completely-regular space]] $X$ can be obtained by means of the space $C ( X )$ of all continuous and bounded real-valued functions on $X$ equipped with the usual sup-norm $\| f \| _ { \infty } : = \operatorname { sup } \{ | f ( x ) | : x \in X \}$. The following statement holds [[#References|[a5]]]: The space $X$ is weakly $\alpha$-favourable if and only if the set |

− | + | \begin{equation*} \{ f \in C ( X ) : f \ \text{attains its maximum in} \ X \} \end{equation*} | |

− | is residual in | + | is residual in $C ( X )$. In other words, $X$ is weakly $\alpha$-favourable if and only if almost-all (from the Baire category point of view) of the functions in $C ( X )$ attain their maximum in $X$. The rich interplay between $X$, $C ( X )$ and $\operatorname{BM} ( X )$ is excellently presented in [[#References|[a3]]]. |

− | The class of | + | The class of $\alpha$-favourable spaces (spaces which admit $\alpha$-winning tactics) is strictly narrower than the class of weakly $\alpha$-favourable spaces. G. Debs [[#References|[a2]]] has exhibited a completely-regular topological space $X$ which admits a winning strategy for $\alpha$ in $\operatorname{BM} ( X )$, but does not admit any $\alpha$-winning tactics in $\operatorname{BM} ( X )$. Under the name "espaces tamisables" , the $\alpha$-favourable spaces were introduced and studied also by G. Choquet [[#References|[a1]]]. |

− | [[#References|[a10]]] is an excellent survey paper about topological games (including | + | [[#References|[a10]]] is an excellent survey paper about topological games (including $\operatorname{BM} ( X )$). |

====References==== | ====References==== | ||

− | <table>< | + | <table> |

+ | <tr><td valign="top">[a1]</td> <td valign="top"> G. Choquet, "Une classe régulières d'espaces de Baire" ''C.R. Acad. Sci. Paris Sér. I'' , '''246''' (1958) pp. 218–220</td></tr> | ||

+ | <tr><td valign="top">[a2]</td> <td valign="top"> G. Debs, "Strategies gagnantes dans certain jeux topologique" ''Fundam. Math.'' , '''126''' (1985) pp. 93–105</td></tr> | ||

+ | <tr><td valign="top">[a3]</td> <td valign="top"> G. Debs, J. Saint-Raymond, "Topological games and optimization problems" ''Mathematika'' , '''41''' (1994) pp. 117–132</td></tr> | ||

+ | <tr><td valign="top">[a4]</td> <td valign="top"> M.R. Krom, "Infinite games and special Baire space extensions" ''Pacific J. Math.'' , '''55''' : 2 (1974) pp. 483–487</td></tr> | ||

+ | <tr><td valign="top">[a5]</td> <td valign="top"> P.S. Kenderov, J.P. Revalski, "The Banach–Mazur game and generic existence of solutions to optimization problems" ''Proc. Amer. Math. Soc.'' , '''118''' (1993) pp. 911–917</td> | ||

+ | </tr><tr><td valign="top">[a6]</td> <td valign="top"> "The Scottish Book: Mathematics from the Scottish Café" R.D. Mauldin (ed.) , Birkhäuser (1981)</td></tr> | ||

+ | <tr><td valign="top">[a7]</td> <td valign="top"> R.A. McCoy, "A Baire space extension" ''Proc. Amer. Math. Soc.'' , '''33''' (1972) pp. 199–202</td></tr> | ||

+ | <tr><td valign="top">[a8]</td> <td valign="top"> J. Oxtoby, "The Banach–Mazur game and the Banach category theorem" , ''Contributions to the Theory of Games III'' , ''Ann. of Math. Stud.'' , '''39''' , Princeton Univ. Press (1957) pp. 159–163</td></tr> | ||

+ | <tr><td valign="top">[a9]</td> <td valign="top"> J. Saint-Raymond, "Jeux topologiques et espaces de Namioka" ''Proc. Amer. Math. Soc.'' , '''87''' (1983) pp. 499–504 {{MR|}} {{ZBL|0511.54007}} </td></tr> | ||

+ | <tr><td valign="top">[a10]</td> <td valign="top"> R. Telgárski, "Topological games: On the fiftieth anniversary of the Banach–Mazur game" ''Rocky Mount. J. Math.'' , '''17''' (1987) pp. 227–276 [[ZBL|0619.90110}}</td></tr> | ||

+ | <tr><td valign="top">[a11]</td> <td valign="top"> S.M. Ulam, "The Scottish Book" , ''A LASL monograph'' , Los Alamos Sci. Lab. (1977) (Edition: Second)</td></tr> | ||

+ | </table> |

## Latest revision as of 17:01, 1 July 2020

A game that appeared in the famous Scottish Book [a11], [a6], where its initial version was formulated as Problem 43 by the Polish mathematician S. Mazur: Given the space of real numbers $\mathbf{R}$ and a non-empty subset $E$ of it, two players $A$ and $B$ play a game in the following way: $A$ starts by choosing a non-empty interval $I_{0}$ of $\mathbf{R}$ and then $B$ responds by choosing a non-empty subinterval $I _ { 1 }$ of $I_{0}$. Then player $A$ in turn selects a non-empty interval $I _ { 2 } \subset I _ { 1 }$ and $B$ continues by taking a non-empty subinterval $I_3$ of $I_2$. This procedure is iterated infinitely many times. The resulting infinite sequence of nested intervals $\{ I _ { n } \} _ { n = 0 } ^ { \infty }$ is called a play. By definition, the player $A$ wins this play if the intersection $\cap _ { n = 0 } ^ { \infty } I _ {n}$ has a common point with $E$. Otherwise $B$ wins. Mazur had observed two facts:

a) if the complement of $E$ in some interval of $\mathbf{R}$ is of the first Baire category in this interval (equivalently, if $E$ is residual in some interval of $\mathbf{R}$, cf. also Category of a set; Baire classes), then player $A$ has a winning strategy (see below for the definition); and

b) if $E$ itself is of the first Baire category in $\mathbf{R}$, then $B$ has a winning strategy. The question originally posed by Mazur in Problem 43 of the Scottish Book (with as prize a bottle of wine!) was whether the inverse implications in the above two assertions hold. On August 4, 1935, S. Banach wrote in the same book that "Mazur's conjecture is true" . The proof of this statement of Banach however has never been published. The game subsequently became known as the Banach–Mazur game.

More than 20 years later, in 1957, J. Oxtoby [a8] published a proof for the validity of Mazur's conjecture. Oxtoby considered a much more general setting. The game was played in a general topological space $X$ with $\emptyset \neq E \subset X$ and the two players $A$ and $B$ were choosing alternatively sets $W _ { 0 } \supset W _ { 1 } \supset \ldots$ from an a priori prescribed family of sets $\mathcal{W}$ which has the property that every element of $\mathcal{W}$ contains a non-empty open subset of $X$ and every non-empty open subset of $X$ contains an element of $\mathcal{W}$. As above, $A$ wins if $( \cap _ { n = 0 } ^ { \infty } W _ { n } ) \cap E \neq \emptyset$, otherwise $B$ wins. Oxtoby's theorem says that $B$ has a winning strategy if and only if $E$ is of the first Baire category in $X$; also, if $X$ is a complete metric space, then $A$ has a winning strategy exactly when $E$ is residual in some non-empty open subset of $X$.

Later, the game was subjected to different generalizations and modifications.

## Generalizations.

Only the most popular modification of this game will be considered. It has turned out to be useful not only in set-theoretic topology, but also in the geometry of Banach spaces, non-linear analysis, number theory, descriptive set theory, well-posedness in optimization, etc. This modification is the following: Given a topological space $X$, two players (usually called $\alpha$ and $\beta$) alternatively choose non-empty open sets $U _ { 1 } \supset V _ { 1 } \supset U _ { 2 } \supset V _ { 2 } \supset \ldots$ (in this sequence the $U _ { n }$ are the choices of $\beta$ and the $V _ { n }$ are the choices of $\alpha$; thus, it is player $\beta$ who starts this game). Player $\alpha$ wins the play $\{ U _ { n } , V _ { n } \} _ { n = 1 } ^ { \infty }$ if $\cap _ { n = 1 } ^ { \infty } U _ { n } = \cap _ { n = 1 } ^ { \infty } V _ { n } \neq \emptyset$, otherwise $\beta$ wins. To be completely consistent with the general scheme described above, one may think that $E = X$ and $\alpha$ starts by always choosing the whole space $X$. This game is often denoted by $\operatorname{BM} ( X )$.

A strategy $s$ for the player $\alpha$ is a mapping which assigns to every finite sequence $( U _ { 1 } \supset V _ { 1 } \supset \ldots \supset U _ { n } )$ of legal moves in $\operatorname{BM} ( X )$ a non-empty open subset $V _ { n }$ of $X$ included in the last move of $\beta$ (i.e. $V _ { n } \subset U _ { n }$). A stationary strategy (called also a tactics) for $\alpha$ is a strategy for this player which depends only on the last move of the opponent. A winning strategy (a stationary winning strategy) $s$ for $\alpha$ is a strategy such that $\alpha$ wins every play in which his/her moves are obtained by $s$. Similarly one defines the (winning) strategies for $\beta$.

A topological space $X$ is called weakly $\alpha$-favourable if $\alpha$ has a winning strategy in $\operatorname{BM} ( X )$, while it is termed $\alpha$-favourable if there is a stationary winning strategy for $\alpha$ in $\operatorname{BM} ( X )$. It can be derived from the work of Oxtoby [a8] (see also [a4], [a7] and [a9]) that the space $X$ is a Baire space exactly when player $\beta$ does not have a winning strategy in $\operatorname{BM} ( X )$. Hence, every weakly $\alpha$-favourable space is a Baire space. In the class of metric spaces $X$, a metric space is weakly $\alpha$-favourable if and only if it contains a dense and completely metrizable subspace. One can use these two results to see that the Banach–Mazur game is "not determined" . I.e. it could happen for some space $X$ that neither $\alpha$ nor $\beta$ has a winning strategy. For instance, the Bernstein set $X$ in the real line (cf. also Non-measurable set) is a Baire space which does not contain a dense completely metrizable subspace (consequently $X$ does not admit a winning strategy for either $\alpha$ or $\beta$).

The above characterization of weak $\alpha$-favourability for metric spaces has been extended for some non-metrizable spaces in [a10].

A characterization of $\alpha$-favourability of a given completely-regular space $X$ can be obtained by means of the space $C ( X )$ of all continuous and bounded real-valued functions on $X$ equipped with the usual sup-norm $\| f \| _ { \infty } : = \operatorname { sup } \{ | f ( x ) | : x \in X \}$. The following statement holds [a5]: The space $X$ is weakly $\alpha$-favourable if and only if the set

\begin{equation*} \{ f \in C ( X ) : f \ \text{attains its maximum in} \ X \} \end{equation*}

is residual in $C ( X )$. In other words, $X$ is weakly $\alpha$-favourable if and only if almost-all (from the Baire category point of view) of the functions in $C ( X )$ attain their maximum in $X$. The rich interplay between $X$, $C ( X )$ and $\operatorname{BM} ( X )$ is excellently presented in [a3].

The class of $\alpha$-favourable spaces (spaces which admit $\alpha$-winning tactics) is strictly narrower than the class of weakly $\alpha$-favourable spaces. G. Debs [a2] has exhibited a completely-regular topological space $X$ which admits a winning strategy for $\alpha$ in $\operatorname{BM} ( X )$, but does not admit any $\alpha$-winning tactics in $\operatorname{BM} ( X )$. Under the name "espaces tamisables" , the $\alpha$-favourable spaces were introduced and studied also by G. Choquet [a1].

[a10] is an excellent survey paper about topological games (including $\operatorname{BM} ( X )$).

#### References

[a1] | G. Choquet, "Une classe régulières d'espaces de Baire" C.R. Acad. Sci. Paris Sér. I , 246 (1958) pp. 218–220 |

[a2] | G. Debs, "Strategies gagnantes dans certain jeux topologique" Fundam. Math. , 126 (1985) pp. 93–105 |

[a3] | G. Debs, J. Saint-Raymond, "Topological games and optimization problems" Mathematika , 41 (1994) pp. 117–132 |

[a4] | M.R. Krom, "Infinite games and special Baire space extensions" Pacific J. Math. , 55 : 2 (1974) pp. 483–487 |

[a5] | P.S. Kenderov, J.P. Revalski, "The Banach–Mazur game and generic existence of solutions to optimization problems" Proc. Amer. Math. Soc. , 118 (1993) pp. 911–917 |

[a6] | "The Scottish Book: Mathematics from the Scottish Café" R.D. Mauldin (ed.) , Birkhäuser (1981) |

[a7] | R.A. McCoy, "A Baire space extension" Proc. Amer. Math. Soc. , 33 (1972) pp. 199–202 |

[a8] | J. Oxtoby, "The Banach–Mazur game and the Banach category theorem" , Contributions to the Theory of Games III , Ann. of Math. Stud. , 39 , Princeton Univ. Press (1957) pp. 159–163 |

[a9] | J. Saint-Raymond, "Jeux topologiques et espaces de Namioka" Proc. Amer. Math. Soc. , 87 (1983) pp. 499–504 Zbl 0511.54007 |

[a10] | R. Telgárski, "Topological games: On the fiftieth anniversary of the Banach–Mazur game" Rocky Mount. J. Math. , 17 (1987) pp. 227–276 [[ZBL|0619.90110}} |

[a11] | S.M. Ulam, "The Scottish Book" , A LASL monograph , Los Alamos Sci. Lab. (1977) (Edition: Second) |

**How to Cite This Entry:**

Banach-Mazur game.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Banach-Mazur_game&oldid=15639