[PDF版]

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

定義と準備

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

κω\kappa \geq \omega とする.MMκ\kappa-closed [M]<κM\Leftrightarrow [M]^{<\kappa} \subseteq M

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

  1. SMS \subseteq M

  2. MMκ+\kappa^+-closed

  3. M=2κ|M| = 2^\kappa

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

κλ,σ\kappa \geq \lambda, \sigma を基数,n<ωn<\omega とする.この時, κ(λ)σndeff:[κ]nσZ[κ]λA,B[Z]n[f(A)=f(B)]\kappa \longrightarrow (\lambda)^n_\sigma \xLeftrightarrow{\mathrm{def}} \forall f: [\kappa]^n \to \sigma\, \exists Z \in [\kappa]^\lambda\, \forall A, B \in [Z]^n \left[ f(A) = f(B)\right]ff に対する ZZ を,分割 ff に関する等質集合(homogeneous set) と呼ぶ.

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

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

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

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

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

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

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

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

  2. {x:n}Hn=\left\{ x_\ell : \ell \leq n \right\} \cap H_{n} = \emptyset

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

  4. fx[[H]n]={i}f_{x_\ell}\left[[H_\ell]^n\right] = \{i_\ell\}

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

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

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

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

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

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

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

以下,各 ξ<χn+\xi < \chi_{n}^+ に対し, η<ξ[iη<iξ]η0,,ηn<ξ[f({iη0,,iηn,iξ})=f({iη0,,iηn,j})]\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\})] を満たすよう帰納的に iξχn+1+Mundefinedξ<χn+\left\langle\: i_\xi \in \chi_{n+1}^+ \cap M \; \middle|\; \xi < \chi_n^+ \:\right\rangle を定めたい.そこで,ξ\xi 未満まで出来たとし,D={iη:η<ξ}Mχn+1+D = \left\{ i_\eta : \eta < \xi \right\} \subseteq M \cap \chi_{n+1}^+ とおく.この時 D=ξ<χn+|D| = |\xi| < \chi_n^+ なので,MMχn+\chi_n^+-closed 性から DMD \in M となる.また,MM は有限部分集合について閉じるから,DMD \subseteq M より [D]n+1M[D]^{n+1} \subseteq M となり,更に [D]n+1=D<χn+|[D]^{n+1}| = |D| < \chi_n^+ から [D]n+1M[D]^{n+1} \in M も云える.そこで,g:[D]n+1κg : [D]^{n+1} \rightarrow \kappag(A)=f(A{j})g(A) = f(A \cup \{j\}) により定める.すると,κM\kappa \subseteq M となるように取っており,H(θ)H(\theta)ZFCP\mathrm{ZFC}-\mathrm{P}(特に対の公理)が成り立つことから [D]n+1×κM[D]^{n+1} \times \kappa \subseteq M.よって g[D]n+1×κMg \subseteq [D]^{n+1} \times \kappa \subseteq M となり,特に g<χn+|g| < \chi_n^+ だからみたび MMχn+\chi_n^+-closed 性より gMg \in M が言える.今, H(θ)yχn+1+[iD(i<y)A[D]n+1(f(A{y})=g(A))]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] が成立する(yy として jj が取れる).この右辺の論理式に現れるパラメータ χn+1+,D,[D]n+1,f,g\chi_{n+1}^+, D, [D]^{n+1}, f, g は全て MM の元であり,MH(θ)M \preccurlyeq H(\theta) であるので,MM でも成立する.そこで iξi_\xi としてそのような yy を取れば良い.

W={iξ:ξ<χn+}W = \left\{ i_\xi : \xi < \chi_n^+ \right\} と置く.この時 fj(A)=f(A{j})f_j(A) = f(A \cup \{j\}) により fj:[W]n+1κf_j: [W]^{n+1} \rightarrow \kappa を定める.帰納法の仮定を分割 fjf_jWW に適用すれば,Z[W]κ+,α<κZ \in [W]^{\kappa^+}, \alpha < \kappafj[[Z]n+1]={α}f_j[[Z]^{n+1}] = \{\alpha\} となるような物が取れる.この時,A={iξ0<<iξn<iξn+1}[Z]n+2(ξk<ξk+1)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ξ0,,iξn,iξn+1})=f({iξ0,,iξn,j})=fj({iξ0,,iξn})=α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={iξ0,,iξn+1}A = \left\{ i_{\xi_0}, \dots, i_{\xi_{n+1}} \right\} の取り方は任意なので,ZZff について等質であることが示せた.

関連する問題

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

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

2ω(ω1)222^\omega \nrightarrow (\omega_1)^2_2

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

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

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

κω\kappa \geq \omega とする.κ2{}^{\kappa} {2} は辞書式順序 << に関する κ+\kappa^+- 型の降鎖・昇鎖を持たない.

昇鎖でも降鎖でも議論は同じなので,以下昇鎖の場合を考える.fαundefinedα<κ+\left\langle\: f_\alpha \; \middle|\; \alpha < \kappa^+ \:\right\ranglefα<fβ(α<β)f_\alpha < f_\beta \; (\alpha < \beta) を満たす κ2{}^{\kappa} {2} の昇鎖とする.この時,γκ\gamma \leq \kappa{fαγ:α<κ+}\left\{ f_\alpha \upharpoonright \gamma : \alpha < \kappa^+ \right\} が濃度 κ+\kappa^+ となるような最小の物とする.そこで,最初の昇鎖は fαγ=fβγfα=fβf_\alpha \upharpoonright \gamma = f_\beta \upharpoonright \gamma \Rightarrow f_\alpha = f_\beta を満たすとして一般性を失わない.

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

有限組合せ論

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

  • 6(3)226 \longrightarrow (3)^2_2 は成立する

    Diagram
  • 5(3)225 \nrightarrow (3)^2_2:次の図が反例(どの三角形も異なる色の辺を含む):

    Diagram

参考文献

  • [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.

Comments