Banach–Mazurゲーム(Banach–Mazur game)とは、位相空間 $X$ の部分集合 $A$ について、2 人が空でない開集合を交互に選んで減少列を作り、共通部分が $A$ と交わればプレイヤー $\mathrm{I}$ の勝ち、そうでなければ $\mathrm{II}$ の勝ちとする無限ゲームである。$\mathrm{II}$ が必勝戦略をもつことは $A$ が痩せていることと同値であり(Oxtoby の定理)、完備距離空間では $\mathrm{I}$ が必勝戦略をもつことは $A$ がある空でない開集合で共痩せであることと同値である。共通部分が空でないことを $\mathrm{II}$ の勝ちとする変種では、$\mathrm{I}$ が必勝戦略をもたないことが空間の Baire 性と同値になる。完備距離空間では Baire の性質をもつ集合のゲームは決定される。
前提知識: Baireのカテゴリー定理, 疎集合, Baireの性質, 完備距離空間
Banach–Mazur ゲーム は、2 人のプレイヤーが位相空間の空でない開集合を交互に選んで小さくしていく無限ゲームである。1935 年に S. Mazur が Lwów の「スコットランドの本」の問題 43 として提案し、S. Banach が解いた(Tel87 §4、pp. 232–233)。プレイヤー I は、最後に残る共通部分が与えられた集合 $A$ と交わることを目指し、プレイヤー II はそれを阻む。
このゲームの値打ちは、勝敗が $A$ の「位相的な大きさ」と正確に対応することにある。II が必ず勝つ方法(必勝戦略)をもつのは、$A$ が痩せた集合(第1類集合)であるときに限る(Oxtoby の定理)。完備距離空間では、I が必勝戦略をもつのは、$A$ がある空でない開集合の中でほとんど全部を占めるときに限る。こうして「痩せている」「ほとんど全部」という Baire のカテゴリーの概念が、ゲームの言葉で言い換えられる。共通部分が空でないことを II の勝ちとする変種を使うと、空間が Baireのカテゴリー定理 の意味の Baire 空間であることも、ゲームで特徴づけられる。
この記事では、これらの定理を一つの補題(戦略の展開)から証明し、完備距離空間では Baire の性質をもつ集合のゲームは決定されること、Vitali 集合のゲームは決定されないことを示す。
$X$ を位相空間とする。$A\subset X$ が 疎(nowhere dense)であるとは閉包の内部が空であることをいい、疎な集合の可算個の和集合を 痩せた集合(meager set、第1類集合)という(Baireのカテゴリー定理 の定義「第1類集合と第2類集合」)。疎な集合の閉包も疎なので、痩せた集合は疎な閉集合の可算個の和集合に含まれる。$X\setminus A$ が痩せているとき、$A$ は 共痩せ(comeager)であるという。空でない開集合 $U$ について $U\setminus A$ が痩せているとき、$A$ は $U$ で共痩せ であるという。
$X$ を空でない位相空間、$A\subset X$ とする。ゲーム $\mathrm{BM}(A)$ では、プレイヤー I と II が交互に $X$ の空でない開集合を選び、
$$
U_0\supset V_0\supset U_1\supset V_1\supset U_2\supset\cdots
$$
という減少列を作る。I が $U_n$ を、II が $V_n$ を選ぶ。各プレイヤーはそれまでに選ばれた集合をすべて知っている。このように無限に続けた列を プレイ という。
$$
A\cap\bigcap_{n}U_n\ne\emptyset
$$
なら I の勝ち、そうでなければ II の勝ちとする。$\bigcap_nU_n=\bigcap_nV_n$ なので、どちらの列で共通部分をとっても同じである。このゲームを $A$ の Banach–Mazur ゲーム(Banach–Mazur game)という。
また、同じ手順で、$\bigcap_nV_n\ne\emptyset$ なら II の勝ち、$\bigcap_nV_n=\emptyset$ なら I の勝ちとするゲームを $\mathrm{BM}^\ast(X)$ と書く。
戦略 とは、それまでの手の列から次の手を決める規則である。II の戦略 $\tau$ は、I の手で終わる各局面 $(U_0,V_0,\dots,U_n)$ に、空でない開集合 $\tau(U_0,V_0,\dots,U_n)\subset U_n$ を対応させる。I の戦略 $\sigma$ は、最初の手 $\sigma(\emptyset)$ と、II の手で終わる各局面 $(U_0,V_0,\dots,V_n)$ に対する空でない開集合 $\sigma(U_0,\dots,V_n)\subset V_n$ からなる。プレイヤーが戦略に従うとは、自分の番ではつねに戦略の値を選ぶことをいう。戦略が 必勝戦略 であるとは、相手がどう選んでも、その戦略に従えば必ず勝つことをいう。両方のプレイヤーが同時に必勝戦略をもつことはない(互いの必勝戦略どうしを戦わせると、両方が勝つことになる)。どちらか一方が必勝戦略をもつとき、ゲームは 決定される という(決定性公理 の定義「決定性と決定性公理」と同じ言葉づかい)。
記号は文献によって異なる。Tel87 §4 は I と II の役割をこの記事と同じにとってゲームを、単位区間の部分集合については $MB(X,J)$、一般の空間では $MB(X,Y,\mathcal{W})$ と書き、$\mathrm{BM}^\ast(X)$ にあたるゲームを $BM(X)$ と書いている。勝敗の条件を補集合に移して、「$\bigcap V_n\subset B$ なら II の勝ち」と書く流儀もある。$B:=X\setminus A$ とおけばこの記事の $\mathrm{BM}(A)$ と同じゲームである。
II が勝つには、共通部分から $A$ の点をすべて追い出せばよい。$A$ が疎な閉集合 $F_0,F_1,\dots$ の和集合に含まれていれば、II は $n$ 手目に「今の開集合から $F_n$ を取り除く」ことができる。疎な閉集合を除いても空でない開集合が残るからである。こうして $A$ の点は 1 手ごとに少しずつ追い出され、最後には一つも残らない。
逆に、II が勝ち方を知っているとき、$A$ が痩せていることを示すには、II の戦略を「すべての可能な I の手に対して同時に」展開する。I の手を空間全体に敷き詰めると、II の応答は互いに素な開集合の族になり、その和集合は稠密になる。これを無限回くりかえすと、稠密な開集合の列が得られ、その共通部分の点はどれも、II が戦略どおりに勝ったプレイの共通部分に入っている。したがって $A$ はこの共通部分の外、つまり疎な閉集合の可算和の中にある。この展開が下の lem-bm-unfolding である。
必勝戦略から集合の大きさを読み取るための補題を、I と II のどちらの戦略にも使える形で述べる。相手の手 $O_k$ に対して応答 $O_k'$ を返す規則 $\rho$ を考える。
$X$ を位相空間、$W$ を空でない開集合とする。$\rho$ は、空でない開集合の有限減少列 $(O_0,O_0',O_1,O_1',\dots,O_n)$ で $O_0\subset W$ となるものに、空でない開集合 $\rho(O_0,\dots,O_n)\subset O_n$ を対応させる規則とする。減少列 $O_0\supset O_0'\supset O_1\supset O_1'\supset\cdots$($O_0\subset W$)が $\rho$ に従う とは、各 $k$ について $O_k'=\rho(O_0,O_0',\dots,O_k)$ となることをいう。
このとき、開集合の列 $W\supset G_0\supset G_1\supset\cdots$ で、各 $G_n$ が $W$ で稠密($W\subset\overline{G_n}$)であり、次を満たすものがある:任意の $x\in\bigcap_nG_n$ について、$\rho$ に従う無限列 $(O_k,O_k')_{k\ge0}$ で $x\in\bigcap_kO_k'$ となるものがある。
$\rho$ に従う長さ $2(n+1)$ の有限列 $p=(O_0,O_0',\dots,O_n,O_n')$ を $n$ 段の局面 とよび、最後の項を $O'(p):=O_n'$ と書く。$n$ 段の局面の族 $\mathcal{P}_n$ を、次の 3 条件を満たすように $n$ についての帰納法で作る。
$G_n$ が $W$ で稠密な開集合なら、$W\setminus G_n$ は疎である。実際 $W\setminus G_n\subset\overline{W}\setminus G_n$ であり、右辺は閉集合で、その内部 $H$ が空でなければ $H$ は($\overline W$ に含まれる開集合なので)$W$ と交わり、空でない開集合 $H\cap W$ が $G_n$ と交わらないことになって稠密性に反する。したがって $W\setminus\bigcap_nG_n=\bigcup_n(W\setminus G_n)$ は痩せている。以下ではこの形で補題を使う。
$X$ を空でない位相空間、$A\subset X$ とする。$\mathrm{BM}(A)$ で II が必勝戦略をもつことと、$A$ が痩せた集合であることは同値である。
($A$ が痩せていれば II が勝つ)$A\subset\bigcup_nF_n$ となる疎な閉集合 $F_0,F_1,\dots$ をとる。II の戦略を $\tau(U_0,\dots,U_n):=U_n\setminus F_n$ と定める。$F_n$ は閉で内部が空なので、$U_n\setminus F_n$ は空でない開集合である。この戦略に従うプレイでは $V_n\cap F_n=\emptyset$ なので、$\bigcap_kV_k$ はどの $F_n$ とも交わらず、$A$ とも交わらない。よって II が勝つ。
(II が勝てば $A$ は痩せている)$\tau$ を II の必勝戦略とする。lem-bm-unfolding を $W:=X$、相手を I、$\rho:=\tau$ として使い、$X$ で稠密な開集合の列 $G_n$ をとる。$x\in\bigcap_nG_n$ なら、$\tau$ に従うプレイで $x\in\bigcap_kV_k$ となるものがある。$\tau$ は必勝戦略なので $A\cap\bigcap_kV_k=\emptyset$ であり、$x\notin A$ である。よって $A\subset X\setminus\bigcap_nG_n$ であり、右辺は補題の直後の注意($W=X$)により痩せている。$\square$
この定理は Tel87 §4(p. 233)に、Oxtoby(1957)が一般の位相空間で証明した結果として紹介されている。
$X$ を空でない位相空間、$A\subset X$ とする。
1 の証明で I の手を小さくする修正は、距離があることだけを使う。2 では、共通部分が空にならないことを完備性で保証している。Tel87 §4(p. 233)は、完備距離空間についてのこの特徴づけを Oxtoby(1957)の結果として紹介している。
Baireのカテゴリー定理 の定義「空間の Baire 性」により、$X$ が Baire 空間 であるとは、稠密な開集合の列の共通部分がつねに稠密であることをいう。
空でない位相空間 $X$ について、$X$ が Baire 空間であることと、$\mathrm{BM}^\ast(X)$ で I が必勝戦略をもたないことは同値である。
(Baire 空間でなければ I が勝つ)$X$ が Baire 空間でないとすると、稠密な開集合 $D_0,D_1,\dots$ と、$\bigcap_nD_n$ と交わらない空でない開集合 $H$ がある。I は $U_0:=H$ を選び、II が $V_n$ を選んだら $U_{n+1}:=V_n\cap D_n$ を選ぶ。$D_n$ は稠密な開集合なので $U_{n+1}$ は空でない開集合である。このとき $\bigcap_nU_n\subset H\cap\bigcap_nD_n=\emptyset$ なので I が勝つ。
(I が勝てば Baire 空間でない)$\sigma$ を I の必勝戦略とし、$W:=\sigma(\emptyset)$ とおく。lem-bm-unfolding を相手を II、$\rho$ を $\sigma$ の 2 手目以降として使い、$W$ で稠密な開集合の列 $G_n\subset W$ をとる。$x\in\bigcap_nG_n$ なら、$\sigma$ に従うプレイで $x$ が共通部分に入るものがあるが、$\sigma$ は必勝戦略なのでそのプレイの共通部分は空であり、矛盾する。よって $\bigcap_nG_n=\emptyset$ である。$D_n:=G_n\cup(X\setminus\overline{W})$ とおくと $D_n$ は開集合で、$X$ で稠密である(空でない開集合 $H$ が $W$ と交われば $H\cap W$ が $G_n$ と交わり、交わらなければ $H\subset X\setminus\overline W$ である)。しかし $W\cap\bigcap_nD_n=\bigcap_nG_n=\emptyset$ なので、$\bigcap_nD_n$ は稠密でない。よって $X$ は Baire 空間でない。$\square$
Tel87 §4(p. 234)は、この特徴づけを Krom(1974)の観察として述べ、本質的には Oxtoby(1957)による、と注意している。II が $\mathrm{BM}^\ast(X)$ で必勝戦略をもつ空間は、したがって Baire 空間である。逆は成り立たない:Tel87 p. 234 は、実数直線の Bernstein 集合が Baire 空間であるが、II が $\mathrm{BM}^\ast$ で必勝戦略をもたない例であることを述べている(この記事では証明しない)。
完備距離空間では II が $\mathrm{BM}^\ast(X)$ で勝つ。thm-bm-player-one の 2 の証明と同じく、II が閉包の直径が $0$ に近づくように手を選べば、共通部分は空でないからである。これは Baireのカテゴリー定理 をゲームの形で述べ直したものになっている。
$X$ を完備距離空間、$A\subset X$ とする。
1 は thm-bm-oxtoby と thm-bm-player-one をまとめたものである。2:Baireの性質 の命題「Baireの二者択一」により、Baire の性質をもつ $A$ は痩せているか、ある空でない開集合で共痩せである。1 により $\mathrm{BM}(A)$ は決定される。$\square$
2 は Tel87 §4(p. 233)に Oxtoby の結果の帰結として述べられている。開集合・閉集合・Borel集合 は Baire の性質をもつので(Baireの性質 の定理「Baireの性質をもつ集合は $\sigma$-代数をなす」)、それらのゲームはすべて決定される。
$X=\mathbb{R}$ とし、有理数を $q_0,q_1,\dots$ と並べる。
選択公理を仮定し、$V\subset\mathbb{R}$ を Vitali 集合($x-y\in\mathbb{Q}$ で定まる同値関係の各同値類から 1 点ずつ選んだ集合)とする。このとき $\mathrm{BM}(V)$ はどちらのプレイヤーも必勝戦略をもたない。
II が必勝戦略をもつとすると、thm-bm-oxtoby により $V$ は痩せている。これは Baireの性質 の定理「Baireの性質をもたない集合」の証明の段 2 に反する。I が必勝戦略をもつとすると、thm-bm-player-one の 1 により $V$ はある空でない開集合 $U$ で共痩せであり、$U$ に含まれる開区間 $(a,b)$ についても $(a,b)\setminus V$ は痩せている。同じ証明の段 3 は、空でない開区間 $(a,b)$ について $(a,b)\setminus V$ が痩せていると仮定して矛盾を導いているので、これも起こらない。
この例は、Baire の性質をもたない集合のゲームが決定されないことがあることを示す。cor-bm-determined の 1 により、完備距離空間の $\mathrm{BM}(A)$ が決定されないのは、$A$ が痩せておらず、しかもどの空でない開集合でも共痩せでないときに限る。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 距離化可能(thm-bm-player-one の 1) | 2 点集合 $\{a,b\}$ の密着位相、$A=\{a\}$ | I が勝てば $A$ はある空でない開集合で共痩せ |
| 完備(thm-bm-player-one の 2) | $X=\mathbb{Q}$(通常の距離)、$A=\mathbb{Q}$ | $A$ が空でない開集合で共痩せなら I が勝つ |
| Baire の性質(cor-bm-determined の 2) | Vitali 集合(ex-bm-vitali) | ゲームが決定される |
1 行目では、空でない開集合は $X$ 自身だけなので、どのプレイでも共通部分は $X$ で $A$ と交わり、I がつねに勝つ。一方、空でない部分集合の閉包はどれも $X$ なので疎な集合は空集合だけであり、痩せた集合も空集合だけである。よって $\{b\}$ は痩せておらず、$A$ は $X$ で共痩せでない。2 行目では、$A=X$ は $X$ で共痩せだが、II は ex-bm-rationals の 3 と同じ手 $V_n:=U_n\setminus\{q_n\}$ で共通部分を空にでき、I は勝てない(thm-bm-oxtoby の言葉では、$\mathbb{Q}$ は $\mathbb{Q}$ の中で痩せている)。
Banach–Mazur ゲームは、Baire空間(記述集合論) $\omega^\omega$ の上の「自然数を出し合うゲーム」(決定性公理 の定義「無限ゲームと戦略」)と並んで、記述集合論で決定性を調べる道具になる。Tel87 §1 は、Mycielski が決定性公理から実数の任意の部分集合が Baire の性質をもつことを導いたことを紹介している(この記事では証明しない)。cor-bm-determined の 1 から見ると、Banach–Mazur ゲームの決定性は「痩せているか、どこかの開集合でほとんど全部か」という二者択一そのものである。
$\mathrm{BM}^\ast(X)$ で I が点 $x_n$ とその開近傍 $U_n$ を選び、II が $x_n$ の開近傍 $V_n\subset U_n$ を選ぶように変えたゲームを、Tel87 §7(p. 243)は Choquet ゲーム $Ch(X)$ とよんでいる。II の選ぶ集合が I の指定した点を含まなければならないので、II にとって有利さが変わる。Choquet は、距離化可能空間 $X$ では II が $Ch(X)$ で必勝戦略をもつことと $X$ が完備距離で距離化できることが同値であることを示した(同 p. 243、この記事では証明しない)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する