パリス・ハリントン定理

数理論理学において、パリス・ハリントンの定理は、ラムゼー理論におけるある主張、すなわちペアノ算術で表現可能な強化された有限ラムゼー定理は、このシステムでは証明できないことを述べています。ただし、ラムゼー理論の主張は、わずかに強力なシステムでは証明可能です。

この結果は、一部の人々（以下の参考文献にある『数理論理学ハンドブック』の編集者など）によって、算術言語で述べることはできるがペアノ算術では証明できない整数に関する真のステートメントの最初の「自然な」例として説明されている。そのようなステートメントが存在することは、ゲーデルの第一不完全性定理によってすでに知られていた。

強化された有限ラムゼー定理は、色付けと自然数に関する定理であり、次のことを述べています。

任意の正の整数n、k、m （m ≥ n ）に対して、次の特性を持つN を見つけることができます。 S = {1、2、3、...、N }のn要素サブセットのそれぞれをk色のいずれかで色付けすると、少なくともm要素を持つSのサブセットY を見つけることができます。この場合、 Yのn要素サブセットはすべて同じ色になり、 Yの要素数は少なくともYの最小の要素数になります。

Yの要素の数が少なくともYの最小の要素であるという条件がなければ、これはにおける有限ラムゼー定理の系であり、N は次のように与えられます。 ${\displaystyle K_{{\mathcal {P}}_{n}(S)}}$

${\displaystyle {\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,).}$

さらに、強化された有限ラムゼー定理は、コンパクト性議論を使用して、有限ラムゼー定理を無限ラムゼー定理から演繹するのとほぼ同じ方法で演繹できます (詳細については、ラムゼー定理の記事を参照してください)。この証明は、2 次演算で実行できます。

パリス・ハリントンの定理は、強化された有限ラムゼー定理がペアノ算術では証明できないことを述べています。

大まかに言えば、ジェフ・パリスとレオ・ハリントン(1977) は、ペアノ算術では強化された有限ラムゼー定理が証明不可能であることを示し、ペアノ算術ではそれがペアノ算術自体の無矛盾性を意味することを示しました。ペアノ算術が本当に無矛盾であると仮定すると、ペアノ算術はゲーデルの第二不完全性定理によって自身の無矛盾性を証明できないため、これはペアノ​​算術が強化された有限ラムゼー定理を証明できないことを示しています。

強化された有限ラムゼー定理は、関連する式のクラスに対してまでの帰納法を仮定して証明できます。あるいは、算術理論に対して、-文に対して反射原理 を仮定して証明することもできます。反射原理は、ペアノ算術の無矛盾性も意味します。これは、2 階算術(またははるかに強力なツェルメロ-フランケル集合論)で証明可能であり、標準モデルでも当てはまります。 ${\displaystyle \varepsilon_{0}}$${\displaystyle \Sigma _{1}^{0}}$

強化された有限ラムゼー定理を満たす最小の数N は、 n、m、kの計算可能な関数ですが、非常に速く増加します。特に、これは原始再帰関数ではありませんが、アッカーマン関数などの非原始再帰関数の標準的な例よりもはるかに速く増加します。これは、アッカーマン関数などの関数を含む 、ペアノ算術で証明可能なすべての計算可能な関数を支配します。 ^[1]

• グッドスタインの定理
• 金森・マカルーン定理
• クラスカルの木定理

• マーカー、デイビッド（2002）。モデル理論入門。ニューヨーク：シュプリンガー。ISBN 0-387-98760-6。
• 数学の世界エントリー
• パリス、ジェフ、ハリントン、レオ(1977)。「ペアノ算術における数学的不完全性」。バーワイズ、ジョン、ケイスラー、H. ジェローム(編)。『数学論理ハンドブック』。アムステルダム、ニューヨーク: ノースホランド。pp. 1133–1142。ISBN 978-0-7204-2285-6。

• 証明不可能性の簡単な紹介（パリス・ハリントン定理の証明を含む）Andrey Bovykin著