Namespaces
Variants
Actions

Difference between revisions of "Banach-Mazur game"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (moved Banach–Mazur game to Banach-Mazur game: ascii title)
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.)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300401.png" /> and a non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300402.png" /> of it, two players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300403.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300404.png" /> play a game in the following way: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300405.png" /> starts by choosing a non-empty interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300406.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300407.png" /> and then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300408.png" /> responds by choosing a non-empty subinterval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b1300409.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004010.png" />. Then player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004011.png" /> in turn selects a non-empty interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004013.png" /> continues by taking a non-empty subinterval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004014.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004015.png" />. This procedure is iterated infinitely many times. The resulting infinite sequence of nested intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004016.png" /> is called a play. By definition, the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004017.png" /> wins this play if the intersection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004018.png" /> has a common point with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004019.png" />. Otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004020.png" /> wins. Mazur had observed two facts:
+
<!--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.
  
a) if the complement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004021.png" /> in some interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004022.png" /> is of the first Baire category in this interval (equivalently, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004023.png" /> is residual in some interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004024.png" />, cf. also [[Category of a set|Category of a set]]; [[Baire classes|Baire classes]]), then player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004025.png" /> has a winning strategy (see below for the definition); and
+
Out of 126 formulas, 126 were replaced by TEX code.-->
  
b) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004026.png" /> itself is of the first Baire category in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004027.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004028.png" /> 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.
+
{{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]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004029.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004030.png" /> and the two players <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004032.png" /> were choosing alternatively sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004033.png" /> from an a priori prescribed family of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004034.png" /> which has the property that every element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004035.png" /> contains a non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004036.png" /> and every non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004037.png" /> contains an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004038.png" />. As above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004039.png" /> wins if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004040.png" />, otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004041.png" /> wins. Oxtoby's theorem says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004042.png" /> has a winning strategy if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004043.png" /> is of the first Baire category in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004044.png" />; also, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004045.png" /> is a [[Complete metric space|complete metric space]], then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004046.png" /> has a winning strategy exactly when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004047.png" /> is residual in some non-empty open subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004048.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004049.png" />, two players (usually called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004051.png" />) alternatively choose non-empty open sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004052.png" /> (in this sequence the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004053.png" /> are the choices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004054.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004055.png" /> are the choices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004056.png" />; thus, it is player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004057.png" /> who starts this game). Player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004058.png" /> wins the play <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004059.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004060.png" />, otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004061.png" /> wins. To be completely consistent with the general scheme described above, one may think that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004062.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004063.png" /> starts by always choosing the whole space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004064.png" />. This game is often denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004065.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004066.png" /> for the player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004067.png" /> is a mapping which assigns to every finite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004068.png" /> of legal moves in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004069.png" /> a non-empty open subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004070.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004071.png" /> included in the last move of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004072.png" /> (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004073.png" />). A stationary strategy (called also a tactics) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004074.png" /> is a strategy for this player which depends only on the last move of the opponent. A winning strategy (a stationary winning strategy) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004075.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004076.png" /> is a strategy such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004077.png" /> wins every play in which his/her moves are obtained by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004078.png" />. Similarly one defines the (winning) strategies for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004079.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004080.png" /> is called weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004082.png" />-favourable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004083.png" /> has a winning strategy in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004084.png" />, while it is termed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004086.png" />-favourable if there is a stationary winning strategy for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004087.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004088.png" />. It can be derived from the work of Oxtoby [[#References|[a8]]] (see also [[#References|[a4]]], [[#References|[a7]]] and [[#References|[a9]]]) that the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004089.png" /> is a [[Baire space|Baire space]] exactly when player <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004090.png" /> does not have a winning strategy in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004091.png" />. Hence, every weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004092.png" />-favourable space is a Baire space. In the class of metric spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004093.png" />, a metric space is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004094.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004095.png" /> that neither <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004096.png" /> nor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004097.png" /> has a winning strategy. For instance, the Bernstein set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004098.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b13004099.png" /> does not admit a winning strategy for either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040100.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040101.png" />).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040102.png" />-favourability for metric spaces has been extended for some non-metrizable spaces in [[#References|[a10]]].
+
The above characterization of weak $\alpha$-favourability for metric spaces has been extended for some non-metrizable spaces in [[#References|[a10]]].
  
A characterization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040103.png" />-favourability of a given [[Completely-regular space|completely-regular space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040104.png" /> can be obtained by means of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040105.png" /> of all continuous and bounded real-valued functions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040106.png" /> equipped with the usual sup-norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040107.png" />. The following statement holds [[#References|[a5]]]: The space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040108.png" /> is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040109.png" />-favourable if and only if the set
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040110.png" /></td> </tr></table>
+
\begin{equation*} \{ f \in C ( X ) : f \ \text{attains its maximum in} \ X \} \end{equation*}
  
is residual in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040111.png" />. In other words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040112.png" /> is weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040113.png" />-favourable if and only if almost-all (from the Baire category point of view) of the functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040114.png" /> attain their maximum in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040115.png" />. The rich interplay between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040117.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040118.png" /> is excellently presented in [[#References|[a3]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040119.png" />-favourable spaces (spaces which admit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040120.png" />-winning tactics) is strictly narrower than the class of weakly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040121.png" />-favourable spaces. G. Debs [[#References|[a2]]] has exhibited a completely-regular topological space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040122.png" /> which admits a winning strategy for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040123.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040124.png" />, but does not admit any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040125.png" />-winning tactics in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040126.png" />. Under the name  "espaces tamisables" , the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040127.png" />-favourable spaces were introduced and studied also by G. Choquet [[#References|[a1]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130040/b130040128.png" />).
+
[[#References|[a10]]] is an excellent survey paper about topological games (including $\operatorname{BM} ( X )$).
  
 
====References====
 
====References====
<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</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Telgárski,  "Topological games: On the fifth anniversary of the Banach–Mazur game"  ''Rocky Mount. J. Math.'' , '''17'''  (1987)  pp. 227–276</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>
+
<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=22057
This article was adapted from an original article by P.S. Kenderov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article