強化版有限ラムゼーの定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/31 09:08 UTC 版)
「パリス＝ハーリントンの定理」の記事における「強化版有限ラムゼーの定理」の解説
強化版有限ラムゼーの定理は自然数と色付けに関する以下の定理である。 任意の正整数の組 n, k, m に対して、以下の条件を満たす N が存在する: S = {1, 2, 3,..., N} の n 要素の部分集合のそれぞれを k 色を使って色付けしたとき、少なくとも n 要素を持つ 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}\,)} としたときの有限ラムゼーの定理より導かれる。 さらに、強化版有限ラムゼーの定理は無限ラムゼーの定理から、有限ラムゼーの定理を導出するのとほぼ同じ方法で導出される。証明はコンパクト性定理を用い、二階述語論理の中で行われる。
※この「強化版有限ラムゼーの定理」の解説は、「パリス＝ハーリントンの定理」の解説の一部です。
「強化版有限ラムゼーの定理」を含む「パリス＝ハーリントンの定理」の記事については、「パリス＝ハーリントンの定理」の概要を参照ください。
- 強化版有限ラムゼーの定理のページへのリンク
