van der Waerden Theorem and Ramsey Theorem

この文章ではvan der waerdenの定理とRamseyの定理を証明し，コンパクト性原理とも呼ばれるRadoの選択定理を紹介する．

1 van der Waerden’s Theorem

このセクションでは特に断らない限りは，自然数$a,b$について$[a,b]=\{x\in \mathbb{N}\mid a\le x\le b\}$とする．

二つの$m$対 $(x_i),(y_i)\in {[0,l]}^m$が$l$-同値であるとは，値が$l$であるような最後の番号までこの二つが一致していることとする．つまり，

$$\forall j\in \{n\mid x_n=l\}\cup \{n\mid y_n=l\}\forall i\le j{x}_i=y_i$$

この同値類による代表元は$(\ast ,\ast ,\mathrm{\dots },\ast ,l,0,0,\mathrm{\dots },0)$という形のものを選べる．

任意の$m,l\in {\mathbb{N}}_{+}$に対して，次の主張を$S(l,m)$とかこう： 任意の$r\in {\mathbb{N}}_{+}$に対して$N(l,m,r)\in \mathbb{N}$が存在して， 任意の写像$[1,N(l,m,r)]\to [1,r]$ に対して$a,d_1,d_2,\mathrm{\dots },d_m$が存在し， 任意の$(x_i)\in {[0,l]}^m$に対して $a+{\sum }_{i=1}{x}_i{d}_i\le N(l,m,r)$であり，かつ $C(a+{\sum }_{i=1}{x}_i{d}_i)$は$l$-同値類上で定数となる．

補題 1.

$S(l,1)$と$S(l,m)$が成立するならば，$S(l,m+1)$が成立する．

証明.

$r$を固定する．$M=N(l,m,r)$とし，$N=N(l,1,r^M)$とする． そして，写像$C:[1,MN]\to [1,r]$が与えられているとする． さてこのとき，写像$D:[1,N]\to {[1,r]}^M\cong [1,r^M]$ を以下のように定義する．$g,h\in [1,N]$について$D(g)=D(h)$とは 任意の$j\in [0,M-1]$について

$$C(gM-j)=C(hM-j)$$

が成り立つこととする． $N$の定義から，ある$q,k\in {\mathbb{N}}_{+}$が存在して 任意の$x\in [0,l-1]$について $q+xk\le N$であり， $D(q+xk)$が定数となる． さて，$S(l,m)$を区間$[(q-1)M+1,qM]$ に対して適応する．すると，ある$a,d_1,\mathrm{\dots },d_m\in {\mathbb{N}}_{+}$ が存在して， $a+{\sum }_{i=1}^m{x}_i{d}_i\in [(q-1)M+1,qM]$であり， $C(a+{\sum }_{i=1}^m{x}_i{d}_i)$は$l$-同値類上で定数になる． $q,k$の定義から 任意の $x\in [0,l-1]$について

$$D(q+xk)=D(q)$$

が成り立ち，このことと$D$の定義から任意の$b\in [1,M]$について

$$C((q-1)M+b+xkM)=C((q-1)M+b)$$

が成り立つ． 次に$d_{m+1}=kM$ として，$a,d_1,\mathrm{\dots },d_m,d_{m+1}$が求める条件を満たすことを確めよう．任意に$(x_i)\in {[0,l]}^{m+1}$とすると，

$$a+\sum _{i=1}^{m+1}{x}_i{d}_i\le a+\sum _{i=1}^m{x}_i{d}_i+x_{m+1}k{d}_{m+1}\le qM+lkM=(q+lk)M\le MN$$

である． 任意に$(x_i)\in {[0,l]}^{m+1}$をとる．

Case1 のとき， $a+{\sum }_{i=1}^m{x}_i{d}_i\in [(q-1)M+1,qM]$と 先に示したことから，

$$C\left(a+\sum _{i=1}^m{x}_i{d}_i+x_{m+1}{d}_{m+1}\right)=C\left(a+\sum _{i=1}^m{x}_i{d}_i\right)$$

となるので，$l$-同値類の上で定数となる．

Case2 $x_{m+1}=l$のとき．このときは$(x_i)$の$l$-同値類は一個しかないから証明することは何もない．

以上で補題が示された． ∎

以下では一般に${\sum }_{i=1}^0{f}_i=0$であることに注意せよ．

補題 2.

任意の$ｍ$について$S(l,m)$が成立するならば， $S(l+1,1)$が成立する．

証明.

$r$を固定する． 簡単のために$N=N(l,r,r)$とする． さて，任意に$C:[1,2N]\to [1,r]$をとる． すると，$a,d_1,\mathrm{\dots },d_r$が存在して 任意の$(x_i)\in {[0,l]}^r$について $a+{\sum }_{i=1}^r{x}_i{d}_i\le N$であり， $C(a+{\sum }_{i=1}^r{x}_i{d}_i)$は$l$-同値類上で定数となる．

$w\in [0,r]$について

$$C\left(a+\sum _{i=1}^{w}l{d}_i\right)$$

を考えよう．彩色は$r$個で，$[0,r]$は$r+1$個あるので，ある $u,v\in [0,r]$が存在してと

$$C\left(a+\sum _{i=1}^{u}l{d}_i\right)=C\left(a+\sum _{i=1}^{v}l{d}_i\right)$$

である． $x\in [0,l]$を任意に与える，のときには $(l,\mathrm{\dots },l,x,\mathrm{\dots },x)$は$(l,\mathrm{\dots },l,0\mathrm{\dots },0)$と $l$-同値なので

$$C\left(\left(a+\sum _{i=1}^{u}l{d}_i\right)+x\left(\sum _{i=u+1}^v{d}_i\right)\right)=C\left(a+\sum _{i=1}^{u}l{d}_i\right)$$

また， $x=l$のときは $C(a+{\sum }_{i=1}^{u}l{d}_i)=C(a+{\sum }_{i=1}^{v}l{d}_i)$ なので， $q=(a+{\sum }_{i=1}^{u}l{d}_i)$, $k=(a+{\sum }_{i=1}^{v}l{d}_i)$ として，$S(l+1,1)$の成立がわかる． ∎

以上の補題から次のことがわかる．

定理 3.

任意の$l,m\in {\mathbb{N}}_{+}$について，$S(l,m)$が成り立つ．

van der Waerdenの定理とは次の主張のことである．

定理 4 (van der Waerden theorem).

任意の$l,r\in {\mathbb{N}}_{+}$に対して$n(l,r)\in {\mathbb{N}}_{+}$が存在して， 任意の$C:[1,n(l,r)]\to [1,r]$ に対してある$w\in [1,r]$が存在して，$C^{-1}(w)$は 長さ$l$の等差数列を含む．

このvan der Waerdenの定理は$\forall l\in {\mathbb{N}}_{+}S(l,1)$が成り立つというのと同値であるから，上の定理から成立がすぐにわかる． $m$という補助パラメーターを用いて，証明を簡略化しているのである．

系 5 (infinite van der Waerden theorem).

任意の$r\in {\mathbb{N}}_{+}$と任意の彩色$C:{\mathbb{N}}_{+}\to [1,r]$ についてある$w\in [1,r]$が存在して$C^{-1}(w)$ は任意の長さの等差数列を含む．ここで，等差は一定でなくて良い．

証明.

彩色$C$に対して次のように集合を定義する．

$$S=\{(l,n,w)\in {\mathbb{N}}_{+}\times {\mathbb{N}}_{+}\times [1,r]\mid C^{-1}(w)\cap [1,n]\text{は長さ}l\text{の等差数列を含む}\}$$

van der Weardenの定理より，任意の$l$について$(n,w)\in {\mathbb{N}}_{+}\times [1,r]$ が存在して$(l,n,w)\in S$である．特に$S$は無限集合である． また写像$p:S\to {\mathbb{N}}_{+};(l,n,w)\mapsto l$は全射である． そして写像$q:S\to [1,r];(l,n,w)\mapsto w$ を考えると，$S$が無限集合であることと，$p$が全射であることから ある$w\in [1,r]$について$p(q^{-1}(w))$は無限集合である． また，$(l,n,w)\in S$ならばとなる$m$ について$(m,n,w)\in S$なので， $p(q^{-1}(w))$が無限集合となる$w\in [1,r]$について， $C^{-1}(w)$は任意の長さの等差数列を含む． ∎

2 Ramsey’s Theorem

集合$S$と基数$n$について${[S]}^n$で$S$の濃度$n$の部分集合全体を表すことにする．

基数$\kappa$, $n$, $c$, $\lambda$について， 任意の彩色$\mathrm{\Gamma }:{[\kappa ]}^n\to c$について，濃度$\lambda$の$\kappa$の部分 集合$M$が存在して，${\mathrm{\Gamma }|}_{{[M]}^n}$が定数となるという命題を $\kappa \to {(\lambda )}_c^n$で表すことにする． この文章では特に$\kappa$, $\lambda$が高々可算基数の場合を取り扱う． つまり古典的なラムゼーの定理である．

2.1 Infinite Ramsey Theorem

明らかに次がわかる．

補題 6.

${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^1$

まず最初に$n$について帰納法を回せることを示す．

補題 7.

$n\ge 2$について ${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$ならば ${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^{n+1}$

証明.

今 ${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$ が正しいとする．

$A$を加算集合とする．$\mathrm{\Gamma }:{[A]}^{n+1}\to c$を色付けとする． 任意の$x$について，${\mathrm{\Gamma }}_x:{[A\setminus \{x\}]}^n\to c$を以下のように定義する．$S\in {[A]}^n$について

$${\mathrm{\Gamma }}_x(S)=\mathrm{\Gamma }(S\cup \{x\})$$

帰納的に集合列$S_k$と列 $\{x_k\}$と 関数列$v_k:k\to c$を構成していく． まず $S_0=A$とし，$x_0$は$A$の適当な元とする．$v_0$ は空写像である．

一般に$k$まで$S_k$と$x_k$と$v_k$が定義されたときに $S_{k+1}$は$A\setminus \{x_k\}$の部分集合で ${\mathrm{\Gamma }}_{x_k}$について同色なものとする． $x_{k+1}$は$S_{k+1}$の適当な元とし ${v_{k+1}|}_k=v_k$と定義し， $v_{k+1}(k)$は$S_{k+1}$の色とする．

さて，$v:{\omega }_0\to c$を$v(k)=v_{k+1}(k)$ と定義する．このとき$v$は$0,1,\mathrm{\dots },c-1$の値のうちどちらを無限回とる．（これは${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^1$ということでもある．） 一般性を失うことなく$0$がそうであるとしてもよい．

$$B=\{x_k\mid v(k)=0\}$$

と定義する．$B$は加算集合である． ここで，を任意にとる． $S_m$の定義から，$x_{k_1}\mathrm{\dots },x_{k_n}\in S_{k+1}$ であり，$v(k)=0$から

$${\mathrm{\Gamma }}_{x_{k_0}}(\{x_{k_1},\mathrm{\dots }{x}_{k_n}\})=\mathrm{\Gamma }(\{x_{k_0},\mathrm{\dots }{x}_{k_n}\})=0$$

$k_0,\mathrm{\dots },k_n$は任意であったから つまり，$\mathrm{\Gamma }$は${[B]}^n$は$0$の値しか取らない． ∎

以上から次の定理がわかる．

定理 8 (Ramsey’s Theorem).

$n,c\in {\mathbb{N}}_{+}$とすると ${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$が成り立つ．

2.2 Finite Ramsey Theorem

任意の$n,c,a_0\mathrm{\dots },a_{c-1}\in {\mathbb{N}}_{+}$について 次の言明を${\mathrm{MRam}}_c^n(a_0,\mathrm{\dots },a_{c-1})$で表す． ある$r\in {\mathbb{N}}_{+}$が存在して，$r\le N$となる任意の$N$と， 任意の彩色$\mathrm{\Gamma }:{[N]}^n\to c$に対して ある$i\in c$と$A\subset N$が存在して$a_i\le |A|$かつ $\mathrm{\Gamma }({[A]}^n)=i$を満たす．

任意の$n,c,a\in {\mathbb{N}}_{+}$について 次の言明を${\mathrm{Ram}}_c^n(a)$で表す． ある$r\in {\mathbb{N}}_{+}$が存在して，$r\le N$となる任意の$N$と， 任意の彩色$\mathrm{\Gamma }:{[N]}^n\to c$に対して $A\subset N$が存在して$a\le |A|$かつ $\mathrm{\Gamma }({[A]}^n)$は定数である．

定義から直ちに次のことがわかる．

補題 9.

$$\forall n\forall c\forall a_0\mathrm{\dots }\forall a_{c-1}({\mathrm{Ram}}_c^n(\max \{a_0,\mathrm{\dots },a_{c-1}\})⟹{\mathrm{MRam}}_c^n(a_0,\mathrm{\dots },a_{c-1}))$$

我々が示すべき命題は次である．

定理 10 (Finite Ramsey Theorem).

$$\forall n\forall c\forall a{\mathrm{Ram}}_c^n(a)$$

証明.

${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$の成立と 背理法で示す．

$$\exists n\exists c\exists a\neg {\mathrm{Ram}}_c^n(a)$$

を仮定する．

ここで，$\neg R_c^n(a)$とは次の言明のことである． 任意の$r\in {\mathbb{N}}_{+}$に対して，ある$r\le N$と彩色 $\mathrm{\Gamma }:{[N]}^n\to c$が存在して， どんなを満たす$A\subset N$も $\mathrm{\Gamma }({[A]}^n)$は定数にならない．

よって，次のような短調増加列${\{N_i\}}_{i\in \mathbb{N}}$と 彩色${\mathrm{\Gamma }}_i:{[N]}^n\to c$が存在する． 任意の$i$について， どんなを満たす$A\subset N_i$も $\mathrm{\Gamma }({[A]}^n)$は定数にならない．

今全単射$z:\mathbb{N}\to {[\mathbb{N}]}^n$ を考える． ${\mathrm{\Gamma }}_i$たちのコドメインは有限集合なので 次のような $\mathbb{N}$の無限部分集合${\{m(i,0)\}}_j$が存在する． 任意の$i$について$0\in N_{m(i,0)}$であり， ${\mathrm{\Gamma }}_{m(i,0)}(z(0))$ は同じ値．

帰納的に$\{m(i,k)\}$が構成されたときに その可算部分集合$\{m(i,k+1)\}$ を以下を満たすものとして定義する． 任意の$i$について$k+1\in m(i,k+1)$であり， ${\mathrm{\Gamma }}_{m(i,k+1)}(z(k+1))$は単色．

さて，$\mathrm{\Gamma }:{[\mathbb{N}]}^n\to c$ を以下のように定義する． $e\in {[\mathbb{N}]}^n$について $\mathrm{\Gamma }(e)={\mathrm{\Gamma }}_{m(z^{-1}(e),z^{-1}(e))}(e)$ と定義する． このとき${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$が成立するので， ある無限集合$A\subset \mathbb{N}$が存在して $\mathrm{\Gamma }({[A]}^n)$は単色となる． 有限集合$S\subset A$を$|S|=a$となるように適当に取る． そして，$m(i,i)$をとなるように取る． $m(i,j)$の定義から， ${\mathrm{\Gamma }|}_{N_{m(i,i)}}={\mathrm{\Gamma }}_{m(i,i)}$ である．さて，$S$はその定義の仕方から${\mathrm{\Gamma }}_{m(i,i)}({[S]}^n)$ が定数になり，$S\subset N_{m(i,i)}$となる． これは$Ni$の定義に反するので，背理法により定理が証明された． ∎

3 Compactness Principle

上の方法と同じだが， このセクションではRadoの選択原理を用いて 無限ラムゼーの定理から有限ラムゼーの定理を証明する． また，無限van der Waerdenの定理から有限版を導く．

定理 11 (Rado’s selection principle).

族${\{A_i\}}_{i\in I}$を有限集合の族とする． また， は任意の $J_1,J_2\in 𝒫$に対してある$J_3\in 𝒫$ が存在して$J_1\cup J_2\subset J_3$を満たすとする． 各$J\in 𝒫$について $f_J\in {\prod }_{i\in J}{A}_i$が与えられているとする． このとき，$F\in {\prod }_{i\in I}{A}_i$が存在して， 任意の$J\in 𝒫$に対して$K\in 𝒫$ が存在して $J\subset K$と$F|J=f_K|J$ を満たす．

証明.

チコノフの定理から${\prod }_{i\in I}{A}_i$ は離散空間の直積空間としてコンパクトである． 各$J\in 𝒫$について

と定義する．$E_J$ は非空である．　 これが閉集合であることを示そう． $g\notin E_J$とする．このとき任意の$J\subset K$について ${g|}_J\ne {f_K|}_J$である． さて，$O=\{h\in {\prod }_{i\in I}\mid f|J=g|J\}$ とすると，$J$は有限集合なので$O$開集合である． 定義から$O\cap E_J=Ø$なので，$E_J$が閉集合であることがわかる． また，$J_1\cup J_2\subset J_3$となる$𝒫$の元 の三つ組に対して $E_{J_3}\subset E_{J_1}\cap E_{J_2}$ なので，$\{E_J\}$は有限交叉性を持ち，よってコンパクト性から ${\bigcap }_J{E}_J\ne Ø$となる． $F\in {\bigcap }_J{E}_J$を取れば，これは求める性質を持つ．

∎

Proof finite Ramsey theorems from infinite Ramsey theorem.

背理法で示す．

$$\exists n\exists c\exists a\neg {\mathrm{Ram}}_c^n(a)$$

を仮定する．

ここで，$\neg {\mathrm{Ram}}_c^n(a)$とは次の言明のことである． 任意の$r\in {\mathbb{N}}_{+}$に対して，ある$r\le N$と彩色 $\mathrm{\Gamma }:{[N]}^n\to c$が存在して， どんなを満たす$A\subset N$も $\mathrm{\Gamma }({[A]}^n)$は定数にならない．

よって，次のような短調増加列${\{N_i\}}_{i\in \mathbb{N}}$と 彩色${\mathrm{\Gamma }}_i:{[N]}^n\to c$が存在する． 任意の$i$について， どんな$a\le |A|$を満たす$A\subset N_i$も $\mathrm{\Gamma }({[A]}^n)$は定数にならない．

$I={[\mathbb{N}]}^n$とし， $A_i=c$と定義し， $𝒫=\{{[N_i]}^n\mid i\in \mathbb{N}\}$ とする．このとき $f_{{[N_i]}^n}:{[N_i]}^n\to c$を $f_{{[N_i]}^n}(e)={\mathrm{\Gamma }}_i(e)$と定義する． するとRado’s selection principle から $\mathrm{\Gamma }:{[\mathbb{N}]}^n\to c$が存在し， 任意の$N_i$について， が存在し$\mathrm{\Gamma }|{[N_i]}^n={\mathrm{\Gamma }}_k|{[N_i]}^n$ が成り立つ． さて，${\mathrm{\aleph }}_0\to {({\mathrm{\aleph }}_0)}_c^n$が成り立つので， ある$S\subset \mathbb{N}$が存在して$\mathrm{\Gamma }({[S]}^n)$は定数になる． $S$の部分集合$A$を$a\le |A|$となるようにとる． 次にとなる$N_i$をとる． すると，$\mathrm{\Gamma }|{[N_i]}^n={\mathrm{\Gamma }}_k|{[N_i]}^n$ なので，${[N_k]}^n$の部分集合で，${\mathrm{\Gamma }}_k({[A]}^n)$ が定数で，$a\le |A|$となるものは存在しないはずなので，これは矛盾である．よって有限Ramseyの定理が成り立つ． ∎

Proof finite van der Waerden theorems from infinite one.

無限van der Waerdenの定理を仮定して有限のそれを証明する． 有限van der waerdenの定理が成り立たないとする．つまり， ある$l,r\in {\mathbb{N}}_{+}$が存在して任意の$n\in {\mathbb{N}}_{+}$に対してある彩色$C_n:[1,n]\to [1,r]$が存在してどんな$w\in [1,r]$についても$C_n^{-1}(w)$が長さ$l$の等差数列を含まないとする． $I={\mathbb{N}}_{+}$とし とおく． また，$i\in I$に対して$A_i=[1,r]$とする． 各$[1,n]\in 𝒫$について $f_{[1,n]}:[1,n]\to [1,r]=A_i$を $f_{[1,n]}=C_n\in {\prod }_{i\in [1,n]}{A}_i$と定義する． このときRado’s selection principleより，ある$F\in {\prod }_{i\in I}{A}_i$つまり， 写像$F:{\mathbb{N}}_{+}\to [1,r]$が存在して 任意の$[1,n]\in 𝒫$に対して$[1,k]\in 𝒫$が存在して $[1,n]\subset [1,k]$と${F|}_{[1,n]}={f_{[1,k]}|}_{[1,n]}={C_k|}_{[1,n]}$ が成り立つ．$F$は${\mathbb{N}}_{+}$の彩色なので，infinite van der Waerdenの定理から，ある $w\in [1,r]$が存在して$F^{-1}(w)$は任意の長さの等差数列を含む． 特に長さ$l$の等差数列${\{a_i\}}_{i=1}^l$を含む． $N$を${\{a_i\}}_{i=1}^l\subset [1,N]$となるように大きくとると， $F$の取り方から$N\le K$となる$K$が存在して${F|}_{[1,K]}={C_K|}_{[1,N]}$ となる．これは$C_K^{-1}(w)$が長さ$l$の等差数列を含むということだから矛盾する．よって有限van der Waerdenの定理が成り立つ．

∎

4 おまけ：帰納法による有限ラムゼーの定理の証明

定義 12.

任意の$n,c,a\in {\mathbb{N}}_{+}$について，$R_c^n(a)$で， $R_c^n(a)\to {(a)}_c^n$を成り立たせる最小の正の自然数とする． もちろんまだ存在するかどうかは知らないとする． もし，$l\to {(a)}_c^n$ならば，$R_c^n(a)$は存在するし， $R_c^n(a)\le l$である．

鳩の巣原理から次がわかる．

定理 13.

任意の$n,c,a\in {\mathbb{N}}_{+}$について $ac\to {(a)}_c^1$ つまり$R_c^1(a)\le ac$.

補題 14.

当たり前だが，$R_c^n(a)\ge a$である．

定理 15.

任意の$n,k,a\in {\mathbb{N}}_{+}$について次がわかる． もし$R_k^n(a)$が存在し， かつ$R_2^n(R_k^n(a))$が存在するなら $R_{k+1}^n(a)$も存在し， $R_{k+1}^n(a)\le R_2^n(R_k^n(a))$ を満たす．

証明.

$N\le R_2^n(R_k^n(a))$ とし， $\mathrm{\Gamma }:{[N]}^n\to k+1$を彩色とする． そして$r\in k+1$を適当にとり，新たに彩色$\mathrm{\Delta }:N\to 2$を

と定義する． $N\le R_2^n(R_k^n(a))$なので， ある$N$の部分集合$A$で $\mathrm{\Delta }({[A]}^n)$が定数であって，$\mathrm{card}(A)=R_k^n(a)$ となる．もし$\mathrm{\Delta }({[A]}^n)$の値が$1$ならば，$\mathrm{\Gamma }({[A]}^n)=\{r\}$で， $\mathrm{card}(A)=R_k^n(a)\ge a$なので，証明は終わる． もし$\mathrm{\Delta }({[A]}^n)=0$ならば ${\mathrm{\Gamma }|}_{{[A]}^n}:{[A]}^n\to k$とみなせるので， $\mathrm{card}(A)=R_k^n(a)$からさらに$A$の部分集合$B$で$\mathrm{card}(B)\ge a$であり，$\mathrm{\Gamma }({[B]}^n)$が定数であるものが存在する．これで証明が終わる． ∎

定理 16.

もし$n$を任意に与える． もし任意の$x\in {\mathbb{N}}_{+}$について$R_2^n(x)$が存在するならば， $R_2^{n+1}(a)$も存在し， $R_2^{n+1}(a)\le {(R_2^n)}^{2a}(a)=R_2^n(R_2^n(\mathrm{\dots }{R}_2^n(a)))$ を満たす．

証明.

${(R_2^n)}^{2a}(a)\le N$ とする． 帰納的に $N_i$で$N_i\subset N$かつ$|N_i|\ge {(2R_2^n)}^{2a-i}(a)$, $x_i\in N_i$と $v_i:i\to 2$ $(i\in 2a)$ を構成しいていく． まず$N_0=N$とし，$x_0$は $N_0$の適当な元とする． そして，$v_0$は空写像である． $N_i$, $e_i$, $v_i$ が構成された時に $N_{i+1}$, $e_i$, $v_i$を構成する． $|N_i|\ge {(2R_2^n)}^{2a-i}(a)$なので， ${\mathrm{\Gamma }}_{x_i}$をについて同色な部分集合$A$で， $A\le {(R_2^n)}^{2a-i-1}(a)$となる$A$が存在する．これを$N_{i+1}$とし，$v_{i+}(i+1)$は ${[N_{i+1}]}^n$の色とする．

さて，$v_{2a-1}:2a\to 2$はについて，$|S|=a$で，$v_{2a-1}(S)$が等色になるものが存在する($2a\to {(a)}_2^1$が成り立つということでもある)．その値は$0$としても一般性を失わない． $M=\{x_i\mid i\in A\}$とする． もちろん$|M|=a$である． 任意にをとると， $x_{k_i}\in N_{k_0}$である． また，$v_{2a-1}(k_0)=0$なので

$${\mathrm{\Gamma }}_{x_{k_0}}(\{x_{k_1},\mathrm{\dots },x_{k_n}\})=\mathrm{\Gamma }(\{x_{k_0},\mathrm{\dots }{x}_{k_n}\})=0$$

である．$k_{\ast }$は任意であったから，$\mathrm{\Gamma }({[M]}^{n+1})=0$ であり，等色である． ∎

定理 17.

任意の$n,c,a\in {\mathbb{N}}_{+}$について$R_c^n(a)$が存在する．つまり， 任意の$n,c,a\in {\mathbb{N}}_{+}$について十分大きい$N$が存在して

$$N\to {(a)}_c^n$$

を満たす．

証明.

上の命題を帰納法で回すとわかる． ∎