[PDF版]

※これは研究室でのゼミ資料を一部改変して公開したものである.

定義と準備

以下では,初等部分構造を用いた議論をするので,まずその準備をしておく:

\(\kappa \geq \omega\) とする.\(M\)\(\kappa\)-closed \(\Leftrightarrow [M]^{<\kappa} \subseteq M\)

\(\theta > \kappa \geq \omega\) とする.\(S \in [H(\theta)]^{\leq 2^\kappa}\) とおくと,\(M \preccurlyeq H(\theta)\) で次を満たすものが存在する:

  1. \(S \subseteq M\)

  2. \(M\)\(\kappa^+\)-closed

  3. \(|M| = 2^\kappa\)

Löwenheim-Skolem の定理より \(M_0 \preccurlyeq H(\theta)\)\(S \subseteq M_0\) かつ \(|M_0| = |S| = 2^\kappa\) を満たすものが取れる.\(M_\alpha \preccurlyeq M_\beta \preccurlyeq H(\theta), |M_\alpha| = 2^\kappa\; (\alpha < \beta < \kappa^+)\) なる初等鎖を構成できれば,\(M = \bigcup_{\alpha < \kappa^+} M_\alpha\) が求める物となる.まず,\(\alpha\) が極限順序数の時には \(M_\alpha = \bigcup_{\beta < \alpha} M_\beta\) と置けば,初等鎖定理より \(\beta < \alpha \rightarrow M_\beta \preccurlyeq M_\alpha\) となり,濃度の条件も OK.つづいて \(\alpha = \beta + 1\) とする.この時,\((2^{\kappa})^{<\kappa^+} =(2^\kappa)^{\leq \kappa} = 2^{\kappa \kappa} = 2^\kappa\) に注意すれば,\(S_\alpha = M_\beta \cup [M_\beta]^{<\kappa^+}\) の濃度は \(2^\kappa\) である.そこで Löwenheim-Skolem の定理により \(S_\alpha \subseteq M_\alpha \preccurlyeq H(\theta), |M_\alpha| = 2^\kappa\) なる \(M_\alpha\) を取れば良い.

\(\kappa \geq \lambda, \sigma\) を基数,\(n<\omega\) とする.この時, \[\kappa \longrightarrow (\lambda)^n_\sigma \defs \forall f: [\kappa]^n \to \sigma\, \exists Z \in [\kappa]^\lambda\, \forall A, B \in [Z]^n \left[ f(A) = f(B)\right]\]\(f\) に対する \(Z\) を,分割 \(f\) に関する等質集合(homogeneous set) と呼ぶ.

\(\kappa \geq \lambda \geq \omega\) の時,次が成立: \[\kappa \longrightarrow (\lambda)^1_\sigma \Leftrightarrow \begin{cases} \sigma < \cf(\kappa) & (\kappa = \lambda)\\ \sigma < \kappa & (\kappa > \lambda) \end{cases}\]

\(n = 1\) のとき,\(\kappa \longrightarrow (\lambda)^1_\sigma\) は次と同値であることが判る: \[\forall f : \kappa \rightarrow \sigma \, \exists \alpha < \sigma \, (|f^{-1}[\{\alpha\}]| \geq \lambda)\]

まずは \(\kappa = \lambda\) の時を考え,対偶を示す. \(\sigma \geq \cf(\kappa)\) の時,\(A = \set{a_\alpha : \alpha < \sigma} \in [\kappa]^\sigma\)\(\kappa\) の共終部分集合とする.\(f : \kappa \rightarrow \sigma\)\(f(\alpha) = \min \Set{\gamma }{ \alpha \leq a_\gamma}\) により定める.すると,各 \(\gamma < \sigma\) に対し \(|f^{-1}[\{\gamma\}]| \leq |a_\gamma| < \kappa\) となるので \(\kappa \nrightarrow (\kappa)^1_\sigma\).逆に \(\kappa \nrightarrow (\kappa)^1_\sigma\) とする.\(f: \kappa \rightarrow \sigma\)\(|f^{-1}[\{\beta\}]| < \kappa\) を満たすようなものとする.この時 \(\kappa = \bigcup_{\beta < \sigma} f^{-1}[\{\beta\}]\) より \(\sigma \geq \cf(\sigma)\) となる.よって示された.

今度は \(\lambda < \kappa\) とし対偶を示す.\(\sigma = \kappa\) とすると,恒等関数 \(id: \kappa \rightarrow \kappa\) を考えれば \(f^{-1}[\{\alpha\}] = \{\alpha\}\) より \(\kappa \nrightarrow (\lambda)^1_\kappa\) である.逆に,\(\kappa \nrightarrow (\lambda)^1_\sigma\) とし,\(f : \kappa \rightarrow \sigma\)\(|f^{-1}[\{\alpha\}]| < \lambda\) を満たすとする. \[\kappa = \left|\bigcup_{\beta < \sigma} f^{-1}[\{\beta\}]\right| = \max\left\{ \sigma, \sup_{\beta < \sigma} \left|f^{-1}[\{\beta\}]\right| \right\}\] ここで \(|f^{-1}[\{a\}]| < \lambda\) より \(\sup_{\alpha < \sigma} |f^{-1}[\{\alpha\}]| \leq \lambda < \kappa\) となる事に注意すれば,\(\kappa = \sigma\) となる.

よって,\(n = 0, 1\) の時の \(\kappa \longrightarrow (\lambda)^n_\sigma\) はかなり簡単になるので,興味があるのは \(n \geq 2\) の時である.次は Ramsey による古典的な結果である.本筋の命題ではないので,証明は概略に留める:

\(\forall n, k < \omega\, [\omega \longrightarrow (\omega)^n_k]\)

\(n\) に関する帰納法で示す.\(n = 0\) は先程の議論より自明.\(n\) の時成立を仮定し,\(n+1\) の場合を考える.\(f: [\omega]^{n+1} \rightarrow k\) を固定し,各 \(x \in \omega\) に対し,\(f_x : [\omega \setminus \{x\}]^n \rightarrow k\)\(f_x(A) = f(A \cup \set{x})\) により定める.次を満たす \(H_\ell \in [\omega]^\omega, x_\ell < \omega, i_\ell < k\) を帰納的に構成する:

  1. \(H_\ell \supseteq H_{\ell+1}\)

  2. \(\set{x_\ell : \ell \leq n} \cap H_{n} = \emptyset\)

  3. \(x_\ell \in H_{\ell - 1}\, (\ell \geq 1)\)

  4. \(f_{x_\ell}\left[[H_\ell]^n\right] = \{i_\ell\}\)

すると,\(L = \set{\ell < \omega : i_\ell = i}\) が無限集合になるような \(i < k\) が少なくとも一つ存在する.この時,\(H = \set{x_\ell : \ell \in L}\) が求めるものとなる.

よって特に \(\omega \longrightarrow (\omega)^2_2\).では,等質集合の濃度が非可算となるような,即ち \(\kappa \longrightarrow (\omega_1)^2_2\) が成り立つような \(\kappa\) はどんなものがあるだろうか?実は \((2^\omega)^+\) で十分である:

\((2^\omega)^+ \longrightarrow (\omega_1)^2_\omega\).よって特に \((2^\omega)^+ \longrightarrow (\omega_1)^2_2\)

これは次の Erdős-Rado の定理で \(n=1, \kappa = \omega\) とおけば直ちに従う:

\(\kappa \geq \omega\) とする. \[\mathrm{exp}_0(\kappa) = \kappa, \mathrm{exp}_{n+1}(\kappa) = 2^{\exp_n(\kappa)}\] と表すとき,次が成立: \[(\mathrm{exp}_{n}(\kappa))^+ \longrightarrow (\kappa^+)^{n+1}_\kappa\]

\(n\) に関する帰納法で証明する.\(n = 0\) の時は \(\kappa^+ \longrightarrow (\kappa^+)^1_\kappa\) であり,\(\kappa < \kappa^+ = \cf(\kappa^+)\) なので補題 2より成立.

\(n+1\) の場合を考える.以後,簡単の為 \(\mathrm{exp}_n(\kappa) = \chi_n\) と略記する.帰納法の仮定は, \[(\chi_n)^+ \longrightarrow (\kappa^+)^{n+1}_\kappa\] である.\(f: [\chi_{n+1}^+]^{n+2} \longrightarrow \kappa\) を固定し,\(Z \in [\chi_{n+1}^+]^{\kappa^+}\)\(f\) について等質となるものを得たい.そこで,まず \(f, \chi_{n+1}^+ \in H(\theta), \kappa \subseteq H(\theta)\) を満たす十分大きな \(\theta > \omega\) を取り,その \(\chi_n^+\)-closed な初等部分構造 \(M \preccurlyeq H(\theta)\)\(f, \chi_{n+1}^+ \in M\) かつ \(\kappa \subseteq M\) となるものを取る.補題 1 より,特に \(|M| = 2^{\chi_n} = \chi_{n+1}\) とできる.すると,\(|M \cap \chi_{n+1}^+| \leq \chi_{n+1}\) となり,\(\chi_{n+1}^+\) の正則性より \(j = \sup^+(\chi_{n+1}^+ \cap M) \in \chi_{n+1}^+\) が取れる.

以下,各 \(\xi < \chi_{n}^+\) に対し, \[\forall \eta < \xi \, [ i_\eta < i_\xi] \wedge \forall \eta_0, \dots, \eta_n < \xi \, [f(\{i_{\eta_0}, \dots, i_{\eta_n}, i_\xi\}) = f(\{i_{\eta_0}, \dots, i_{\eta_n}, j\})]\] を満たすよう帰納的に \(\Braket{i_\xi \in \chi_{n+1}^+ \cap M }{ \xi < \chi_n^+}\) を定めたい.そこで,\(\xi\) 未満まで出来たとし,\(D = \set{ i_\eta : \eta < \xi} \subseteq M \cap \chi_{n+1}^+\) とおく.この時 \(|D| = |\xi| < \chi_n^+\) なので,\(M\)\(\chi_n^+\)-closed 性から \(D \in M\) となる.また,\(M\) は有限部分集合について閉じるから,\(D \subseteq M\) より \([D]^{n+1} \subseteq M\) となり,更に \(|[D]^{n+1}| = |D| < \chi_n^+\) から \([D]^{n+1} \in M\) も云える.そこで,\(g : [D]^{n+1} \rightarrow \kappa\)\(g(A) = f(A \cup \{j\})\) により定める.すると,\(\kappa \subseteq M\) となるように取っており,\(H(\theta)\)\(\mathrm{ZFC}-\mathrm{P}\)(特に対の公理)が成り立つことから \([D]^{n+1} \times \kappa \subseteq M\).よって \(g \subseteq [D]^{n+1} \times \kappa \subseteq M\) となり,特に \(|g| < \chi_n^+\) だからみたび \(M\)\(\chi_n^+\)-closed 性より \(g \in M\) が言える.今, \[H(\theta) \models \exists y \in \chi_{n+1}^+\;\left[ \forall i \in D\, (i < y) \wedge \forall A \in [D]^{n+1}\, (f(A \cup \{y\}) = g(A))\right]\] が成立する(\(y\) として \(j\) が取れる).この右辺の論理式に現れるパラメータ \(\chi_{n+1}^+, D, [D]^{n+1}, f, g\) は全て \(M\) の元であり,\(M \preccurlyeq H(\theta)\) であるので,\(M\) でも成立する.そこで \(i_\xi\) としてそのような \(y\) を取れば良い.

\(W = \set{ i_\xi : \xi < \chi_n^+}\) と置く.この時 \(f_j(A) = f(A \cup \{j\})\) により \(f_j: [W]^{n+1} \rightarrow \kappa\) を定める.帰納法の仮定を分割 \(f_j\)\(W\) に適用すれば,\(Z \in [W]^{\kappa^+}, \alpha < \kappa\)\(f_j[[Z]^{n+1}] = \{\alpha\}\) となるような物が取れる.この時,\(A = \{i_{\xi_0} < \dots < i_{\xi_n} < i_{\xi_{n+1}}\} \in [Z]^{n+2}\;(\xi_k < \xi_{k+1})\) を任意に取れば, \[f(A) = f(\{i_{\xi_0}, \dots, i_{\xi_n}, i_{\xi_{n+1}}\}) = f(\{i_{\xi_0}, \dots, i_{\xi_n}, j\}) = f_j(\{i_{\xi_0}, \dots, i_{\xi_n}\}) = \alpha\] ここで \(A = \set{i_{\xi_0}, \dots, i_{\xi_{n+1}}}\) の取り方は任意なので,\(Z\)\(f\) について等質であることが示せた.

関連する問題

\((2^\omega)^+\) が最小であること

上での議論から,\(\kappa \geq (2^\omega)^+\) ならば \(\kappa \longrightarrow (\omega_1)^2_2\) が成立することがわかる.この値は最小なのだろうか?次の Sierpinski の議論から,\(2^\omega\) では不十分であり,この結果が optimal であることがわかる:

\(2^\omega \nrightarrow (\omega_1)^2_2\)

より一般に,次が成り立つ:

\(\kappa \geq \omega\) に対し,\(2^\kappa \nrightarrow (\kappa^+)^2_2\).よって特に \(2^\kappa \nrightarrow (\kappa^+)^2_\kappa\)

問題になるのは濃度だけなので,\(\power{\kappa}{2}\) を考える.\(<\)\(\power{\kappa}{2}\) 上の辞書式順序,\(\lhd\)\(\power{\kappa}{2}\) 上のある整列順序とする.この時,関数 \(f : [\power{\kappa}{2}]^2 \rightarrow 2\) を次で定義する: \[f(\{x, y\}) \defeq \begin{cases} 0 & (x < y \Leftrightarrow x \lhd y)\\ 1 & (otherwise) \end{cases}\] もし分割 \(f\) に関する等質集合 \(Z \in [\power{\kappa}{2}]^{\kappa^+}\) が存在したとすれば,\(Z\) は辞書式順序 \(<\) またはその逆順序 \(>\) により整列され,特に \(\kappa^+\)- 型の昇鎖または降鎖を含むことになる.次の主張を示せば証明は完了する:

昇鎖でも降鎖でも議論は同じなので,以下昇鎖の場合を考える.\(\Braket{f_\alpha }{ \alpha < \kappa^+}\)\(f_\alpha < f_\beta \; (\alpha < \beta)\) を満たす \(\power{\kappa}{2}\) の昇鎖とする.この時,\(\gamma \leq \kappa\)\(\set{ f_\alpha \restr \gamma : \alpha < \kappa^+}\) が濃度 \(\kappa^+\) となるような最小の物とする.そこで,最初の昇鎖は \(f_\alpha \restr \gamma = f_\beta \restr \gamma \Rightarrow f_\alpha = f_\beta\) を満たすとして一般性を失わない.

\(\alpha < \kappa^+\) に対し,\(f_\alpha \restr \xi_\alpha = f_{\alpha+1} \restr \xi_\alpha\) かつ \(f_\alpha(\xi_\alpha) = 0, f_{\alpha+1}(\xi_\alpha) = 1\) となるような \(\xi_\alpha\) を取る.これは辞書式順序の定義から一意に定まる.\(\gamma \leq \xi_\alpha\) とすると \(f_\alpha \restr \xi_\alpha \neq f_{\alpha+1} \restr \xi_\alpha\) となってしまうので,\(\xi_\alpha < \gamma\) であることに注意しよう.この時,\(\kappa^+\) の正則性より \(A = \set{\alpha < \kappa^+ : \xi_\alpha = \xi}\) の濃度が \(\kappa^+\) になるような \(\xi < \gamma < \kappa^+\) が取れる.\(\alpha, \beta \in A\) かつ \(f_\alpha \restr \xi = f_\beta \restr \xi\) とする.このとき \(\xi = \xi_\alpha = \xi_\beta\) なので,\(f_{\alpha+1} \restr \xi_\beta = f_{\alpha+1} \restr \xi_\alpha = f_\alpha \restr \xi_\alpha = f_\beta \restr \xi_\beta\) となる.また \(\xi_\alpha\) の取り方より \(f_{\alpha+1}(\xi_{\beta}) = 1\) である.このような条件を満たす \(\delta\) の中で \(\beta+1\) は最小なので,\(\beta+1 \leq \alpha+1\) となる.同様の議論により \(\alpha+1\leq\beta+1\) となり,従って \(\alpha=\beta\) となる.よって,\(\set{f_\alpha \restr \xi : \alpha \in A}\) の濃度は \(\kappa^+\) である.しかし,これは \(\gamma\) の最小性に反する.

有限組合せ論

\(\kappa, \lambda < \omega\) の場合は(有限)組合せ論の非自明な問題である.以下に二つだけ例を挙げる:

参考文献

[1] K. Kunen, Set Theory, vol. 34. College Publications, 2011.

[2] T. Jech, Set Theory: The Third Millennium Edition, revised and expanded, 3rd ed. Springer-Verlag Berlin Heidelberg New York, 2002.

[3] A. Kanamori, The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings. Springer, 2009.

[4] 根上生也, グラフ理論3段階, vol. 2. 遊星社, 1990.

[5] 田中一之, 坪井明人, and 野本和幸, ゲーデルと20世紀の論理学(ロジック) 2 完全性定理とモデル理論, vol. 2. 東京大学出版会, 2011.