主張

\(n\,\)がどれくらい大きければ良いかは，ここで紹介する証明でははっきりさせることができません。

この\(\,n\,\)の値の大きさを知っている方は教えていただけると嬉しいです。

しかし

\(k\,\)が奇数なら\(\,n\leq \log_3 (k+1)\,\)

\(k\,\)が偶数なら\(\,n\leq \log_2 (k+2)-1\,\)

程度に\(\,n\,\)が小さいと，引き分けが発生することが分かっています^{参考図書\([1]\)}。

こちらの証明は簡単なので，要望があれば別の記事にしたいと思います。

定理の特別な場合として\(\,c=2\,\)人の場合を考えてみると，より強力なことが言えます。

証明はヘイルズ–ジューエットの定理より，\(\,n\,\)が十分に大きいとき引き分けは起こらないので，後は後手必勝ではないことが分かれば良いです。

後手必勝ではないことは戦略拝借論法より，簡単に示すことができるので証明完了です。

証明

証明はめちゃくちゃ難しいです。

この節以降で紹介している概念や命題の全てを理解する必要があるので，かなり大変です。

ここではこの節以降の解説を読んだという前提で証明を行います。

命題4において\(\,W=\{1,2,\ldots, k\},B=W\,\)として適用します。

このとき十分大きな\(\,n\,\)が存在して\(\,\mathscr{P}(W)\,\)は\(\,W^{n}\,\)において\(\,c\text{-}\)正則となります。

ここで

\(\,W^{n}=\{\,(i_1,i_2,\cdots,i_n)\,\,|\,\,1\leq i_j\leq k \,\}\,\)

なので，

\(W^{n}\,\)は\(\,n\,\)次元\(\,k\,\)目並べのフィールドとみなせます。

また\(\,W^{n}\,\)を\(\,c\,\)分割することは

フィールド\(\,W^{n}\,\)に\(\,c\,\)人が自分の色の石を置き続け，フィールドが埋まった状態を表しています。

この状態のときに\(\,\mathscr{P}(W)\,\)は\(\,c\text{-}\)正則であることから，

\(c\,\)人の中の誰かは\(\,\mathscr{P}(W)\,\)に含まれる石の配置\(\,S\,\)を実現していることになります。

そこでこの配置\(\,S\,\)について考えましょう。

\(S\in \mathscr{P}(W)\,\)より，機能的な写像\(\,f:W\to \displaystyle \bigcup_{n=1}^{\infty} W^{n}\,\)が存在して，\(\,S=f(W)\,\)と書けます。

最初は具体的に考えた方が説明しやすいので，

例として\(\,3\,\)次元\(\,4\,\)目並べで，\(\,f\,\)は組\(\,(1,t,2)\,\)によって機能性が保証されているとします。

このとき\(\,S=f(W)\,\)より，\(\,S\,\)は

\((1,t,2)\,\,(1\leq t\leq 4)\)

と表せられる点の連なりです。

明示して書けば

\((1,1,2),(1,2,2),(1,3,2),(1,4,2)\)

ということになります。

図示すれば，下のように\(\,4\,\)つ石が並んでいる配置になることが分かります。

一般に言えば\(\,S\,\)の元\(\,(s_1,s_2,\ldots, s_n)\,\)の成分\(\,s_i\,\)は\(\,t\,\)かそれ以外かになります。

\(t\,\)の成分だけ集めたものは\(\,t\vec{e}\,\)と書けます。

ただし\(\,\vec{e}\,\)は成分が\(\,0\,\)か\(\,1\,\)で，最低でも\(\,1\,\)が\(\,1\,\)回は登場するベクトルです(零ベクトルではないことが保証されます)。

それ以外の成分を集めたものを\(\,\vec{p_0}\,\)と書くことにすると，\(\,S\,\)は

\(\vec{p_0}+t\vec{e}\,\,(1\leq t\leq k)\)

と表される点の連なりです。

よって\(\,S\,\)は石が\(\,k\,\)個並んでいる配置を意味します。

以上より，\(\,c\,\)人のプレイヤーの中の誰かは勝利配置\(\,S\,\)を実現していることになります。

したがってプレイヤーの誰かは\(\,n\,\)次元\(\,k\,\)目並べでは勝利するので，ヘイルズ–ジューエットの定理は示されました。\(\quad\square\)

定義

この節以降はヘイルズ–ジューエットの定理の証明に必要な概念と命題を紹介していきます。

またこれから定義する正則性(regularity)，地方的(provincial)，機能的(functional)といった言葉は日本ではあまりメジャーではないので，注意してください。英語の方で覚えると良いかもしれません。

※ \(N\,\)分割として\(\,C_i=\emptyset\,\)の場合も認めます。

そのように考えれば\(\,N\,\)が自然数のときは，
\(\,N\,\)分割に\(\,\emptyset\,\)を付け加えることで，\(\,(N+1)\,\)分割とみなすことができるので，
\((N+1)\text{-}\)正則\(\,\Rightarrow\,\)\(\,N\text{-}\)正則が成り立つことが分かります。

分かりにくいので，\(N\,\)人で遊ぶ\(\,5\,\)目並べにおけるイメージで説明したいと思います。

以下のように考えましょう。

集合\(\,X\,\)\(\,\cdots\,\)石を置く場所の集合

\(X\,\)の\(N\,\)個の類への分割\(\,\cdots\,\)\(\,N\,\)人遊んで\(\,X\,\)の全ての場所に自分の色の石を置いた状態

集合系\(\,\mathscr{P}\,\)\(\,\cdots\,\)\(\,X\,\)内での勝利配置(\(\,5\,\)個連続して石が並ぶような場所)を集めたもの。

このイメージをもとに考えると，\(\,N\text{-}\)正則であるとは

盤上\(\,X\,\)の全てに石を置いたとき，\(\,N\,\)人の内の誰か一人は勝利している状態

となります。

正則で言う\(\,\exists C_k\exists S(\subset \mathscr{P}) : S\subset C_k\,\)という条件が，
\(C_k\,\)色(いろ)の石が勝利配置に並ぶのに対応することに気づけば分かりやすいと思います。

基本的な命題

それでは証明です。

うまいイメージが思いつかないので，そういうイメージがある方は教えていただけると嬉しいです。

\(C\,\)を\(\,|C|=N\,\)となるような集合としましょう。

このとき\(\,X\times Y\,\)の\(\,N\,\)分割は写像\(\,f:X\times Y\to C\,\)のことだと考えられます。

なぜなら\(\,f(a)=f(b)\,\)という同値関係による\(\,X\,\)の類別と\(\,X\,\)の\(\,N\,\)分割は\(\,1\,\)対\(\,1\,\)対応するからです。

この\(\,N\,\)分割とは写像\(\,f\,\)に付随する同値関係による類別と同じという考え方は，これから使っていくので覚えておいてください。

このとき\(\,Y\,\)の\(\,N^{M}\,\)分割\(\,g\,\)を次のように定義できます。

\(X\,\)から\(\,C\,\)への写像を集めた集合\(\,\mathfrak{F}(X,C)\,\)の濃度は\(\,|\mathfrak{F}(X,C)|=N^{M}\,\)となるので，
\(g:Y\to\mathfrak{F}(X,C)\,\)となるような写像\(\,g\,\)を定義できればOKです。

写像\(\,f\,\)を利用して\(\,y\in Y\,\)に対して，写像\(\,g\,\)を次のように定めます。

\(g(y)=f_y\)

ただし写像\(\,f_y:X\to C\,\)は\(\,f_y(x)=f(x,y)\,\)と定まるものします。

このようにして\(\,Y\,\)の\(\,N^{M}\,\)分割\(\,g\,\)が与えられたので，\(\,N^{M}\text{-}\)正則であることから

任意の\(\,y,y’\in Q\,\)について

\(f_y=f_{y’}\)

となるような\(\,Q(\not=\emptyset)\in \mathscr{Q}\,\)が存在します。

ある\(\,y_0\in Q\,\)を固定しましょう。

\(\,f_{y_0}:X\to C\,\)によって\(\,X\,\)は\(\,N\,\)分割を与えられるので，今度は\(\,N\text{-}\)正則であることから

任意の\(\,x\in P\,\)について

\(f_{y_0}(x)=c\)

となるような\(\,c\in C\,\)と\(\,P\in \mathscr{P}\,\)が存在します。

ここで\(\,f_{y_0}=f_y\,\,(\forall y\in Q)\,\)なので，上の式はさらに

任意の\(\,x\in P,y\in Q\,\)について

\(f_y(x)=c\)

だといえます。

\(f_y\,\)の定義より，これは任意の\(\,(x,y)\in P\times Q\,\)について

\(f(x,y)=p\)

が成り立つことを表すので，題意は示されました。\(\quad\square\)

定義

どうして地方性を定義したのかというと，次の命題が成り立つからです。

つまり地方性は正則性を保つということです。

しっかり命題2を証明しておきましょう。

再び\(\,C\,\)を\(\,|C|=N\,\)となるような集合として，\(\,Y\,\)の\(\,N\,\)分割\(\,g:Y\to C\,\)を考えましょう。

このとき合成写像\(\,g\circ f:X\to C\,\)は\(\,X\,\)の\(\,N\,\)分割となります。

要は\(\,Y\,\)の\(\,N\,\)分割から\(\,X\,\)の\(\,N\,\)分割を構成しています。

よって\(\,X\,\)における正則性から\(\,A\subset X\,\)かつ\(\,g(f(A))=\{c\}\,\)を満たすような\(\,A\in \mathscr{P},c\in C\,\)が存在します。

地方性より\(\,B\subset f(A)\,\)となるような\(\,B\in\mathscr{Q}\,\)が存在します。

この\(\,B\in\mathscr{Q}\,\)について，\(\,g(B)\subset g(f(A))=\{c\}\,\)つまり\(\,g(B)=\{c\}\,\)となるので，題意は示されました。\(\quad\square\)

基本的な命題

\(n\,\)に関する数学的帰納法で示していきましょう。

\(n=1\,\)のときは\(\,\mathscr{P}_1=\mathscr{P}\,\)であり，前提の条件から\(\,\mathscr{P}\,\)の正則性は言える^※ので，大丈夫です。

\(n-1\geq 1\,\)のとき成り立つと仮定して，\(\,n\,\)のときについて示していきましょう。

前提条件より任意の自然数\(\,k\,\)に対して\(\,X\,\)の有限部分集合\(\,S\,\)が存在して，\(\,\mathscr{P}\,\)は\(\,S\,\)において\(\,k\text{-}\)正則です。

ここで\(\,|S|=s\,\)とおくと(\(\,|S|\,\)の有限性の条件が効いています)，
\(\,n-1\,\)のときの仮定から\(\,\mathscr{P}_{n-1}\,\)は\(\,k^{s}\text{-}\)正則です。

命題1より\(\,\mathscr{P}\otimes\mathscr{P}_{n-1}\,\)は\(\,S\times X\,\)において\(\,k\text{-}\)正則です。

\(S\times X\subset X\times X\,\)なので，\(\,X\times X\,\)においても\(\,k\text{-}\)正則ということができます。

ここで写像\(\,f:X\times X\to X\,\)を\(\,f(x_1,x_2)=x_1x_2 \,\,(x_1,x_2\in X)\,\)として定めます。

すると\(\,f\,\)は\(\,\mathscr{P}\otimes\mathscr{P}_{n-1}\,\)と\(\,\mathscr{P}_n\,\)に関して地方的です。

なぜなら\(\,A\times A_1\cdots A_{n-1}\in \mathscr{P}\otimes\mathscr{P}_{n-1}\,\)に対して，
\(f(A\times A_1\cdots A_{n-1})=AA_1\cdots A_{n-1}\in \mathscr{P}_{n}\,\)となるからです。

よって命題2から任意の自然数\(\,k\,\)について，\(\,\mathscr{P}_n\,\)は\(\,X\,\)において\(\,k\text{-}\)正則であることが言えるので，\(\,n\,\)の場合についても示されました。

したがって数学的帰納法により題意は示されました。\(\quad\square\)

※ちなみに命題3の前提の

条件\(\,(1):\,\)任意の自然数\(\,k\,\)に対して\(\,X\,\)の有限部分集合\(\,S\,\)が存在して，\(\,\mathscr{P}\,\)は\(\,S\,\)において\(\,k\text{-}\)正則である

とこれと似ている

条件\(\,(2):\,\)\(\,\mathscr{P}\,\)は\(\,X\,\)において正則である。

の関係は「条件\(\,(1)\,\)\(\,\Rightarrow\,\)条件\(\,(2)\,\)」となります。

同値ではないことに注意しましょう。

\(\Rightarrow\,\)は次のように証明できます。

任意の\(\,k\in \mathbb{N}\,\)に対して存在する\(\,X\,\)の有限部分集合\(\,S(k)\,\)について，
包含写像\(\,i:S(k)\to X\,\)は\(\,\mathscr{P}\,\)に関して明らかに地方的です。

もっと分かりやすく言えば\(\,X\,\)の\(\,k\text{-}\)分割は\(\,S\,\)の\(\,k\text{-}\)分割とみなせるということです。

そのため命題2より，任意の\(\,k\in \mathbb{N}\,\)について\(\,\mathscr{P}\,\)は\(\,k\text{-}\)正則であることが示されるので，\(\,\Rightarrow\,\)は成り立ちます。

また逆の\(\,\Leftarrow\,\)が成り立たないことは次の反例によって分かります。

\(X=\mathbb{N}\,\)として，\(\,\mathscr{P}\,\)を\(\,X\,\)の無限部分集合を集めた集合系としましょう。

このとき任意の自然数\(\,k\,\)について\(\,X\,\)を\(\,k\,\)分割すると，\(\,X\,\)は無限集合なのでどこかの類は無限集合となります。

つまりどこかの類は\(\,\mathscr{P}\,\)の元を含むことになるということなので，条件\(\,(2)\,\)は満たされている状況だと分かります。

しかし条件\(\,(1)\,\)は明らかに満たされていません。

なぜなら\(\,S\,\)は有限集合であるため，\(\,\mathscr{P}\,\)の元を含むことはないからです。

以上により条件\(\,(1),(2)\,\)の関係が明らかになりました。

定義

元論文\([1]\)では，“functional”は名詞なので“機能的写像”と訳すのが正当かもしれませんが，煩わしいので形容詞的に訳しています。

分かりにくいので，具体例を通して確認しましょう。

例えば\(\,W=\{1,2,3,4\}\,\)のときに，\(\,f:W\to X\,\)の値が以下のようになっていたとします。

\(\,f(1)=11311211\,\)
\(\,f(2)=12322212\,\)
\(\,f(3)=13333213\,\)
\(\,f(4)=14344214\,\)

このとき\(\,f\,\)は機能的で，長さは\(\,8\,\)となります。

なぜなら\(\,W\cup \{t\}\,\)上の語\(\,1t3tt21t\,\)が存在して，各\(\,f(1),f(2),f(3),f(4)\,\)の値はこの\(\,1t3tt21t\,\)の\(\,t\,\)に\(\,W\,\)の元\(\,1,2,3,4\,\)をそれぞれ代入した値になっているからです。

次節ではこの関数の機能性と集合の正則性の結びつきに関する命題を確認していきます。

※\(\,W\,\)上の自由半群\(\,X\,\)とは\(\,W^{n}=\underbrace{W\times\cdots W}_{n個}\,\)という表記法を用いれば，
\(\,\displaystyle X=\bigcup_{n=1}^{\infty} W^{n}\,\)と表されます。つまり\(\,W\,\)の\(\,n\,\)次元空間を集めたものです。

\(W^{n}\,\)の元\(\,(\alpha_1,\cdots,\alpha_n)\,\)は記法を簡略化して\(\,\alpha_1\cdots\alpha_n\,\)と書くことにしています。

このように書いたものを“語”と呼びます(半群の場合のみ)。

また自由半群には下のような結合的な演算\(\,\ast\,\)が定められています。

\(\alpha_1\cdots\alpha_n,\,\,\beta_1\cdots\beta_m\in X\,\)について

\(\alpha_1\cdots\alpha_n\ast\beta_1\cdots\beta_m=\alpha_1\cdots\alpha_n\beta_1\cdots\beta_m\)

ただ\(\,2\,\)つの語をくっつけて\(\,1\,\)つの語にするだけですね。

基本的な命題

前節と同じ\(\,W\,\)を\(\,t\not \in W\,\)となるような集合，\(\,X\,\)を\(\,W\,\)の自由半群とした状況で，次の命題4が成り立ちます。

それでは証明です。一番大変です。

自然数\(\,k,c\,\)を固定し，命題4の主張を\(\,I_{k,c}\,\)とおくことにします。

この主張\(\,I_{k,c}\,\)を\(\,k,c\,\)に関する数学的帰納法で，任意の\(\,k,c\,\)に関して成り立つことを示せば良いです。

まず\(\,k=1\,\)の場合に成り立つことを確認しましょう。

この場合\(\,B\,\)は\(\,1\,\)元集合なので，\(\,c\,\)分割したときの類の一つは必ず\(\,B\,\)自身になります(逆にそれ以外の類は\(\,\emptyset\,\)となります)。

そのため\(\,B\in\mathscr{P}(B)\,\)を示せば良いです。

これは明らかで\(\,B\,\)の恒等写像\(\,\mathrm{id}_{B}:B\to X\,\)は長さ\(\,1\,\)で機能的だから，
\(\mathrm{id}_{B}(B)=B\in\mathscr{P}(B)\,\)となるからです。

また\(\,c=1\,\)のときは，\(\,B\,\)の\(\,1\,\)分割の類はもちろん\(\,B\,\)自身のみです。

そのため先ほどと同様に\(\,B\in\mathscr{P}(B)\,\)から，成り立つことが分かります。

さてここからは自然数\(\,n\gt 1, m\geq 1\,\)について
\(I_{n,m}\,\)と\(\,I_{n-1,c}\,(\forall c\in \mathbb{N})\,\)のとき成り立つと仮定して，\(\,I_{n,m+1}\,\)のときにも成り立つことを証明していきます。

\(I_{n,m+1}\,\)のときについて考えるために\(\,W\,\)の\(\,n\,\)元部分集合\(\,A\,\)を考えましょう。

まず仮定\(\,I_{n,m}\,\)より，ある自然数\(\,r\,\)が存在し\(\,\mathscr{P}(A)\,\)は\(\,A^r\,\)において\(\,m\text{-}\)正則となります。

次に仮定\(\,I_{n-1,c}\,(\forall c\in\mathbb{N})\,\)を使うために，適当な\(\,a\in A\,\)を固定して\(\,1\,\)元だけ減らした\(\,B=A-\{a\}\,\)について考えましょう。

仮定\(\,I_{n-1,c}\,(\forall c\in\mathbb{N})\,\)より，任意の自然数\(\,c\,\)に対して\(\,X\,\)の有限部分集合として\(\,B^{p}\,\)(\(\,p\,\)はある自然数)が存在して，\(\,\mathscr{P}(B)\,\)は\(\,B^{p}\,\)において\(\,c\text{-}\)正則です。

よって命題3より先ほどの自然数\(\,r\,\)について

\(\mathscr{P}_{r+1}(B)\coloneqq \{f_0(B)f_1(B)\cdots f_r(B)\,|\,f_i\)は機能的\(\,\}\,\)

は\(\,X\,\)において\(\,(m+1)\text{-}\)正則です。

\( \displaystyle \bigcup_{s=1}^{\infty}B^{s}\subset X\,\)と\(\,\mathscr{P}_{r+1}(B)\,\)の元は\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)に含まれることから

これは\(\,\mathscr{P}_{r+1}(B)\,\)は\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)において\(\,(m+1)\text{-}\)正則であることに読み替えられます。

なぜなら\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\subset X\,\)より\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)の分割を適当に\(\,X\,\)の分割まで拡大でき，

\(\mathscr{P}_{r+1}(B)\,\)の元は\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)に含まれることから，\(\,X\,\)の正則性を示す包含関係を\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)の正則性を示す包含関係に読み替えられるからです。

\(\mathscr{P}_{r+1}(B)\,\)の\(\displaystyle \,\bigcup_{s=1}^{\infty}B^{s}\,\)における\(\,(m+1)\text{-}\)正則性から，

ある自然数\(\,q\,\)が存在して\(\,\mathscr{P}_{r+1}(B)\,\)が\(\,B^{q}\,\)において\(\,(m+1)\text{-}\)正則となることを示しましょう。

背理法により示すため，
任意の自然数\(\,s\,\)について\(\,\mathscr{P}_{r+1}(B)\,\)が\(\,B^{s}\,\)において\(\,(m+1)\text{-}\)正則とならないと仮定します。

\((m+1)\text{-}\)正則とはならないので，\(\,C\,\)を\(\,|C|=m+1\,\)となる集合とおくと

各\(\,s\,\)と，任意の\(\,c\in C\,\)について\(\,g_{s}^{-1}(c)\,\)が\(\,\mathscr{P}_{r+1}(B)\,\)の元を含まないような\(\,(m+1)\,\)分割\(\,g_s:B^{s}\to C\,\)が存在します。

これを利用して\(\,(m+1)\,\)分割\(\,g:\displaystyle \bigcup_{s=1}^{\infty}B^{s}\to C\,\)を次のように構成します。

\(\displaystyle x\in \bigcup_{s=1}^{\infty}B^{s}\,\)に対して，各\(\,B^{s}\,\)は互いに素より\(\,x\in B^{s}\,\)となるような自然数\(\,s\,\)がただ一つ定まります。

この\(\,s\,\)を利用して\(\,g(x)\coloneqq g_s(x)\,\)と定めます。

\((m+1)\,\)分割\(\,g\,\)が与えられたので，\(\,\mathscr{P}_{r+1}(B)\,\)の\(\,\displaystyle \bigcup_{s=1}^{\infty}B^{s}\,\)における\(\,(m+1)\text{-}\)正則性から，

\(P\subset g^{-1}(c)\,\)となるような\(\,c\in C,\,P\in\mathscr{P}_{r+1}(B)\,\)が存在します。

ここで\(\,P\in \mathscr{P}_{r+1}(B)\,\)より\(\,P=f_0(B)\cdots f_r(B)\) (\(f_i\)は機能的)と書けます。

\(f_i\,\)の長さを\(\,l_i\,\)とおき，\(\,l=l_0+\cdots+l_r\,\)とすれば\(\,P=f_0(B)\cdots f_r(B)\subset B^{l}\,\)です。

つまり\(\,P\,\)と共通部分を持つ\(\,B^{s}\,\)はただ一つです。

このことと，\(g\,\)の定義より\(\,P\subset g^{-1}(c)=\displaystyle \bigcup_{s=1}^{\infty} g_{s}^{-1}(c)\)であることから

ある\(\,s\,\)について，\(\,P \subset g_{s}^{-1}(c)\,\)と言えます。

これは\(\,g_s\,\)の構成方法に矛盾するので，

背理法により，ある自然数\(\,q\,\)が存在して\(\,\mathscr{P}_{r+1}(B)\,\)が\(\,B^{q}\,\)において\(\,(m+1)\text{-}\)正則となることが示されました。

さて，ここまでで示したことを用いて\(\,I_{n,m+1}\,\)の場合にも成り立つことを証明しましょう。

\((m+1)\text{-}\)正則性を考えるために，\(\,A^{q}=C_0\cup C_1\cup \cdots \cup C_m\,\)と\(\,(m+1)\,\)分割します。

\(A\supset B\,\)より，これは\(\,B^{q}\,\)の\(\,(m+1)\,\)分割を与え，\(\,\mathscr{P}_{r+1}(B)\,\)の\(\,B^{q}\,\)における\(\,(m+1)\text{-}\)正則性から

機能的な\(\,g_0,g_1,\ldots,g_r\,\)が存在して，\(\,g_0(B)g_1(B)\cdots g_r(B)\subset B^{q}\,\)はその類のどれかに含まれます。

必要なら番号を変えて\(\,g_0(B)\cdots g_r(B)\subset C_0\,\)とします。

\(g_i(A)\,\)の元は機能性より\(\,t\,\)の部分に\(\,A\,\)の元を代入するだけなので，\(\,B\subset A\,\)より\(\,g_0(A)g_1(A)\cdots g_r(A)\subset A^{q}\,\)です。

ここで写像\(\,\phi:A^{r}\to g_0(a)g_1(A)\cdots g_r(A)\,\)を下の式で定めます。

\(\phi(w_1w_2\cdots w_r)=g_0(a)g_1(w_1)\cdots g_r(w_r)\)

この\(\,\phi\,\)は\(\,\mathscr{P}(A)\,\)に関して地方的です。

以下でこの理由を説明します。

\(S\subset A^{r}\,\)かつ\(\,S\in \mathscr{P}(A)\,\)を満たす\(\,S\,\)が存在したとしましょう。

すると\(\,S\in \mathscr{P}(A)\,\)より，ある機能的な写像\(\,f:W\to X\,\)を用いて\(\,S=f(A)\,\)と書けます。

このことは厳密な書き方ではないのですが，\(\,S=w_1\cdots t\cdots w_r\,\)と書けるということです。

そのため\(\,\phi(S)=g_0(a)g_1(w_1)\cdots g_i (t)\cdots g_r(w_r)\,\)と表せます。

各\(\,g_1,\ldots,g_r\,\)は機能的なので，\(\,\phi(S)\,\)のどこかしらには\(\,g_i(t)\,\)のように\(\,t\,\)が出現する箇所が存在します。

そのため\(\,\phi(S)=h(A)\,\)となるような機能的な写像\(\,h\,\)を構成することができるので，地方的になるというわけです。

\(r\,\)の取り方より，\(\,\mathscr{P}(A)\,\)は\(\,A^{r}\,\)において\(\,m\text{-}\)正則なので，
命題2から\(\,g_0(a)g_1(A)\cdots g_r(A)\,\)においても\(\,m\text{-}\)正則です。

もし\(\,C_0\cap g_0(a)g_1(A)\cdots g_r(A)=\emptyset\,\)なら，\(\,C_1,\ldots,C_m\,\)により\(\,g_0(a)g_1(A)\cdots g_r(A)\,\)を\(\,m\,\)分割できます。

\(\mathscr{P}(A)\,\)の\(m\text{-}\)正則性より，\(\,C_1,\ldots,C_m\,\)のどれかの類に\(\,\mathscr{P}(A)\,\)の元が含まれるので，この場合\(\,I_{n,m+1}\,\)は成り立ちます。

そこで\(\,C_0\cap g_0(a)g_1(A)\cdots g_r(A)\not=\emptyset\,\)の場合を考えましょう。

この場合

\(x=g_0(a)g_1(a_1)\cdots g_r(a_r)\)

という\(\,x\in C_0\,\)が存在しますね。この\(\,x\,\)を利用して，正則性の条件を満たしてることを証明していきます。

\(x=v_1v_2\cdots v_q\in A^{q}\,\)という表示に変え，次のように\(\,A\cup \{t\}\,\)上の語\(\,\alpha=\alpha_1\alpha_2\cdots\alpha_q\,\)を定義します。

\(\alpha_i=\begin{cases}\,v_i&(v_i\in B)\\ \,t&(v_i=a)\end{cases}\)

つまり\(\,x\,\)の\(\,a\,\)の部分を\(\,t\,\)に変えたものが\(\,\alpha\,\)ということです。

このとき\(\,x\,\)の中の\(\,g_0(a)\,\)には\(\,g_0\,\)が機能的であることから，少なくとも一回\(\,g_0(a)\,\)には\(\,a\,\)が出現します。

これは\(\,\alpha\,\)に\(\,t\,\)が少なくとも一回は\(\,t\,\)が出現することを意味します。

よって\(\,\alpha\,\)から機能的な\(\,g:W\to X\,\)を自然に構成することができます。

この\(\,g\,\)について，その構成法から

\(g(a)=x\)

です。

また構成法より\(\,g(B)\subset g_0(B)g_1(B)\cdots g_r(B)\subset C_0\,\)を満たすことも分かります(二つ目の包含関係はそうなるように\(\,C_0\,\)を選んでいたから)。

さらに\(\,g(A)=g(B)\cup\{g(a)\}\,\)で，\(\,g(a)=x\in C_0\,\)でもあるので，\(\,g(A)\subset C_0\,\)も得られます。

\(g(A)\in \mathscr{P}(A)\,\)なので，\(\,I_{n,m+1}\,\)が成り立つことが示されました。

したがって数学的帰納法より題意は示されました。\(\quad\square\)

今回の記事ではヘイルズ–ジューエットの定理(Hales–Jewett theorem)を解説いたしました。

定理の主張は簡単でしたけど，証明はものすごく大変でしたね(これでも元論文\([1]\)よりは解説を丁寧にしたつもりです)。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) Hales, A. W., and R. I. Jewett. “Regularity and Positional Games.” Transactions of the American Mathematical Society, vol. 106, no. 2, 1963, pp. 222–29. JSTOR, https://doi.org/10.2307/1993764. Accessed 14 Mar. 2025.