パリス・ハーリントンの定理

パリス・ハーリントンの定理
型	組合せ数学

パリス・ハーリントンの定理 (Paris–Harrington theorem) は有限ラムゼーの定理の拡張であり，ペアノ算術から証明ができないが標準モデルで真である命題の例，あるいは命題がペアノ算術から証明不能であるという定理を指し，この命題から誘導する関数はペアノ算術の可証再帰関数を支配することが知られている．

概要

パリス・ハーリントンの定理の定理を述べるために，用語を定義する．

定義

順序数と同様に自然数\(M\)を自然数の有限集合\(\{n\mid n<M\}\)と同一視する． 有限集合\(H\subseteq\mathbb{N}\)が相対的に大きい (relatively large) であるとは\(H\)の要素の個数が\(H\)の要素の最小値以上になることである． \([M]^e\)で\(M\)の部分集合で要素の個数が\(e\)と等しい集合全体とする． 関数\(P\colon [M]^e\to r\)を\(r\)-分割 (\(r\)-partition) や\(r\)-彩色 (\(r\)-coloring) という． \(r\)-分割\(P\colon [M]^e\to r\)と\(N\subseteq M\)で\(N\)の要素の個数が\(e\)以上であるとき，\(P\)の\([N]^e\)による制限が定数関数になる，すなわち\((\exists d\in r)(\forall X\in [N]^e)[P(X)=d]\)を満たすとき，\(N\)は分割\(P\)に対して均質 (homogeneous) ，\(P\)-均質 (\(P\)-homogeneous) ，あるいは単色 (monochromatic) であるという． 自然数 \(e,r,k\)，自然数の有限集合\(M\)に対し\(M\rightarrow (k)^e_r\)で，任意の\([M]^e\)の\(r\)-分割に対し，\(P\)-均質集合\(H\)で，\(H\)の要素の個数は\(k\)以上となるようなものが存在する，という命題を表すこととする． 自然数 \(e,r,k\)，自然数の有限集合\(M\)に対し\(M\xrightarrow[*]{} (k)^e_r\)で，任意の\([M]^e\)の\(r\)-分割に対し，相対的に大きい\(P\)-均質集合\(H\)で，\(H\)の要素の個数は\(k\)以上となるようなものが存在する，という命題を表すこととする．

次の定理が有限ラムゼーの定理とそのパリス・ハーリントンによる拡張である．

有限ラムゼーの定理とその拡張
任意の自然数\(e,r,k\)に対し，ある自然数\(M\)が存在し\(M\rightarrow (k)^e_r\)である． 任意の自然数\(e,r,k\)に対し，ある自然数\(M\)が存在し\(M\xrightarrow[*]{} (k)^e_r\)である．

パリス・ハーリントンの定理
ペアノ算術で以下の命題は証明できない，またもっと強く，以下はペアノ算術の\(1\)-無矛盾性とペアノ算術上で同値である． 任意の自然数\(e,r,k\)に対し，ある自然数\(M\)が存在し\(M\xrightarrow[*]{} (k)^e_r\)である．

誘導される関数

以下計算可能関数\(\mathrm{PH}(e,r)\)を\(\mathrm{PH}(e,r):=\min\{M\mid M\xrightarrow[*]{}(e+1)^e_r\}\)とする．

定理
ペアノ算術に於いて再帰関数\(g\)の全域性が証明できるとき，ある\(e\)が存在し，任意の\(n>e\)に対し\(\mathrm{PH}(n,n)>g(n)\)である．従って\(\mathrm{PH}\)はペアノ算術に於いて可証全域ではない．

任意の\(\alpha<\varepsilon_0\)に対してカントール標準形による基本列に対する急増加関数，\(f_\alpha\)はペアノ算術で全域性が証明可能であることから\(f\)は急激に増大することが分かる．このアイデアをもっと精緻にした以下の定理が知られている．

定理
任意の\(n\)に対し\(F_{\varepsilon_0}(n)\leq\mathrm{PH}(n+3,8)\leq F_{\varepsilon_0}(n+1)\)である．ここで\(F_\alpha\)を急増加関数とする．

定理
ある初等再帰関数\(l\)が存在し任意の\(n\)に対し\(H_{\varepsilon_0}(n)\leq\mathrm{PH}(n+1,l(n))\)である．ただし\(H\)はハーディ関数とする．