ヒンドマンの定理をストーンチェックコンパクト化を用いて証明する

最近ストーンチェックコンパクト化というものについて勉強したのですが、組み合わせ論（ラムゼー理論）の有名な定理であるヒンドマンの定理が、実は$\mathbb{N}$ のストーンチェックコンパクト化を考えることで非常に鮮やかに証明できるということを知りました。（元論文の証明は１００ページ超に及びますが、ストーンチェックコンパクト化を用いれば証明自体は１ページくらいになります。）個人的に非常に面白い話だと思ったのですが、証明を追うにあたって日本語の文献が見つからず苦労したので、調べた結果をここにまとめておこうと思います。位相空間の基本的な事柄以外の前提知識はなくても読めるように書いていくので、ぜひ最後まで読んで証明の美しさを体感していただけると嬉しいです！

目標（ヒンドマンの定理）

まず最初に、証明したいヒンドマンの定理の主張を紹介しておきます。

この定理の意味を考えてみます。$X$の有限和が全て同じ色ということは、$X$の元が全て同じ色であるのはもちろん、$X$の元を足し合わせても全て同じ色になると言っているのです。この$X$はバケモンみたいな構造を持っているということがなんとなく分かります。そしてこのような$X$が、どのような色の塗り分け方に対しても必ず存在するというのがヒンドマンの定理の主張です。つまり、素数とそれ以外で塗り分けたりしてもいいし、他のどんなめちゃくちゃな塗り分け方をしてもいいわけです。なんだか凄そうな定理だというのが分かってきたのではないでしょうか。こんな凄まじい定理が位相空間の定理によって示されてしまうなんて、とてもワクワクしませんか？

フィルターに関する基本事項

それではこの定理を示すべく、前提知識の準備をします。主にフィルターや超フィルターに関する基本事項です。

位相と同じで有限交叉について閉じています。特徴的なのは$(3)$で、ある$F$を含めば$F$と$X$の間にある集合は全て含むと言っています。なんとなくフィルター感がありますね。

特に細分は後でよく出てきます。たまにどっちが細分か分からなくなりますが、より多くの元を含んでいる方が細分です。

さて、位相の時と同じで、部分集合族から生成されるフィルターというものを考えることができます。ただし、フィルターの場合は有限交叉的な部分集合族に対してのみ、それが生成するフィルターを定義することができます。

次の補題は細分と両立を結びつける、基本的かつ重要な主張です。

(証明)
$(1)$$\Longrightarrow(2)$
共通の細分を$\mathcal{H}$とする。$F \in \mathcal{F},G \in \mathcal{G} $を任意に取ると$F,G \in \mathcal{H} $とフィルターの公理から$F \cap G$$\in$$\mathcal{H}$である。よってフィルターの公理から$F \cap G$$\neq$$\emptyset$
$(2)$$\Longrightarrow$$(1)$
$\mathcal{F}, \mathcal{G}$が両立することより、$\mathcal{F}$$\cup$$\mathcal{G}$は有限交叉的な集合族になっている。よってこれが生成するフィルター$< \mathcal{F} \cup \mathcal{G} >$を考えることができ、これが共通の細分になっている。

以降、基本補題といえばこの補題を指します。

この超フィルターというのが超重要です。超フィルターが今回の証明の主役になっていきます。ということで、準備のため超フィルターに関する定理を二つほど紹介しておきます。

(証明)
$(1)$$\Longrightarrow(2)$
背理法で示す。すなわち、$\mathcal{U}$が超フィルターかつ、ある$A \subset X$について$A \notin $$\mathcal{U}$かつ$X/A$$\notin$$\mathcal{U}$であると仮定する。
この時、$A$のみからなる部分集合族が生成するフィルターを考えると、これは$\mathcal{U}$と共通の細分を持たない。（持つとしたら超フィルターの定義より$\mathcal{U}$しかありえないが、これは$<\{A\}>$の細分ではない）
したがって基本補題より二つのフィルターは両立しないので、ある$U$$\in$$\mathcal{U}$が存在して$U \cap A$$ = \emptyset$となる。同様に考えて、ある$V \in $$\mathcal{U}$が存在して$V \cap X/A$$=$$\emptyset$となる。この時$U \cap V$$=$$\emptyset$で、これは$U \cap V \in \mathcal{U} $に矛盾する。
$(2) \Longrightarrow (1)$
$\mathcal{U}$を$(2)$の条件を満たすフィルター、$\mathcal{F}$を$\mathcal{U}$の細分とする。$F$$\in$$\mathcal{F}$を任意に取ると、$X/F$$\notin$$\mathcal{F}$である。（これが含まれると$F$との共通部分である$\emptyset$も含まれてしまい矛盾だから。）したがって$X/F$$\notin$$\mathcal{U}$で、これと$(2)$の仮定から$F$$\in$$\mathcal{U}$となる。以上より$\mathcal{F}$$\subset$$\mathcal{U}$が成り立つことが分かるから、$\mathcal{F}$$=$$\mathcal{U}$である。したがって$\mathcal{U}$が超フィルターであることが言えた。

この定理から特に次のことが言えます。
超フィルターは$A$と$X/A$のどちらか一方のみを必ず含む
（両方含んでしまうと共通部分の空集合が含まれてしまい矛盾します）
超フィルターに関してはこれを使うことで見通しよく議論できる場合が多く、今後もどんどん使っていきます。

シンプルながら強いです。証明は細分全体に対してZornの補題を適用すれば良いです。ちなみにこの補題はウルトラフィルター補題とも呼ばれているらしいです。なんかカッコいいので今後はこの名前で呼んでいこうと思います。

位相空間$β \mathbb{N} $の定義

さて、準備が整ったので、いよいよ証明の舞台となる$\mathbb{N}$のストーンチェックコンパクト化、$\beta\mathbb{N}$を構成していこうと思います。

まず、$e(A)$には$e(A \cap B)=e(A) \cap e(B)$や$e(A)^c=e( A^c )$などの性質があります。これらは超フィルターの性質から導かれるものであり、今後断りなく使っていくので注意してください。
$\{e(A)|A \subset \mathbb{N} \}$が開基になるための条件を満たしていることの確認は比較的容易なので割愛します。さて、$\beta\mathbb{N}$は$\mathbb{N}$の超フィルター全体に適切な位相を入れた位相空間なわけですが、そもそも$\mathbb{N}$上の超フィルターってなんだ？という感じなので、いくつか具体例を挙げておこうと思います。
まず、自然数$n$を固定したとき、$n$を含む$\mathbb{N}$の部分集合全体を$\mathcal{U}_n$で表すと、これは超フィルターになっています。$\mathcal{U}_n$がフィルターになっていることはすぐに分かりますが、超フィルターになっているかどうかは一瞬？となります。こんな時は補題３を思い出しましょう。フィルターが任意の集合$A$に対して$A$または$X/A$を必ず含むことが言えれば超フィルターであると言えれば良いのでした。今任意の集合$A$を持ってきました。あなたは$n$を含みますか？
はい→$A$が$\mathcal{U}_n$に含まれます。ありがとう。
いいえ→$X/A$が$\mathcal{U}_n$に含まれます。ありがとう。
といった感じです。超フィルター絡みではこういう議論をすることが結構あります。
さて、今述べた超フィルター$\mathcal{U_n}$は主超フィルターと言います。今後使うことがあるので一応定義の形で改めて書いておきます。

主超フィルターに関して一つ補題を示しておきます。

（証明）
$\mathbb{N}$上の超フィルター$p$が有限集合$F=\{x_1,x_2,,,,x_n\}$を要素に持ったと仮定する。$p$が$x_1〜x_n$をいずれも要素に持たないと仮定すると、$ \mathbb{N}/\{x_1\}〜 \mathbb{N}/\{x_n\} $は$p$の要素であるからこれらの共通部分である$\mathbb{N}/F$も$p$の要素となる。このとき$F \cap \mathbb{N}/F= \emptyset $も$p$の要素となってしまい矛盾。よって$p$はある$x_i$を要素にもつ。これとフィルターの公理より$ \mathcal{U}_{x_i} \subset p$となる。これと超フィルターの極大性から$\mathcal{U}_{x_i}=p$と分かる。
（証明終）

さて、もちろん$\mathbb{N}$上の超フィルターは主超フィルターだけではありません。$\mathbb{N}$上のフィルターというのは色々存在するわけですが（気になった方は調べてみてください）ウルトラフィルター補題よりこれらには全てその細分となる超フィルターが存在しているのでこれらも全て$\beta\mathbb{N}$に含まれています。（二つのフィルターが共通の超フィルターを細分に持つ場合もあるとはいえ、それでも超フィルターはたくさん存在します。）こんな感じで、$\beta\mathbb{N}$は結構巨大な位相空間なんだなというイメージを持っておくと良いと思います。
ここからは$\beta\mathbb{N}$の性質について調べていきます。$\beta\mathbb{N}$はヒンドマンの定理が翻訳される舞台になっているので、$\beta\mathbb{N}$に関して知見を深めておくことでヒンドマンの定理を簡単に示すことができます。

(証明)
ハウスドルフ性は比較的簡単に示せるのでコンパクト性を示していく。
背理法を用いる。$\beta\mathbb{N}$がコンパクトでないと仮定する。この時$\beta\mathbb{N}$の開基からなる開被覆であって有限部分被覆を持たないようなもの$\left\{e(A_i)\right\}_{i\in I} $が存在する。この時任意の有限集合$\{i_1,i_2,,,,i_n\}$$\subset$$I$に対して$\bigcup_{i=1}^{n} e(A_i)$$\neq$$\beta\mathbb{N}$となる。両辺の補集合をとって$\bigcap_{i=1}^{n} e( \mathbb{N}/A_i)$$\neq$$\emptyset$となる。よって$e(\bigcap_{i=1}^{n} \mathbb{N}/A_i)$$\neq$$\emptyset$より$\bigcap_{i=1}^{n} \mathbb{N}/A_i$$\neq$$\emptyset$となる。これが$I$の任意の有限部分集合に対して成り立つから、$F=\{ \mathbb{N} /A_i|i \in I\}$は有限交叉的な集合族である。したがって$F$が生成するフィルター$< F>$を考えることができる。さらにウルトラフィルター補題よりこれの細分なる超フィルター$\mathcal{U}$が存在するが、このとき$\mathcal{U}$はどの$e(A_i)$にも含まれないから$\left\{e(A_i)\right\}_{i\in I} $が$β \mathbb{N} $の開被覆であったことに矛盾する。よって$β \mathbb{N} $はコンパクトである。
（証明終）

$β \mathbb{N} $に演算を入れる

次に、$\beta\mathbb{N}$上に適切な演算を定義して、$\beta\mathbb{N}$を半群と見なす、ということをやっていきます。半群とは結合法則のみを仮定した演算入り集合のことです。

私は最初この定義を見たとき？？となりました。なかなかイメージが掴めない演算です。しかしやっていくうちにこの定義はとても妥当であることが分かってきます。とりあえず演算のwell-defined性、すなわち超フィルター$p,q$に対して$p+q$も超フィルターであること、を確認しておきます。

（証明）
超フィルター$p,q$に対して$p+q$が超フィルターであることを示す。まず、$\emptyset \notin p+q, \mathbb{N} \in p+q$は明らか。$A,B \in p+q$とすると、$\{n \in \mathbb{N} |A-n \in q\} \in p$および$\{n \in \mathbb{N} |B-n \in q\} \in p$が成り立つ。ここで$(A-n) \cap (B-n)=(A \cap B)-n$に注意すると、$\{n \in \mathbb{N} |A-n \in q\} \cap \{n \in \mathbb{N} |B-n \in q\}$$\subset$ $\{n \in \mathbb{N} |(A \cap B)-n \in q\}$ が分かる。左辺は$p$の元だからフィルターの公理から右辺も$p$の元である。よって$A \cap B \in p+q$が言えた。超フィルターの残りの公理も同様にして確かめることができるので省略する。
（証明終）

次の補題は、上で定義した演算がある意味で$\mathbb{N}$における加法の拡張になっているということを示すという点で、演算の妥当性の一部を示すものです。

（証明）
$A \in \mathcal{U}_a+\mathcal{U}_b \Longleftrightarrow \{n \in \mathbb{N} |A-n \in \mathcal{U}_b \} \in \mathcal{U}_a \Longleftrightarrow a \in \{n \in \mathbb{N} |A-n \in \mathcal{U}_b \} \Longleftrightarrow A-a \in \mathcal{U}_b \Longleftrightarrow a+b \in A \Longleftrightarrow A \in \mathcal{U}_{a+b} $より従う。
（証明終）

さて、位相空間$\beta\mathbb{N}$に演算構造を入れることに成功しました。
今後の流れを少し説明しておくと、
$(1)$ 右連続半群を定義する。$\beta\mathbb{N}$が今定義した演算により右連続半群になっていることも示せる。
$(2)$コンパクト右連続半群に対して使えるエリスの補題と呼ばれるものを証明する。
$(3)$$\beta\mathbb{N}$にエリスの補題を適用することによってヒンドマンの定理が示せる
といった感じです。順番にやっていきましょう。

要するに位相空間と演算のセットで演算に関して連続なんだなあと思っておけば良いと思います（右とか左とか細かいところはありますが）

（証明）
結合法則はやればできるので、演算に関する右連続性を示していく。$q \in \beta\mathbb{N}$を固定して、$f_q:p→p+q$が連続写像であることを示す。これは任意の$A \subset \mathbb{N} $に対して$f_q^{-1}(e(A))$が$\beta\mathbb{N}$の開集合であることが言えればよい。
$p \in f_q^{-1}(e(A)) \Longleftrightarrow p+q \in e(A) \Longleftrightarrow A \in p+q \Longleftrightarrow \{n \in \mathbb{N} |A-n \in q\} \in p \Longleftrightarrow p \in e(\{n \in \mathbb{N} |A-n \in q\})$より$f_q^{-1}(e(A))=e(\{n \in \mathbb{N} |A-n \in q\})$となる。右辺は明らかに$\beta\mathbb{N}$の開集合である。以上より示された。
（証明終）

エリスの補題

主定理の証明で重要な役割を果たすエリスの補題を紹介します。これはコンパクトな右連続半群に関する補題です。先ほど示した通り$β \mathbb{N} $はコンパクトな右連続半群なので、$β \mathbb{N} $に対してこの補題を適用することができます。

この補題自体個人的にはとても興味深いです。示していきます。証明にはツォルンの補題の双対を使います。

(証明)
$S$はコンパクトハウスドルフだから、$S$においてコンパクト$\Longleftrightarrow$閉集合であることに注意しておく。
$S$の非空部分集合であって、コンパクトかつ演算について閉じているようなものたちを集めた部分集合族$\mathcal{F}$を考える。$\mathcal{F}$がツォルンの補題の双対の仮定を満たしていること、すなわち$\mathcal{F}$の任意の全順序部分集合に対してその下界が（$\mathcal{F}$内に）存在することを示す。 $\{F_i\}_{i\in I}$ を$\mathcal{F}$の全順序部分集合とする。$\{F_i\}_{i\in I}$ から有限個の元を選ぶと、これらは包含関係で一列に並べることができるので、特に交わる。よって$\{F_i\}_{i\in I}$ はコンパクト空間$S$の有限交叉的な閉集合族になっているので$\bigcap_{i\in I} F_i$$\neq$$\emptyset$となる。さらに$\bigcap_{i\in I} F_i$$\in$$\mathcal{F}$であることが分かるので、$\bigcap_{i\in I} F_i$は$\{F_i\}_{i\in I}$ の下界になっている。以上より$\mathcal{F}$がツォルンの補題の双対の仮定を満たすことが確かめられた。よって$\mathcal{F}$には極小元が存在する。これを$\mathcal{M}$と書く。$\mathcal{M}$$\in$$\mathcal{F}$なので$\mathcal{M}$$\neq$$\emptyset$である。さて、実は$\mathcal{M}$の元は全てべき等元になっている。これを以下で確かめていく。まず、次の補題を示す。

(証明)
まず、$\mathcal{M}+x$$\subset$$\mathcal{M}$は明らか。次に$\mathcal{M}+x \in \mathcal{F} $を示す。$\mathcal{M}+x$が演算について閉じていることは結合法則から従う。また、$S$の右連続性より$\mathcal{M}+x$はコンパクト集合$\mathcal{M}$の連続像だからコンパクトである。したがって$\mathcal{M}+x \in \mathcal{F} $が分かった。これと$\mathcal{M}$の極小性から$\mathcal{M}+x= \mathcal{M} $が言えた。
（証明終）

では上の補題を用いて、$\mathcal{M}$の任意の元がべき等元であることを示していこう。$x \in \mathcal{M} $を任意に取る。このとき$\mathcal{M}+x= \mathcal{M} $であるから、ある$e$$\in$$\mathcal{M}$が存在して$e+x=x$となる。ここで$T=\{y \in \mathcal{M}|y+x=x \}$と定義すると、$e \in \mathcal{M} $より$T \neq \emptyset $である。また、$T$が演算について閉じていることも容易に確かめられる。さらに$T= \mathcal{M} \cap f^{-1}_x(\{x\})$（ただし$f_x$は$x$を右から足すという連続写像）　とかけることから、$T$が閉集合、すなわちコンパクトであることもわかる。以上より$T \in \mathcal{F} $である。これと$\mathcal{M}$の極小性より$\mathcal{M}=T$となる。ここで特に$T$において$y=x$とした場合を考えれば、$x+x=x$が分かる。以上より$\mathcal{M}$の任意の元はべき等元である。
(証明終)

$β \mathbb{N} $を用いたヒンドマンの定理の証明

ようやく全ての舞台が整ったのでヒンドマンの定理を証明していきます。まずは主張を次のように言い換えておきます。

こう言い換えてしまうとなんだか味気ない気もしますがまあ良いでしょう。
証明の方針としては、エリスの補題により存在が保証される$ β \mathbb{N} $のべき等元を用いて条件を満たす$X$を帰納的に構成していくといった感じです。やっていきましょう。
（証明）
$ β \mathbb{N} $のべき等元$p$を一つ取る。$p$が有限集合を要素に持つと仮定すると補題５より$p$は主超フィルターとなるが、このとき$p=p+p$より$ \mathcal{U}_{2n}= \mathcal{U}_n+\mathcal{U}_n= \mathcal{U}_n $となり、$n=2n$が導かれ、これを満たす自然数$n$は存在せず矛盾。よって$p$の任意の要素は無限集合である。

$\mathbb{N}$の部分集合$A$に対して$A*=\{n \in A|A-n \in p\}$と定める。$p$がべき等元であることより、$A \in p \Longrightarrow A \in p+p \Longrightarrow \{n \in \mathbb{N} |A-n \in p\} \in p \Longrightarrow A*=A \cap \{n \in \mathbb{N} |A-n \in p\} \in p$となるから、$A \in p \Longrightarrow A* \in p$が成り立つ。
さて、ある$C_k$が存在して$C_k \in p$となる。（$C_1$〜$C_n$がいずれも$p$に含まれなければ、$\mathbb{N}/C_1$〜$\mathbb{N}/C_n$の共通部分である$\emptyset$が$p$に含まれてしまい矛盾だから。）以下$C_k$$\in p$となる$C_k$を単に$C$と表す。$C \in p$より$C* \in p$である。
まず$C* \in p$から$C*$は無限集合だから$x_1 \in C*$がとれる。明らかに$FS(\{x_1\}) \subset C*$である。
いま$x_1〜x_m$が、互いに相異なりかつ$FS(\{x_1,,,,x_m\}) \subset C*$を満たすように構成できたとする。このとき、任意の$v \in FS(\{x_1,,,,x_m\})$に対して、$v \in C*$より$C-v \in p$となり、したがって$ C*-v=(C-v)* \in p$となる。
よって$C*\cap\bigcap_{v\in F}(C^*-v) \in p$より$C*\cap\bigcap_{v\in F}(C^*-v) $は無限集合だから$x_{m+1} \in C*\cap\bigcap_{v\in F}(C^*-v)$かつ$x_1〜x_m$のいずれとも相異なるような$x_{m+1}$がとれる。
このとき、$FS(\{x_1,,,,x_{m+1}\}) \subset C*$が成り立っている。
以上の手順により帰納的に$\mathbb{N}$の無限部分集合$X=\{x_1,x_2,,,,\}$を構成すれば$FS(X) \subset C* \subset C$となり$X$は条件を満たす。
（証明終）

以上で証明が完了しました！！おめでとうございます！！

最後に

いかがだったでしょうか。$β \mathbb{N} $という隠れた構造が実は組み合わせ論の問題で本質的な役割を果たしているというのは、化石を発掘しているみたいで個人的にはとても面白かったです。世の中にはまだまだこういう面白い構造がたくさん眠っているのかもしれないと思うと興奮します。最後までお読みいただきありがとうございました。