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


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

概要

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

定義
  • 順序数と同様に自然数を自然数の有限集合と同一視する.
  • 有限集合相対的に大きい (relatively large) であるとはの要素の個数がの要素の最小値以上になることである.
  • の部分集合で要素の個数がと等しい集合全体とする.
  • 関数-分割 (-partition) や-彩色 (-coloring) という.
  • -分割の要素の個数が以上であるとき,による制限が定数関数になる,すなわちを満たすとき,は分割に対して均質 (homogeneous) ,-均質 (-homogeneous) ,あるいは単色 (monochromatic) であるという.
  • 自然数 ,自然数の有限集合に対しで,任意の-分割に対し,-均質集合で,の要素の個数は以上となるようなものが存在する,という命題を表すこととする.
  • 自然数 ,自然数の有限集合に対しで,任意の-分割に対し,相対的に大きい-均質集合で,の要素の個数は以上となるようなものが存在する,という命題を表すこととする.

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

有限ラムゼーの定理とその拡張
  1. 任意の自然数に対し,ある自然数が存在しである.
  2. 任意の自然数に対し,ある自然数が存在しである[1]
パリス・ハーリントンの定理[1]

ペアノ算術で以下の命題は証明できない,またもっと強く,以下はペアノ算術の-無矛盾性とペアノ算術上で同値である.

  • 任意の自然数に対し,ある自然数が存在しである.

誘導される関数

以下計算可能関数とする.

定理[1]

ペアノ算術に於いて再帰関数の全域性が証明できるとき,あるが存在し,任意のに対しである.従ってはペアノ算術に於いて可証全域ではない.

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

定理[2]

任意のに対しである.ここでを急増加関数とする[注 1]

定理[3]

ある初等再帰関数が存在し任意のに対しである.ただしハーディ関数とする.

脚注

  1. ただし急増加関数の定義は巨大数研究Wikiのものとは微妙にことなり,と定義している,つまり合成回数が巨大数研究Wikiの定義より一回多い.

出典

  1. 1.0 1.1 1.2 1.3 J. Paris, and L. Harrington. A mathematical incompleteness in Peano arithmetic. 1977.
  2. J. Ketonen, and R. Solovay. Rapidly growing Ramsey functions. Annals of Mathematics 113.2 (1981): 267-314.
  3. R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey theory. Vol. 20. John Wiley & Sons, 1990.
特に記載のない限り、コミュニティのコンテンツはCC-BY-SAライセンスの下で利用可能です。