Banach–Mazur game

From Wikipedia, the free encyclopedia

In mathematics, in particular in general topology and set theory, a Banach-Mazur game is a game played between 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.

[edit] Definition

A general Banach-Mazur game is defined as follows: we have a topological space X and a family Y of subsets of X satisfying the following properties:

Each member of Y has non-empty interior.
Each non-empty open subset of X contains a member of Y.

A typical example is to let X equal the unit interval [0, 1] and let Y consist of all closed intervals [a, b] contained in [0, 1].

The game proceeds as follows. Let C be any subset of X. There are two players, Player I and Player II. Player I begins by choosing a member Y₁ of Y. Player II responds by choosing a member Y₂ of Y such that Y₂ is contained in Y₁. Then Player I responds by choosing Y₃ in Y with Y₃ contained in Y₂, and so on. In this way, we obtain a decreasing sequence of sets

$\cdots \subseteq Y_3 \subseteq Y_2 \subseteq Y_1 \subseteq X$

where Player I has chosen the sets with odd index and Player II has chosen the sets with even index. Player II wins the game if

$\bigcap_{n=1}^{\infty} Y_n \subseteq C.$

In other words, Player II wins if, after all the (infinitely many) choices are made, the set that remains lies entirely in C. (Some authors switch the goals of the two players in the game, so that player I wins if the intersection of all the sets is entirely in C.)

[edit] Winning strategies

The question is then, "For what sets C does Player II have a winning strategy?" Clearly, if C = X, Player II has a winning strategy. So the question can be informally given as, "How 'big' does the set C have to be to ensure that Player II has a winning strategy?", or equivalently, "How 'small' does the complement of C in X have to be in order to ensure that Player II has a winning strategy?"

Let us show that Player II has a winning strategy if the complement of C in X is countable and X is T₁ and has no isolated points. Let the elements of the complement of C be x₁, x₂, x₃,... Suppose Y₁ has been chosen by Player I. Let U₁ be the (non-empty) interior of Y₁. Then U₁ - {x₁} is a non-empty open set in X, so Player II can choose a member Y₂ of Y contained in U₁ - {x₁}. After Player I chooses a subset Y₃ of Y₂, Player II can choose a member Y₄ of Y contained in Y₃ that excludes the point x₂ in a similar fashion. Continuing in this way, each point x_n will be excluded by the set Y_2n, and so the intersection of all the Y_n's will be contained in C.

Let us note that in the proof above, the additional assumptions on X are really needed. For instance, if $X = {a, b, c}$ is equipped with the discrete topology and $Y$ consists of all non-empty subsets of X, then Player II has no winning strategy in the Banach-Mazur game for the co-finite set ${a, b}$ , as a matter of fact his opponent has a winning strategy. Similar effect happens if X is equipped with indiscrete topology and $Y = {X}$ .

A set is "small" in a set-theoretic sense if it is countable. The corresponding notion for topology is the concept of a set being of the first category or meagre. A set is meagre if it is the countable union of nowhere dense sets. It turns out that this is just how small the complement of C has to be in order for Player II to have a winning strategy. In other words, we have the following:

Let X be a topological space, let Y be a family of subsets of X satisfying the two properties above, and let C be any subset of X. Then Player II has a winning strategy for the Banach-Mazur game if and only if the complement of C in X is meagre.

This is not to say that Player I has a winning strategy if the complement of C in X is not meagre. Player I has a winning strategy if and only if there is some Y_i in Y such that the intersection of C with Y_i is a comeager subset of Y_i. It may be the case that neither player has a winning strategy. If one player has a winning strategy, the game is determined. When X is [0, 1] and Y consists of the closed intervals [a, b], the game is determined if the target set has the property of Baire; i.e. it differs from an open set by a meagre set. (The converse does not hold.)

[edit] References

A proof can be found in

Oxtoby, J.C. The Banach-Mazur game and Banach category theorem, Contribution to the Theory of Games, Volume III, Annals of Mathematical Studies 39 (1957), Princeton, 159-163