[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

Proof. 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}

Proof. 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{γ  |  α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

Proof. 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+M  |  ξ<χ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

Proof. 問題になるのは濃度だけなので,κ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^+-型の昇鎖または降鎖を含むことになる.次の主張を示せば証明は完了する:

昇鎖でも降鎖でも議論は同じなので,以下昇鎖の場合を考える.fα  |  α<κ+\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]
根上生也, グラフ理論3段階, vol. 2. 遊星社, 1990.
[2]
田中一之, 坪井明人, and 野本和幸, ゲーデルと20世紀の論理学(ロジック) 2 完全性定理とモデル理論, vol. 2. 東京大学出版会, 2011.
[3]
K. Kunen, Set theory, vol. 34. College Publications, 2011.
[4]
T. Jech, Set theory: The third millennium edition, revised and expanded, 3rd ed. Springer-Verlag Berlin Heidelberg New York, 2002.
[5]
A. Kanamori, The higher infinite: Large cardinals in set theory from their beginnings. Springer, 2009.

Comments