Paris–Harringtonの定理

同義語:Paris-Harringtonの定理Paris–Harrington theorem

概要

Paris–Harringtonの定理(Paris–Harrington theorem)とは、有限の Ramsey の定理に、同色の集合 $H$ が $|H|\ge\min H$ を満たすという条件を加えた命題が、真であるのに Peano算術では証明できないという定理である。命題自体は無限の Ramsey の定理と König の補題から容易に従うが、必要な範囲の大きさは Peano算術で全域と証明できるどの関数よりも速く増大する。算術の符号化を含まない、証明できない命題の最初の自然な例とされる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Ramseyの定理, Peano算術, Gödelの不完全性定理

Paris–Harrington の定理(Paris–Harrington theorem)は、有限の Ramsey の定理をほんの少し強めた組合せ論の命題が、真であるのに Peano算術 では証明できない、という定理である。強めるのは一点だけで、同色の集合 $H$ に対して、大きさがあらかじめ決めた数以上であることに加えて、$|H|\ge\min H$ を要求する。「$H$ の大きさが $H$ 自身の最小元に追いつく」というこの条件によって、必要な範囲の大きさは Peano算術で全域と証明できるどの関数よりも速く増大する。
Gödelの不完全性定理 が与える証明できない文は、理論の証明を算術で符号化して作るものである。これに対し、この定理の命題には算術の符号化が現れず、色分けと有限集合だけで述べられる。証明できない文の最初の自然な例とされる(Hal12 p. 22)。
この記事では、命題が真であることを Ramseyの定理 の無限の形と König の補題から完全に証明する。次に、$1$ 元部分集合の色分けでは必要な範囲を正確に求め、$2$ 元部分集合では $2$ 色でも範囲が少なくとも $n$ の指数関数の程度に増えることを示して、条件 $|H|\ge\min H$ の効き方を具体的に見る。Peano算術で証明できないことは文献の支配の結果を引用し、そこから独立性が導かれる部分だけを証明する。

定義と主張

集合 $X$ と自然数 $k$ について、$X$ の $k$ 元部分集合全体を $[X]^k$ と書く。$[n,N]:=\{i\in\mathbb N\mid n\le i\le N\}$ とする。色分け $c\colon[X]^k\to\{1,\dots,r\}$ について、$H\subset X$ が 同色 であるとは、$c$ が $[H]^k$ の上で一定であることをいう。

比較的大きい集合

空でない有限集合 $H\subset\mathbb N$ は、$|H|\ge\min H$ を満たすとき 比較的大きい(relatively large)という。

たとえば $\{3,7,100\}$ は比較的大きいが、$\{4,7,100\}$ はそうでない。元の値の大小ではなく、最小元と個数の関係だけが問題になる。
有限 Ramsey の定理は「$k,r,s$ に対して、十分大きい $N$ をとると、$[1,N]$ の $k$ 元部分集合の $r$ 色の色分けは、$s$ 元の同色集合をもつ」という主張である(Hal12 Corollary 2.3、p. 14)。次の命題はこれを強めたものである。

強められた有限 Ramsey の定理

正の整数 $k,r,n$ に対して、自然数 $N\ge n$ が存在して、任意の色分け $c\colon[\,[n,N]\,]^k\to\{1,\dots,r\}$ に対し、比較的大きい同色集合 $H\subset[n,N]$ が存在する。

このような $N$ の最小値を $\mathrm{PH}(k,r,n)$ と書く。$N$ が条件を満たせば、色分けを $[n,N]$ に制限することで $N+1$ も条件を満たす。$n\ge k$ のとき、比較的大きい $H$ は $|H|\ge\min H\ge n\ge k$ を満たすので、$k$ 元部分集合が実際に存在し、同色という条件に意味がある。
$n:=\max(s,k)$ とすれば $|H|\ge n\ge s$ となるから、thm-ph-strong から有限 Ramsey の定理が従う。

Paris–Harrington の定理

thm-ph-strong の主張を算術の文に書いたものは、真であるが、Peano算術では証明できない。

真であることは次の節で証明する。証明できないことは後の節で述べる。

主張が真であること

無限の形の Ramsey の定理を使う。Ramseyの定理 の記事は $k=2$ の場合を証明している。

無限 Ramsey の定理

$k,r\ge1$ とし、$X\subset\mathbb N$ を無限集合とする。任意の $c\colon[X]^k\to\{1,\dots,r\}$ に対し、無限の同色集合 $H\subset X$ が存在する。

要点:$k$ についての帰納法で、$x$ を 1 つ固定して $k-1$ 元部分集合の色分けに帰着する。

詳しい証明を開く

$k=1$ は無限集合を有限個に分けることから分かる。$k\ge2$ とし、$k-1$ で成り立つとする。$X_0:=X$ とする。無限集合 $X_i$ が定まったら、$x_i:=\min X_i$ とし、$X_i\setminus\{x_i\}$ の上の $k-1$ 元部分集合の色分け $s\mapsto c(\{x_i\}\cup s)$ に帰納法の仮定を当てて、無限の同色集合 $X_{i+1}\subset X_i\setminus\{x_i\}$ とその色 $\chi_i$ をとる。$x_0< x_1<\cdots$ であり、$i< j_1<\cdots< j_{k-1}$ なら $c(\{x_i,x_{j_1},\dots,x_{j_{k-1}}\})=\chi_i$ である。$\chi_i$ は有限個の値しかとらないので、無限個の $i$ で同じ色になる。それらの $x_i$ の全体が求める $H$ である。$\square$

強められた有限 Ramsey の定理

$k,r,n$ を固定し、結論を否定する。$N\ge n$ について、比較的大きい同色集合をもたない $c\colon[\,[n,N]\,]^k\to\{1,\dots,r\}$ を 悪い色分け という。仮定からすべての $N\ge n$ に悪い色分けがある。
悪い色分けを頂点とし、$[n,N+1]$ の上の色分けの親を $[n,N]$ への制限とする木を考える。悪い色分けの制限は悪い。$[n,N]$ の上の比較的大きい同色集合は、$[n,N+1]$ の上でも比較的大きい同色集合だからである。最初の段の上に根を 1 つ加えると、各段の頂点は有限個で、木は無限である。Kőnigの補題 により無限の枝が存在する。枝の色分けは互いに延長なので、合わせて $c\colon[\,[n,\infty)\,]^k\to\{1,\dots,r\}$ が得られ、すべての制限 $c|_{[\,[n,N]\,]^k}$ は悪い。ここで $[n,\infty):=\{i\in\mathbb N\mid i\ge n\}$ である。
lem-ph-infinite により、無限の同色集合 $H\subset[n,\infty)$ がある。$a:=\min H\ge n\ge1$ とし、$S$ を $H$ の小さい方から $a$ 個の元の集合とする。$\min S=a=|S|$ だから $S$ は比較的大きく、同色である。$N:=\max S$ とすると、$S$ は $c|_{[\,[n,N]\,]^k}$ の比較的大きい同色集合であり、この制限が悪いことに反する。$\square$

証明は $H$ が無限であることと König の補題を本質的に使っている。無限集合 $H$ からは、$\min H$ が決まったあとで必要なだけ元をとれる。

条件の一般化

同じ証明で、任意の関数 $f\colon\mathbb N\to\mathbb N$ について、条件 $|H|\ge\min H$ を $|H|\ge f(\min H)$ に替えた命題が示せる。$S$ を $H$ の小さい方から $\max(1,f(a))$ 個の元にすればよい。$f$ が定数なら有限 Ramsey の定理であり、$f$ が恒等写像なら thm-ph-strong である。

必要な範囲の大きさ

条件 $|H|\ge\min H$ がどう効くかを、小さい場合で見る。$k=1$ では値が正確に求まる。

$1$ 元部分集合の場合

正の整数 $r,n$ について
$$ \mathrm{PH}(1,r,n)=2^r(n-1)+1 $$
である。

$M:=2^r(n-1)+1$ とする。
上界。 $c\colon[n,M]\to\{1,\dots,r\}$ が比較的大きい同色集合をもたないとして矛盾を導く。$X_0:=[n,M]$ とし、$X_j\ne\emptyset$ のとき、$a_j:=\min X_j$、$C_j$ を $X_j$ のうち $a_j$ と同じ色の元の全体、$X_{j+1}:=X_j\setminus C_j$ とする。$C_j$ は最小元 $a_j$ の同色集合なので、仮定から $|C_j|\le a_j-1$ である。
$j\le r$ について $X_j\ne\emptyset$ かつ $a_j-1\le2^j(n-1)$ であることを、$j$ についての帰納法で示す。$j$ 未満で成り立つとすると、取り除いた元の個数は
$$ \sum_{i< j}|C_i|\le\sum_{i< j}2^i(n-1)=(2^j-1)(n-1) $$
以下である。一方 $|[n,M]|=(2^r-1)(n-1)+1$ はこれより大きいので $X_j\ne\emptyset$ である。さらに $[n,M]$ の小さい方から $(2^j-1)(n-1)+1$ 個の元のうち少なくとも 1 つは残っているので、$a_j\le n+(2^j-1)(n-1)$、すなわち $a_j-1\le2^j(n-1)$ である。
$C_0,\dots,C_{r-1}$ は互いに異なる色の集合だから、$r$ 色すべてが取り除かれて $X_r=\emptyset$ となる。これは $X_r\ne\emptyset$ に反する。
下界。 $n=1$ なら $M=1=n$ で、$N\ge n$ の最小値だから成り立つ。$n\ge2$ とする。$i=0,\dots,r-1$ について
$$ I_i:=[2^i(n-1)+1,\ 2^{i+1}(n-1)] $$
とすると、$[n,M-1]$ は $I_0,\dots,I_{r-1}$ の非交和である。$I_i$ の元に色 $i+1$ を与える。同色集合 $H\subset I_i$ は $|H|\le|I_i|=2^i(n-1)<\min H$ を満たすので比較的大きくない。よって $M-1$ は条件を満たさず、$\mathrm{PH}(1,r,n)\ge M$ である。$\square$

色が $1$ つ増えるごとに範囲が $2$ 倍になる。同じ色の元をすべて集めても大きさが最小元に足りない区間を、色の数だけ積み重ねられるからである。
$2$ 元部分集合では、$2$ 色でも様子が変わる。

$2$ 元部分集合の $2$ 色の下界

$n\ge2$ について $\mathrm{PH}(2,2,n)>n\cdot2^{n-2}$ である。

$x\ge2$ について $b(x):=\min\{i\mid x\le2^i\}$ とする。$b(x)\ge1$ であり、$2^{b(x)-1}< x\le2^{b(x)}$ である。$x< y$ について、$b(x)=b(y)$ なら $c(\{x,y\}):=1$、$b(x)\ne b(y)$ なら $c(\{x,y\}):=2$ と定める。
$N\le n\cdot2^{n-2}$ として、$c$ の $[n,N]$ への制限に比較的大きい同色集合がないことを示す。$H$ が比較的大きい同色集合だとする。$|H|\ge\min H\ge n\ge2$ なので、$H$ の 2 元部分集合が存在し、色が定まる。
色 $1$ のとき、$H$ はある $i\ge1$ についての区間 $(2^{i-1},2^i]$ に含まれる。この区間の整数は $2^{i-1}$ 個で、$\min H>2^{i-1}\ge|H|$ だから、$H$ は比較的大きくない。
色 $2$ のとき、$H=\{x_1<\cdots< x_s\}$ とすると、$b(x_1)<\cdots< b(x_s)$ である。$s\ge x_1\ge n$ に注意して
$$ x_s>2^{b(x_s)-1}\ge2^{b(x_1)+s-2}\ge x_1\cdot2^{s-2}\ge n\cdot2^{n-2} $$
となり、$x_s\le N$ に反する。$\square$

$k=1$ では範囲は $n$ の一次式であったが、$k=2$ では少なくとも $n$ の指数関数の程度に増える。$k$ と $r$ を増やすと増大は急激に強まり、次の節の結果に至る。

Peano算術で証明できないこと

$\mathrm{PH}(k,r,n)=N$ という関係は、有限個の色分けを調べれば判定できるので原始再帰的であり、thm-ph-strong は算術の文として書ける。関数が Peano算術で全域と証明できる とは、そのグラフが $\Sigma_1$ 論理式 $A$ で書け、$\mathsf{PA}\vdash\forall\vec x\,\exists!y\,A(\vec x,y)$ となることをいう。
文献の結果を次の形で引用する。$\{0,\dots,L-1\}$ の $l$ 元部分集合の任意の $l$ 色の色分けが、大きさ $l+1$ 以上の比較的大きい同色集合をもつような最小の $L$ を $\sigma(l)$ とする。

支配の定理

関数 $\sigma$ は、Peano算術で全域と証明できるどの関数 $f$ についても、十分大きいすべての $l$ で $\sigma(l)\ge f(l)$ を満たす。

これは Paris と Harrington の結果であり(Fre17 §1 の Corollary 1.5 の直前が [PH77, Theorem 3.2] として引く。同論文の記号では $\sigma(n,n)$)、この記事では証明しない。Ketonen と Solovay は $\sigma$ を急増加階層の関数 $F_{\varepsilon_0}$ と結びつけた(Fre17 序論)。$F_{\varepsilon_0}$ は Peano算術で全域と証明できるすべての関数を支配する関数である。証明できない根拠が、Goodsteinの定理 と同じ順序数 $\varepsilon_0$ に行き着く。

Paris–Harrington の定理

真であることは前の節で示した。Peano算術で thm-ph-strong が証明できたとする。$g(l):=\mathrm{PH}(l,l,l+1)+1$ とおくと、$g$ のグラフは $\Sigma_1$ 論理式で書け、最小数原理により一意性も証明できるので、$g$ と $f:=g+1$ は全域と証明できる。
$L:=g(l)$ とする。$\{0,\dots,L-1\}$ の $l$ 元部分集合の $l$ 色の色分けを $[l+1,L-1]$ に制限すると、$L-1=\mathrm{PH}(l,l,l+1)$ だから比較的大きい同色集合 $H$ があり、$|H|\ge\min H\ge l+1$ である。よって $\sigma(l)\le g(l)< f(l)$ がすべての $l\ge1$ で成り立つ。これは thm-ph-dominate に反する。$\square$

強められる前の有限 Ramsey の定理との違いは、$|H|\ge s$ の $s$ が色分けの前に決まっているか、$H$ が決まってから $\min H$ で決まるかだけである。rem-ph-f の $f$ が定数か恒等写像かの違いと言ってもよい。

固定すると証明できる場合

$k,r,n$ のどれを固定するかで、証明に必要な強さが変わる。算術の部分体系 の $\mathsf{I\Sigma}_m$ は、$\Sigma_m$ 論理式の帰納法をもつ理論である。

固定するもの主張証明できる理論
$k,r,n$ のすべて$\exists N$ の $\Sigma_1$ 文Robinson算術(真な $\Sigma_1$ 文)
$k\ge2$ と $r$$\forall n\,\exists N$$\mathsf{I\Sigma}_{k-1}$
なし$\forall k,r,n\,\exists N$Peano算術では証明できない

$k\ge2$ と $r$ を固定した場合は、Fre17 の序論が Hájek–Pudlák の教科書の定理として引く結果である(この記事では証明しない)。$\mathsf{PA}=\bigcup_m\mathsf{I\Sigma}_m$ だから、$k$ を固定すれば $\mathsf{PA}$ の有限の段で証明でき、$k$ を動かすと全部の段を合わせても足りなくなる。文献の主張は rem-ph-forms の形で述べられており、そこで示すとおり色を $1$ つ足してこの記事の形に移る。
同じ論文の主結果は、個々の場合の証明の長さについてのものである。rem-ph-forms の F 形で $m=k+1$ とし、色の数を $k$ の適当な初等関数にとると、十分大きい $k$ で、$\mathsf{I\Sigma}_{k-2}$ の中の証明の Gödel 数は $F_{\varepsilon_0}(k-3)$ 以上になる(Fre17 序論の (1))。各場合は弱い理論で証明できるが、帰納法の複雑さをわずかに下げるだけで証明は途方もなく長くなる。

反例:数値ごとの証明と全称の証明

「すべての数値 $\bar k,\bar r,\bar n$ について $T\vdash A(\bar k,\bar r,\bar n)$ なら $T\vdash\forall k,r,n\,A(k,r,n)$」という含意は成り立たない。$T=\mathsf{PA}$、$A(k,r,n):=\exists N\,(\mathrm{PH}(k,r,n)=N)$ がその反例である。

  • 満たすこと:各場合は真な $\Sigma_1$ 文なので、$\mathsf{PA}$ で証明できる。
  • 満たさないこと:全称の文は thm-ph-main により証明できない。
  • 成り立たない含意:数値ごとの証明を 1 本の全称の証明にまとめられるとは限らない。

文献による形の違い

比較的大きいことの定義

文献の述べ方には次の違いがある。

  • Hal12 Corollary 2.6(p. 16)は $|H|>\min H$ を要求し、MMV25 Statement 1.1 は $|H|>\max(m,\min H)$ の形で述べる。
  • Fre17 は $\{0,\dots,N-1\}$ を色分けし、$|H|\ge\min H$ と $|H|\ge m$ を別々に要求する。この $k,r,m$ についての主張を F 形 と呼ぶ。
    Hal12 の狭義の不等号の形は thm-ph-strong と同値である。実際、狭義の形からこの記事の形は明らかである。逆に、この記事の形を $n+1$ に当てる。$[n,N]$ の色分け $c$ に対し、$c'(s):=c(\{x-1\mid x\in s\})$ で $[n+1,N+1]$ の色分け $c'$ を定めると、$c'$ の比較的大きい同色集合 $H$ から、$H':=\{x-1\mid x\in H\}$ は $c$ の同色集合で、$|H'|=|H|\ge\min H=\min H'+1>\min H'$ である。
    F 形もこの記事の形と互いに移る。この記事の形から F 形を得るには $n:=\max(m,1)$ として $[n,N]$ に制限すればよい。逆に、F 形を $r+1$ 色、$m:=n+k$ で使う。$[n,N-1]$ の色分け $c$ を、最小元が $n$ 未満の $k$ 元部分集合に新しい色を与えて $\{0,\dots,N-1\}$ へ延ばす。$H$ を得られた同色集合とする。$|H|\ge n+k$ だから $H$ の $n$ 以上の元は $k$ 個以上あり、それらの $k$ 元部分集合は元の色をもつ。よって新しい色は $[H]^k$ に現れず、$H\subset[n,N-1]$ である。
    MMV25 の語では、$|H|>\min H$ を満たす集合は $\omega$-大きい($\omega$-large)という。Ketonen と Solovay はこの概念を $\varepsilon_0$ 未満の順序数 $\alpha$ についての $\alpha$-大きさに広げ、$N$ の評価を改良した(MMV25 §1)。

条件を変えた反例

変える条件反例成り立たなくなること
色は有限個(無限個を許す)$k=1$、$c(x):=x$、$n\ge2$。同色集合は $1$ 元集合だけで、$\lvert H\rvert=1< n\le\min H$どの $N$ でも比較的大きい同色集合がない
$\lvert H\rvert\ge\min H$($\lvert H\rvert\ge\max H$ に替える)$k=1$、$r=1$、$n\ge2$。$H\subset[n,N]$ は $\lvert H\rvert\le\max H-n+1<\max H$どの $N$ でも条件を満たす $H$ がない
$N$ は $r$ に依存する($r$ によらない $N$ を求める)$k=1$、$n\ge2$。prop-ph-one から $\mathrm{PH}(1,r,n)$ は $r$ とともに増える$k,n$ だけで決まる $N$ が存在すること
rem-ph-f の $f$ は $N$ より先に固定($f$ を $N$ に依存させる)$k=1$、$r=1$、$n=1$、$f(x):=N+1$$f$ に対して $N$ を見つけられること

色を無限個にした反例は lem-ph-infinite の仮定「色が有限個」を、$\max H$ に替えた反例は比較的大きい集合の定義の最小元に関する条件を、それぞれ満たしていない。$f$ を $N$ に依存させた反例は rem-ph-f で $f$ が $N$ より先に決まっていることが要ることを示す。$f(x)=N+1$ なら $[1,N]$ の中に大きさ $N+1$ の集合はない。

関連項目

参考文献

[1]
Lorenz J. Halbeisen, Combinatorial Set Theory, Springer, 2012, Chapter 2:Corollary 2.3(p. 14)、Corollary 2.6(p. 16)、p. 22
[2]
Alberto Marcone, Antonio Montalbán, Andrea Volpi, The barrier Ramsey theorem, arXiv:2505.02544, 2025, §1(Statement 1.1、ω-large の定義)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する