おはにゃー！。
帽子クイズを知っていますか？。
- 人間たちが何人かいます。
- 人間たちはそれぞれ何色かの帽子のうち、一色の帽子を割り当てられ、被っています。
- 人間たちは、自分以外の人のうち、いくらかの（これはルールにより異なります）人間の帽子をみて、自分の帽子をあてます。
- ある割合よりも多くの人間が、正答できるような戦略はあるでしょうか。あるとすれば、どのようなものでしょうか。
といった問題は、屡々、帽子クイズなどと総称されます。
このゲームの無限版として、次のものを考えましょう。
ただし、$\omega$ で、自然数全体の集合およびその濃度を表すこととします。
- $\omega$ 人の人がいます。
- $\omega$ 色の帽子がたくさんあります。
- このような人間たちが、ゲームをします。
- まず、人間たちは、（帽子を配られる前に）作戦会議をします。作戦会議終了後、人間たちは一切の会話ができないものとします。
- 人間たちそれぞれにたいして、ある $1$ 色が選ばれ、その色の帽子を（本人にわからないように）被せられます。
- 人間たちは、帽子を被せられたあと、自分以外のすべての人間の帽子の色を確認できます（そうして他人の帽子の色をすべて知ります）。
- 人間たちは、確認のあと、自分の帽子を予想して、予想した結果を全員が同時に叫びます（したがって他人の予想を参照して自分の予想を決めることはできません）。
以上のゲームを「無限帽子クイズ」と呼ぶことにします。
さて、このゲームには要求された戦略が存在することがわかります。
証明します。
人間たちは $\omega$ 人いて、帽子も $\omega$ 色あるのでした。
ここでは人間たちも、帽子も、それぞれ、$0, 1, 2, \cdots$ と番号付けられているものとしましょう。
$\mathcal{N} :=\ ^\omega\omega$ で、$\omega$ から $\omega$ への函数の全体を表すこととします。
つまり、$f \in \mathcal{N}$ は、$\omega$ から $\omega$ へのある函数であり、人間たちへの帽子の割当を表すものとします
（たとえば $f(0) = 100$ なら、番号 $0$ を割り当てられた人間は、色 $100$ の帽子を被っている、ということです）。
$\mathcal{N}$ 上に次の同値関係を導入します*1*2*3: $$f \sim g :\leftrightarrow \exists F \Subset \omega \Bigl(f \upharpoonright_{\omega\backslash F}\ =\ g \upharpoonright_{\omega\backslash F}\Bigr)$$
つまり、2つの函数が有限集合上でだけ異なっている場合にはそれらは同じものだとおもってしまいましょう、ということです。
$\mathcal{M} := \mathcal{N}/ \sim$ とします。
選択公理によれば、$\mathcal{M}$ 上の選択函数があります。
この選択関数を、$\Psi \colon \mathcal{M}\to \mathcal{N}$ と書くことにします*4。
以上のことを、帽子を渡される前の「作戦会議」の段階でおこなっておきます。
さて、帽子を被らされ、お互いに情報共有をすることはもはやできません。
今回の帽子の割当を、$a \in \mathcal{N}$ とします。
人間 $i$ は次のようにして、己の帽子を予測します。
まず、$i$ からすれば、$a$ の $i$ 以外の値はわかりますから、$a$ が$\mathcal{M}$ でみたとき、どの同値類に入っているかは判断できます（つまり、答えが含まれる類までは絞れるということです）。その類が、$C_i$ であるとしましょう。このとき、$i$ は、$\Psi(C_i)(i)$ だと予測すればよいです。
以上の戦略で、たかだか有限人の人間を除く、すべての人間たちが予想を的中させられることを示します:
まず、各 $i$ が判断した「答えの入っている類」はすべて同一であることがわかります。その類を $C$ としましょう。
すると、戦略の定め方から、 $$g\ \colon \omega\to\omega\ ;\ \ i \mapsto \Psi(C_i)(i)$$ は、$\Psi(C)$ と一致します。
$a \in C$ でしたから、 $a \sim g$ 、つまり、クイズの条件を満たすことがわかりました。証明終了です。
この証明では、選択公理を用いました。
すると、自然な疑問として、今の議論は「本質的に」選択公理を使っていたのだろうか、というものが浮かびます。
以下の議論によって、実際、無限帽子ゲームの必勝法は選択公理にある意味で本質的に依存していたことがわかります。
発想は、クイズの解となる戦略は Lebesgue 非可測集合を構成してしまう、というものです*5。
この発想を精緻化するために、戦略の概念を形式化しましょう。 ただし以下では、$a \in \mathcal{N}$ にたいして、$i$ 番目以外のところを $a_{-i}$ で書き表すことにします*6
- 「無限帽子ゲーム」における戦略とは、函数 $S\ \colon \mathcal{N}\times \omega \to \omega$ であって、 すべての $i \in \omega$ と、すべての $a, a' \in \mathcal{N}$ について、 $$a_{-i} = a'_{-i} \ \ \rightarrow\ \ S(a, i) = S(a', i)$$ となるようなもののことである。
- 戦略 $S$ が必勝 (winning) であるとは、すべての $a \in \mathcal{N}$ にたいして、ある $n \in \omega$ が存在して、 すべての $i \in \omega$ について、 $$i > n \ \ \rightarrow \ \ S(a, i) = a(i)$$ となることである。
つまり、戦略とは、答えと人間を与えたときに、その人間の予測を与えるようなものであって、しかも、「自分のかぶっている帽子には依存しない」答えを出すようなものである、ということです。
また、必勝戦略とは、有限人を除くすべての人間が正答するということです。
次の命題が示せます:
証明します。
$S$ が必勝戦略であるとしましょう。
まず、$ ^\omega 2$ で $\omega$ から $2$ への函数の全体（に、$2 = \{0, 1\}$ に離散位相を入れ、その積位相を考えた位相空間）を表すことにして、$^\omega 2$ の部分集合 $E := \{a \in\ ^\omega 2 \mid \exists n \in \omega, \forall m > n, a(m) = a(n) )\}$ を定めます。
以下、$\mathcal{C}' := \ ^\omega 2 \backslash E$ という空間を考察の対象とします。このとき、$\mathcal{C}'$ の元を2進小数展開の係数とみることで、$\mathcal{C}'$ はその像 （$\subset [0, 1]$）と同相になります*7。
これをもって、$\mathcal{C}'$ と $\mathcal{C}'$ の像を同一視します。
このとき、$k \in \omega$ にたいして、集合 $D_k$ を $$D_k := \Bigl\{a \in \mathcal{C}' \mid \forall n \geq k\ \bigl(S(a, n) = a(n)\bigr)\Bigr\}$$
と定めると、$S$ が必勝であることから、
$$\mathcal{C}' = \bigcup_{k \in \omega}D_k$$ となります。
ここで、すべての $k \in \omega$ について、$D_k$ が Lebesgue 可測集合であると仮定します。 すると次のことがわかります:
もしこのことがわかれば、$(\star)$ の左辺は測度 $1$ ですが、右辺は、可算加法性によって測度が $0$ になってしまい、矛盾します。
以下、補題を証明します*8。
$D_k$ を任意に取ります。Lebesgue 測度の正則性によって、勝手な $\varepsilon > 0$ について、ある開集合 $U$ で、2条件
- $D_k \subset U$
- $\mu(U \backslash D_k) < \varepsilon$
を満たすものとることができます*9。$ ^\omega 2$ が第2可算性をもち、しかも、その開基として「有限個の値を決定することによって得られる開集合の族」をとれることに注意しておきます。 すると、ある $N$ 個の開基 $U_0, \cdots, U_{N-1}$であって*10、次の3条件
- $\bigcup_{i = 0}^{N-1}U_i\subset U$
- $\mu\Bigl(U \backslash \bigcup_{i = 0}^{N-1}U_i\Bigr) < \varepsilon$
を満たすものをとることができます。見やすさのため、 $\displaystyle U_f := \bigcup_{i = 0}^{N-1}U_i$ と置くことにします。
すると、$U$ 及び $U_f$ の取り方から $\mu(D_k \bigtriangleup U_f) < 2\varepsilon $ *11 となります。
ここで、$T_n\ \colon \mathcal{C}' \to \mathcal{C}'$ を、
$$T_n(a) := i \mapsto \begin{cases}a(i) & (i \neq n)\\ 1 - a(i) & (i = n)\end{cases}$$
と定めると、これは全単射です。
さきほど定義した $U_f$ 及び $D_k$ への $T_n$ の作用を考えてみます。
まず、$D_k$ の定義によって、$n > k$ ならば、 $T_n(D_k) \cap D_k = \emptyset$ です。
$U_f$ については、$ ^\omega 2$ の（特別な）開基の有限個の和集合でしたから、十分大きな $n$ については、$T_n(U_f) = U_f$ です。
また、可測集合と可測集合の共通部分が再び可測であることを思い出すと、（$n$ に応じた像の分割を考えて）任意の Lebesgue 可測集合 $A \subset \mathcal{C}'$ について、$\mu(T_n(A)) = \mu(A)$ となることがわかります*12。
以上のことを組み合わせると、まず、$n$ を十分大きく取っておくと、 \begin{align} \mu (T_n(D_k)\bigtriangleup U_f) &= \mu(T_n(D_k)\bigtriangleup T_n(U_f))\\ &= \mu(T_n(D_k\bigtriangleup U_f))\\ &= \mu(D_k\bigtriangleup U_f)\\ &< 2\varepsilon \end{align}
となることがわかります。さて、 $$U_f = \bigl(U_f \cap T_n(D_k)\bigr) \sqcup \bigl(U_f \backslash T_n(D_k)\bigr)$$ です。 $T_n(D_k) \cap D_k = \emptyset$ に注意すると、
- $U_f \cap T_n(D_k) \subset U_f \bigtriangleup D_k$
- $U_f \backslash T_n(D_k) \subset U_f \bigtriangleup T_n(D_k)$
ですから、$\mu(U_f) < 4\varepsilon$ が導かれます。
$U_f$ のとりかたによって、 $\mu(U) < 5\varepsilon$ です。
$U$ のとりかたによって、 $\mu(D_k) < 5\varepsilon$ となりますから、 $\varepsilon$ が任意だったことをおもいだすと、$\mu(D_k) = 0$ とわかります。
証明終了です。
さて、実は次のようなことが知られています:
このことと合わせて考えると、（十分強い論理のもと）ZF上では無限帽子クイズの解を証明できないことがわかりました。
参考文献として、C.S. Hardin, A.D. Taylor『An Introduction to Infinite Hat problems 』を挙げておきます。Lebesgue 非可測集合ができてしまうことの証明においては、
$D_k$ という集合に注目することが重要だったわけですが、これは当該文献からもってきました。
この文献においては非可測集合を構成するのではなく、Baire の性質に訴えることによって「ZFC + (弱)到達不能基数が存在する」ことが無矛盾であるという仮定を弱めて、議論しています。
ねるにゃー！。
[2026/01/29 1900追記] : pratonさんに、$\mu(D_k \bigtriangleup U_f)$ の評価の誤りを指摘していただきました。また、関連する表現や、一部ミスリーディングな箇所、記述の足りていない部分を追記しました。ありがとうございます。
*1:これは、有限集合のなすイデアルで函数の空間を割ったということです
*2:$\Subset$ は有限部分集合である、ということです。
*3:同値関係になっていることは簡単にわかります。
*4:つまり、すべての $C \in \mathcal{M}$ について、$\Psi(C) \in C$ だということです。
*5:なぜこのような発想が浮かぶかといえば、Vitali 集合の構成がいま行ったような議論だったから、ということになります。
*6:つまり、 $a_{-i} := a \upharpoonright_{\omega\backslash\{i\}}$ ということです。
*7:以下、注の内部でこのあたりの細かい話を展開するために、$\mathcal{C}'$ の像のことを、$\mathcal{C}' \subset \mathbb{R}$ と書き表します。
*8:以下の議論は、Vitali 集合の議論で言えば、可算集合（或いは一点集合の）測度が $0$ であることを示す議論に（気分が）近いです。
*9:この $U$ というのは、$\mathbb{R}$ の通常の位相についての開集合として取れるわけですが、$E$ の2進小数展開の像を除くことで $\mathcal{C}' \subset \mathbb{R}$ の開集合とみなします。 $E$ は可算な集合なので その像は Lebesgue 零集合です。したがって、このような修正を施しても測度は変わりません。
*10:これら$U_\bullet$ は$ ^\omega 2$ でとって $E$ を除いて $\mathcal{C}'$ の開集合とし、それを2進小数展開によって実数上の部分空間の開集合とみています。なお、$U$ のとりかたにかんする前注の内容も確認してください。
*11:$\bigtriangleup$ は対称差のことです。つまり $A \bigtriangleup B := (A\backslash B) \cup (B \backslash A)$ です。
*12:ここでは、暗に Lebesgue 測度の可算（有限）加法性・平行移動不変性を用いることになります。
