初等部分構造を用いたErdős-Radoの定理の証明 konn-san.com

Proof. 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$を取れば良い．

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

まずは$\kappa = \lambda$の時を考え，対偶を示す． $\sigma \geq \mathrm{cf}(\kappa)$の時，$A = \left\{ a_\alpha : \alpha < \sigma \right\} \in [\kappa]^\sigma$を$\kappa$の共終部分集合とする．$f : \kappa \rightarrow \sigma$を$f(\alpha) = \min \left\{\: \gamma \;\middle|\; \alpha \leq a_\gamma \:\right\}$により定める．すると，各$\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 \mathrm{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$に関する帰納法で示す．$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 \left\{ x \right\})$により定める．次を満たす$H_\ell \in [\omega]^\omega, x_\ell < \omega, i_\ell < k$を帰納的に構成する：

1. $H_\ell \supseteq H_{\ell+1}$

2. $\left\{ x_\ell : \ell \leq n \right\} \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 = \left\{ \ell < \omega : i_\ell = i \right\}$が無限集合になるような$i < k$が少なくとも一つ存在する．この時，$H = \left\{ x_\ell : \ell \in L \right\}$が求めるものとなる．

Proof. $n$に関する帰納法で証明する．$n = 0$の時は$\kappa^+ \longrightarrow (\kappa^+)^1_\kappa$であり，$\kappa < \kappa^+ = \mathrm{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\})]$$ を満たすよう帰納的に$\left\langle\: i_\xi \in \chi_{n+1}^+ \cap M \; \middle|\; \xi < \chi_n^+ \:\right\rangle$を定めたい．そこで，$\xi$未満まで出来たとし，$D = \left\{ i_\eta : \eta < \xi \right\} \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 = \left\{ i_\xi : \xi < \chi_n^+ \right\}$と置く．この時$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 = \left\{ i_{\xi_0}, \dots, i_{\xi_{n+1}} \right\}$の取り方は任意なので，$Z$は$f$について等質であることが示せた．