次: 漸化不等式 上: ラムゼー型定理 前: ラムゼー数

存在定理

南海　 抽象的な論証になるが，十分条件は存在する． まずラムゼーの定理の無限型を示そう． 無限とはいっても，可算無限であることが重要である．

定理 3 (無限ラムゼー定理)        $r$を正整数とし，Sを可算無限集合とする． 写像

$$\chi\ :\ P(r\ ;\ S)\to \{1,\ 2,\ \cdots,\ n\}$$

に対し，$S$の無限部分集合$V$で

$$\chi(P(r\ ;\ V))=k$$

となる組$(V,\ k)$が存在する．

証明     $r$に関する数学的帰納法でおこなう．

$r=1$のとき， $P(1\ ;\ S)=\left\{ \{x\}\ \vert\ x \in S \right\}$なので$P(1\ ;\ S)$は$S$と同一視でき， 無限集合である． $1\le k \le n$に対し， ${\chi}^{-1}(k)$は$P(1\ ;\ S)$の部分集合である． 有限集合の有限個の和集合は有限集合なので， 背理法から ${\chi}^{-1}(k)\ (1\le k \le n)$のうち少なくとも一つは無限集合である． それを$C_k$とする．$C_k$は$S$の部分集合と見なせる． このとき，$(C_k,\ k)$が条件をみたす．

定理が$r=m$で成立するとする．$r=m+1$のときの成立を示す． $P(m+1\ ;\ S)$の写像を

$$\chi\ :\ P(m+1\ ;\ S)\to \{1,\ 2,\ \cdots,\ n\}$$

とする．

$S$は可算無限集合であるから順序を定義し，最小の元をもつように整列することができる． その順序を$<$で表す． $S$のこの順序に関する最小の元を$\theta$とする．

$S$から$\theta$を除いた集合$S/{\theta}$をとる． $P(m\ ;\ S/{\theta})$からの写像$\chi_0$

$$\chi_0\ :\ P(m\ ;\ S/{\theta})\to \{1,\ 2,\ \cdots,\ n\}$$

を， $U\in P(m\ ;\ S/{\theta})$に対し，

$$\chi_0(U)=k\quad \iff\quad \chi(U\cup\{\theta\})=k$$

で定める．このとき帰納法の仮定から このとき$S/{\theta}$の無限部分集合$S_0$で

$$\chi_0(P(r\ ;\ S_0))=k_0$$

となる組$(S_0,\ k_0)$が存在する．

$S_0$には最小の元が存在する．それを$x_1$とする．

$S_0$から$x_1$を除いた集合$S_0/{x_1}$をとる． $P(m\ ;\ S_0/{x_1})$からの写像$\chi_1$

$$\chi_1\ :\ P(m\ ;\ S/{x_1})\to \{1,\ 2,\ \cdots,\ n\}$$

を， $U\in P(m\ ;\ S_0/{x_1})$に対し，

$$\chi_1(U)=k\quad \iff\quad \chi(U\cup{x_1})=k$$

で定める．このとき帰納法の仮定から このとき$S/{x_1}$の無限部分集合$S_1$で

$$\chi_1(P(r\ ;\ S_1))=k_1$$

となる組$(S_1,\ k_1)$が存在する． $S_1$には最小の元が存在する．それを$x_2$とする．

これを繰りかえすことによって，$S$の元の無限列

$$\theta<x_1<x_2<\cdots$$

と分割番号の無限列

$$k_0<k_1<k_2<\cdots$$

が得られる．集合$X$を

$$X=\{x_1,\ x_2,\ \cdots\}$$

とし，その写像$\chi_{\infty}$

$$\chi_{\infty}\ :\ X\to \{1,\ 2,\ \cdots,\ n\}$$

を

$$\chi_{\infty}(x_j)=k_j$$

によって定める．$x_j$は $\{x_{j+1},\ x_{j+2},\ \cdots\}$の任意の$m$個の元からなる部分集合に $x_j$を付け加えると，その$m+1$個の元からなる部分集合の写像$\chi$の像は$k_j$ である．

$r=1$の論証と同様にして， ${\chi_{\infty}}^{-1}(k)\ (1\le k \le n)$の少なくとも一つは無限集合である． それを$V$とする．

$$\chi(P(m+1\ ;\ V))=k$$

となり，$(V,\ k)$は$r=m+1$のときの条件をみたす組である． □

有限ラムゼー定理2の証明の試み      背理法で示す．すなわち定理2の$R$が存在しないとする．

これをいいかえると次の命題となる．

ある整数の組

$$q_k\ge r \ge 1\quad ,\ k=1,\ 2,\ \cdots,\ n$$

で，次の命題をみたすものが存在する．

命題：

十分大きい任意の$N$に対し，$N$個の元からなる集合$S$に対し， $P(r\ ;\ S)$から $\{1,\ 2,\ \cdots,\ n\}$への写像$\chi$で，

$$V\in P(q_k\ ;\ S)\ かつ\ \chi(P(r\ ;\ V))=k$$

となる組$(V,\ k)$が存在しないものが，存在する．

太郎　 十分大きい任意の$N$に対して，組$(V,\ k)$が存在しない写像$\chi$とれるということは， 可算無限集合ではつねに組$(V,\ k)$が存在するということと矛盾する．

ということでしょうか．

南海　 基本的にはそういうことだ． もちろん，無限集合からの写像を帰納的に確定しなければならない． それは今は宿題としておこう．

次: 漸化不等式 上: ラムゼー型定理 前: ラムゼー数