パリス＝ハーリントンの定理
From Wikipedia, the free encyclopedia
数理論理学においてパリス・ハーリントンの定理（ぱりすはーりんとんのていり、英: Paris–Harrington theorem）は、自然数に関するある命題（ラムゼー理論における強化版有限ラムゼーの定理）が、正しいにもかかわらずペアノ算術では証明できないとする定理。
ペアノ算術は代表的な自然数論の公理系であり自然数論の正しい命題の多くを証明できる。一方でゲーデルの不完全性定理によって、正しい命題であるがペアノ算術では証明できないものが存在することも知られていた。ただし、不完全性定理の発表論文で示された命題は、自己言及のパラドックスに関連する人工的な印象のものであった。
パリス・ハーリントンの定理はペアノ算術で証明できない「自然な」命題の例を示した。
強化版有限ラムゼーの定理は自然数と色付けに関する以下の定理である。
- 任意の正整数の組 n, k, m (m ≥ n)に対して、以下の条件を満たす N が存在する: S = {1, 2, 3,..., N} の n 要素の部分集合のそれぞれを k 色を使って色付けしたとき、少なくとも m 要素を持つ S の部分集合 Y で、Y のすべての n 要素の部分集合が同じ色であり、かつ Y の要素数は Y の要素のうち最も小さいものの値以上であるようなものが存在する。
「Y の要素数は Y の要素の最低値以上である」という条件がなければ、この定理はに対し N を
としたときの有限ラムゼーの定理より導かれる。
さらに、強化版有限ラムゼーの定理は無限ラムゼーの定理から、有限ラムゼーの定理を導出するのとほぼ同じ方法で導出される。証明はコンパクト性定理を用い、二階述語論理の中で行われる。[1]