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

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

数理論理学におけるパリス・ハーリントンの定理は、ラムゼー理論における興味深い結果を示す定理です。この定理は、一見すると自然に見える整数に関する命題が、ペアノ算術という基本的な算術の枠組みでは証明できないという、驚くべき事実を明らかにします。

具体的には、パリス・ハーリントンの定理は、強化版有限ラムゼーの定理が、ペアノ算術では証明できないことを示しています。この事実は、ゲーデルの不完全性定理が示す「形式的な算術体系には、その体系内では証明も反証もできない命題が存在する」という抽象的な概念を、具体的な形で示している点で重要です。

強化版有限ラムゼーの定理

強化版有限ラムゼーの定理は、自然数の集合と色の塗り分けに関する定理です。この定理は、以下の様に述べられます。

任意の正整数の組 n, k, m (ただし m ≥ n) が与えられたとき、ある自然数 N が存在し、集合 S = {1, 2, 3, ..., N} の n 要素の部分集合を k 色で塗り分けたとき、次の条件を満たす、m 個以上の要素を持つ S の部分集合 Y が存在する:

1. Y の全ての n 要素の部分集合は同じ色で塗られている。
2. Y の要素数は、Y の要素のうち最小の値以上である。

この定理において、条件2を「Yの要素数はYの要素の最小値以上である」という条件を削除すると、通常の有限ラムゼーの定理となり、ペアノ算術でも証明可能です。強化版有限ラムゼーの定理は、この追加された条件により、ペアノ算術では証明できない複雑さを持ちます。

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

パリスとハリントンは、1977年に、ペアノ算術の枠内で強化版有限ラムゼーの定理が証明可能だと仮定すると、ペアノ算術自身の無矛盾性が証明できてしまうことを示しました。ゲーデルの第二不完全性定理により、ペアノ算術は自身の無矛盾性を証明できないため、強化版有限ラムゼーの定理はペアノ算術では証明できないことが結論付けられます。

強化版有限ラムゼーの定理を満たす数 N は、n, k, m の計算可能な関数として求めることができます。しかし、その増加速度は非常に速く、原始再帰関数の範囲を超えています。実際、よく知られた急速に増加する関数であるアッカーマン関数と比較しても、その増加速度は遥かに上回ります。ペアノ算術はアッカーマン関数がすべての値に対して定義されていることを証明できますが、強化版有限ラムゼーの定理の場合は、その増加が速すぎて、すべての値に対して定義されていることすら証明することができません。

この定理は、算術的な概念が持つ深さと、形式的な証明体系の限界を浮き彫りにする、数理論理学における重要な結果と言えるでしょう。

補足

この定理は、ゲーデルの不完全性定理が示す「証明できない命題」の具体的な例を提供するだけでなく、数学における証明の限界、特に計算可能性の観点から重要な示唆を与えています。

関連項目

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

もう一度検索