パリス＝ハーリントンの定理
強化版有限ラムゼーの定理は自然数と色付けに関する以下の定理である。
任意の正整数の組 n, k, m (m ≥ n)に対して、以下の条件を満たす N が存在する: S = {1, 2, 3,..., N} の n 要素の部分集合のそれぞれを k 色を使って色付けしたとき、少なくとも m 要素を持つ S の部分集合 Y で、Y のすべての n 要素の部分集合が同じ色であり、かつ Y の要素数は Y の要素のうち最も小さいものの値以上であるようなものが存在する。
「Y の要素数は Y の要素の最低値以上である」という条件がなければ、この定理は K P n ( S ) {\displaystyle K_{{\mathcal {P}}_{n}(S)}} に対し N を
( N n ) = | P n ( S ) | ≥ R ( m , m , ... , m ⏟ k ) {\displaystyle {\binom {N}{n}}=|{\mathcal {P}}_{n}(S)|\geq R(\,\underbrace {m,m,\ldots ,m} _{k}\,)}
としたときの有限ラムゼーの定理より導かれる。
さらに、強化版有限ラムゼーの定理は無限ラムゼーの定理から、有限ラムゼーの定理を導出するのとほぼ同じ方法で導出される。証明はコンパクト性定理を用い、二階述語論理の中で行われる。