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

存在定理

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

定理 3
(無限ラムゼー定理)        $r$を正整数とし,Sを可算無限集合とする. 写像
\begin{displaymath}
\chi\ :\ P(r\ ;\ S)\to \{1,\ 2,\ \cdots,\ n\}
\end{displaymath}

に対し,$S$の無限部分集合$V$
\begin{displaymath}
\chi(P(r\ ;\ V))=k
\end{displaymath}

となる組$(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)$の写像を

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

とする.

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

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

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

を, $U\in P(m\ ;\ S/{\theta})$に対し,
\begin{displaymath}
\chi_0(U)=k\quad \iff\quad
\chi(U\cup\{\theta\})=k
\end{displaymath}

で定める.このとき帰納法の仮定から このとき$S/{\theta}$の無限部分集合$S_0$
\begin{displaymath}
\chi_0(P(r\ ;\ S_0))=k_0
\end{displaymath}

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

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

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

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

を, $U\in P(m\ ;\ S_0/{x_1})$に対し,
\begin{displaymath}
\chi_1(U)=k\quad \iff\quad
\chi(U\cup{x_1})=k
\end{displaymath}

で定める.このとき帰納法の仮定から このとき$S/{x_1}$の無限部分集合$S_1$
\begin{displaymath}
\chi_1(P(r\ ;\ S_1))=k_1
\end{displaymath}

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

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

\begin{displaymath}
\theta<x_1<x_2<\cdots
\end{displaymath}

と分割番号の無限列
\begin{displaymath}
k_0<k_1<k_2<\cdots
\end{displaymath}

が得られる.集合$X$
\begin{displaymath}
X=\{x_1,\ x_2,\ \cdots\}
\end{displaymath}

とし,その写像$\chi_{\infty}$
\begin{displaymath}
\chi_{\infty}\ :\ X\to \{1,\ 2,\ \cdots,\ n\}
\end{displaymath}


\begin{displaymath}
\chi_{\infty}(x_j)=k_j
\end{displaymath}

によって定める.$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$とする.

\begin{displaymath}
\chi(P(m+1\ ;\ V))=k
\end{displaymath}

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

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

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

ある整数の組

\begin{displaymath}
q_k\ge r \ge 1\quad ,\ k=1,\ 2,\ \cdots,\ n
\end{displaymath}

で,次の命題をみたすものが存在する.
命題:
十分大きい任意の$N$に対し,$N$個の元からなる集合$S$に対し, $P(r\ ;\ S)$から $\{1,\ 2,\ \cdots,\ n\}$への写像$\chi$で,
\begin{displaymath}
V\in P(q_k\ ;\ S)\ かつ\ \chi(P(r\ ;\ V))=k
\end{displaymath}

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

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

ということでしょうか.

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


next up previous 次: 漸化不等式 上: ラムゼー型定理 前: ラムゼー数
Aozora
2015-03-04