§E1.22基数算術

証明. 全単射$f\colon A\to A'$と$g\colon B\to B'$を取る。写像

は、$f^{-1}$と$g^{-1}$から同じ形で作った写像を逆写像にもつので、§E1.1 命題 3.8により全単射である。写像

も同様に$(a',b')\mapsto(f^{-1}(a'),g^{-1}(b'))$を逆写像にもつ全単射である。

写像$u\colon B^{A}\to B'^{A'}$を$u(h)=g\circ h\circ f^{-1}$で定める。$h\in B^{A}$に対して$g\circ h\circ f^{-1}$は$A'$から$B'$への写像であるから、$u$は定まる。$u'(h')=g^{-1}\circ h'\circ f$で定まる写像$u'\colon B'^{A'}\to B^{A}$は

を満たすので、$u'$は$u$の逆写像であり、§E1.1 命題 3.8により$u$は全単射である。▨

証明.(1)「基数とアレフ」の§E1.21 定義 1.1により、基数とは、それより小さいどの順序数とも等濃でない順序数である。$\mu$を$\kappa$と等濃度な基数とすると、$\mu<\kappa$ならば$\kappa$が基数であることに反し、$\kappa<\mu$ならば$\mu$が基数であることに反する。順序数$\kappa,\mu$は§E1.16 定義 2.1の大小について比較可能であるから$\mu=\kappa$である。恒等写像は$\kappa$から$\kappa$への全単射であるから、$\kappa$自身が$\kappa$と等濃度な基数であり、$\lvert\kappa\rvert=\kappa$である。

(2)(1)により$\lvert\kappa\rvert=\kappa$かつ$\lvert\lambda\rvert=\lambda$であるから、定義 1.1の$A,B$として順序数$\kappa,\lambda$を取ればよい。

(3)§E1.2 定義 5.1により$\prod_{s\in S}A_s$の元は$S$を定義域とし、各$s$での値が$A_s=Y$に属する族である。族$x$に対して、$S$を定義域、$Y$を終域、$x$の値を対応とする写像$\widehat x\colon S\to Y$を与えると、$x\mapsto\widehat x$は$\prod_{s\in S}A_s$から$Y^{S}$への写像である。逆に$h\in Y^{S}$に対して、$S$上で$h$と同じ値を取る族を対応させると、二つの対応は互いに逆であるから、§E1.1 命題 3.8により$x\mapsto\widehat x$は全単射である。したがって定義 1.1により$\bigl\lvert\prod_{s\in S}A_s\bigr\rvert=\lvert Y^{S}\rvert=\lvert Y\rvert^{\lvert S\rvert}$である。▨

証明. 代表集合$A,A',B,B'$を$\lvert A\rvert=\kappa$、$\lvert A'\rvert=\kappa'$、$\lvert B\rvert=\lambda$、$\lvert B'\rvert=\lambda'$となるように取る。

(1)写像$A\sqcup B\to B\sqcup A$を$(a,0)\mapsto(a,1)$、$(b,1)\mapsto(b,0)$で定めると、同じ形の写像を逆写像にもつので全単射である。写像$A\times B\to B\times A$、$(a,b)\mapsto(b,a)$も同様である。

(2)§E1.18 定義 1.1により単射$f\colon A\to A'$と$g\colon B\to B'$が存在する。命題 1.2の証明と同じ式で定めた$s\colon A\sqcup B\to A'\sqcup B'$と$t\colon A\times B\to A'\times B'$は、$f,g$が単射であれば単射である。実際$s(a,0)=s(a',0)$ならば$f(a)=f(a')$から$a=a'$であり、第二の成分が異なる二元の像は第二の成分が異なる。$t(a,b)=t(a',b')$ならば$f(a)=f(a')$かつ$g(b)=g(b')$から$(a,b)=(a',b')$である。

(3)$0=\emptyset$であるから$A\sqcup\emptyset=A\times\{0\}$であり、$a\mapsto(a,0)$は全単射である。$A\times\emptyset=\emptyset$である。$1=\{0\}$であるから$\{0\}\times A\to A$、$(0,a)\mapsto a$は全単射である。$A^{\{0\}}\to A$、$h\mapsto h(0)$は全単射であり、$A^{\emptyset}$は空写像だけからなる一元集合である。$\lambda\geq1$ならば$B$は元$b_0$をもち、$a\mapsto(a,b_0)$は単射$A\to A\times B$である。$a\mapsto(a,0)$は単射$A\to A\sqcup B$である。

(4)§E1.16 定義 2.1の von Neumann 自然数により$2=\{0,1\}$であるから

である。$\lvert 2\rvert=2$であるから定義 1.1により$\kappa+\kappa=\lvert A\times 2\rvert=\kappa\cdot 2=2\kappa$である。▨

証明.$2=\{0,1\}$とし、$S\subseteq X$に対してその特性関数$\chi_S\colon X\to 2$を、$x\in S$のとき$\chi_S(x)=1$、$x\notin S$のとき$\chi_S(x)=0$と定める。写像$\Phi\colon\mathcal P(X)\to 2^{X}$、$\Phi(S)=\chi_S$を考える。$h\in 2^{X}$に対して$\Psi(h)=\{x\in X\mid h(x)=1\}$とおくと、$\Psi(h)\subseteq X$である。任意の$S\subseteq X$について$\Psi(\Phi(S))=\{x\in X\mid\chi_S(x)=1\}=S$であり、任意の$h\in 2^{X}$と$x\in X$について$\chi_{\Psi(h)}(x)=1$と$h(x)=1$は同値で、値は$0$と$1$の二つしかないので$\Phi(\Psi(h))=h$である。よって$\Psi$は$\Phi$の逆写像であり、§E1.1 命題 3.8により$\Phi$は全単射である。定義 1.1により$\lvert 2^{X}\rvert=\lvert 2\rvert^{\lvert X\rvert}=2^{\lvert X\rvert}$であるから、結論を得る。▨

証明.$\lvert C\rvert=\kappa$、$\lvert B\rvert=\lambda$、$\lvert A\rvert=\mu$となる集合$A,B,C$を取る。

(1)写像$F\colon C^{B\times A}\to(C^{B})^{A}$を、$h\in C^{B\times A}$と$a\in A$、$b\in B$に対して$F(h)(a)(b)=h(b,a)$と定める。各$a$について$F(h)(a)$は$B$から$C$への写像であり、$F(h)$は$A$から$C^{B}$への写像である。逆に$k\in(C^{B})^{A}$に対して$G(k)(b,a)=k(a)(b)$とおくと$G(k)\in C^{B\times A}$であり、$G(F(h))=h$かつ$F(G(k))=k$である。よって§E1.1 命題 3.8により$F$は全単射であり、定義 1.1により$\kappa^{\lambda\mu}=\lvert C^{B\times A}\rvert=\lvert(C^{B})^{A}\rvert=(\kappa^{\lambda})^{\mu}$である。

(2)写像$C^{B\sqcup A}\to C^{B}\times C^{A}$を$h\mapsto(h_1,h_2)$、$h_1(b)=h(b,0)$、$h_2(a)=h(a,1)$と定める。$(h_1,h_2)$から$h(b,0)=h_1(b)$、$h(a,1)=h_2(a)$によって$h$が復元されるので、この写像は逆写像をもち、§E1.1 命題 3.8により全単射である。

(3)写像$(C\times B)^{A}\to C^{A}\times B^{A}$を$h\mapsto(\operatorname{pr}_1\circ h,\operatorname{pr}_2\circ h)$と定める。ここで$\operatorname{pr}_1,\operatorname{pr}_2$は$C\times B$の二つの成分を取り出す写像である。$(k_1,k_2)$から$h(a)=(k_1(a),k_2(a))$によって$h$が復元されるので、この写像も逆写像をもつ全単射である。▨

証明.(1)$(\alpha,\beta)\in\theta\times\theta$とする。§E1.16 定義 2.1により$\theta$は所属関係によって整列された推移的集合であるから、$\theta$の任意の二元は大小について比較可能であり、$\max(\alpha,\beta)$は$\alpha$か$\beta$のいずれかに等しく、$\theta$に属する。定義 2.1の三条件は、どの二つも$\max$の値または$\alpha$の値について両立しないので、$(\alpha,\beta)\prec(\gamma,\delta)$を与える条件は高々一つである。とくに$(\alpha,\beta)\prec(\alpha,\beta)$はどの条件からも成り立たない。

$(\alpha,\beta)\neq(\gamma,\delta)$とする。$\max(\alpha,\beta)\neq\max(\gamma,\delta)$ならば、比較可能性により定義 2.1 (1)がどちらか一方の向きで成り立つ。$\max(\alpha,\beta)=\max(\gamma,\delta)$かつ$\alpha\neq\gamma$ならば定義 2.1 (2)がどちらか一方の向きで成り立つ。$\max$が等しく$\alpha=\gamma$ならば$\beta\neq\delta$であり、定義 2.1 (3)がどちらか一方の向きで成り立つ。よって相異なる二元は必ず一方の向きで比較される。

$(\alpha,\beta)\prec(\gamma,\delta)\prec(\epsilon,\zeta)$とし、$m_1=\max(\alpha,\beta)$、$m_2=\max(\gamma,\delta)$、$m_3=\max(\epsilon,\zeta)$とおく。定義 2.1の三条件のいずれの場合も$m_1\leq m_2$かつ$m_2\leq m_3$であるから$m_1\leq m_3$である。$m_1<m_3$ならば定義 2.1 (1)により$(\alpha,\beta)\prec(\epsilon,\zeta)$である。$m_1=m_3$ならば$m_1=m_2=m_3$であり、定義 2.1 (2)と定義 2.1 (3)から$\alpha\leq\gamma\leq\epsilon$を得る。$\alpha<\epsilon$ならば定義 2.1 (2)により結論を得る。$\alpha=\epsilon$ならば$\alpha=\gamma=\epsilon$であり、定義 2.1 (3)から$\beta<\delta<\zeta$を得るので、同じ条件により結論を得る。

$S$を$\theta\times\theta$の空でない部分集合とする。$M=\{\max(\xi,\eta)\mid(\xi,\eta)\in S\}$は$\theta$の空でない部分集合であるから、§E1.16 定義 2.1により最小元$\gamma_0$をもつ。$S_0=\{(\xi,\eta)\in S\mid\max(\xi,\eta)=\gamma_0\}$は空でなく、$\{\xi\mid(\xi,\eta)\in S_0\}$は$\theta$の空でない部分集合であるから最小元$\alpha_0$をもつ。さらに$\{\eta\mid(\alpha_0,\eta)\in S_0\}$も$\theta$の空でない部分集合であるから最小元$\beta_0$をもつ。$(\xi,\eta)\in S$が$(\xi,\eta)\prec(\alpha_0,\beta_0)$を満たすとすると、定義 2.1 (1)では$\max(\xi,\eta)<\gamma_0$となって$\gamma_0$の最小性に反し、定義 2.1 (2)では$(\xi,\eta)\in S_0$かつ$\xi<\alpha_0$となって$\alpha_0$の最小性に反し、定義 2.1 (3)では$(\alpha_0,\eta)\in S_0$かつ$\eta<\beta_0$となって$\beta_0$の最小性に反する。よって$(\alpha_0,\beta_0)$は$S$の最小元であり、$\prec$は整列順序である。

(2)$(\xi,\eta)\prec(\alpha,\beta)$とする。定義 2.1の三条件のいずれの場合も$\max(\xi,\eta)\leq\max(\alpha,\beta)=\gamma$であり、$\xi\leq\max(\xi,\eta)$かつ$\eta\leq\max(\xi,\eta)$であるから$\xi\leq\gamma$かつ$\eta\leq\gamma$である。§E1.16 命題 4.2により$\gamma+1$は$\gamma$より真に大きい最小の順序数であるから、$\xi\leq\gamma$は$\xi<\gamma+1$と同値であり、$\eta$についても同様である。よって$(\xi,\eta)\in(\gamma+1)\times(\gamma+1)$である。▨

証明.(2)$\alpha<\kappa$とする。§E1.16 命題 4.2により$\alpha+1$は$\alpha$より真に大きい最小の順序数であるから、$\alpha<\kappa$から$\alpha+1\leq\kappa$を得る。$\alpha+1=\kappa$と仮定して矛盾を導く。

$\alpha<\omega$の場合を見る。「実数体の構成」の§E1.14 命題 1.2により$\omega$は帰納的集合であるから、$\alpha\in\omega$から$\alpha+1\in\omega$である。すると$\kappa=\alpha+1<\omega$となり、$\omega\leq\kappa$に反する。

$\omega\leq\alpha$の場合を見る。写像$h\colon\alpha+1\to\alpha$を

と定める。$n<\omega$に対して$\omega$が帰納的集合であることから$n+1<\omega\leq\alpha$であり、$\omega\leq\xi<\alpha$に対して$h(\xi)=\xi<\alpha$であるから、$h$の値はすべて$\alpha$に属する。$h$は単射である。実際、値$0$を取るのは$\alpha$だけであり（§E1.14 命題 1.2の Peano の公理により$0$は自然数の後続ではない）、$\omega$未満の相異なる二つの自然数の後続は相異なり、$\omega$以上の相異なる二元の像は相異なり、三つの場合の像はそれぞれ$\{0\}$、$\{n+1\mid n<\omega\}$、$[\omega,\alpha)$に含まれて互いに交わらない。$h$は全射でもある。実際$\zeta<\alpha$とすると、$\zeta=0$ならば$h(\alpha)=\zeta$であり、$0\neq\zeta<\omega$ならば§E1.14 命題 1.2の帰納法により$\zeta=n+1$を満たす自然数$n$が存在して$h(n)=\zeta$であり、$\omega\leq\zeta$ならば$h(\zeta)=\zeta$である。

よって$\alpha+1$と$\alpha$は等濃度であり、$\kappa=\alpha+1$という仮定から$\kappa$と$\alpha$が等濃度になる。$\alpha<\kappa$であるから、これは§E1.21 定義 1.1により$\kappa$が基数であることに反する。

以上により$\alpha+1\neq\kappa$であり、$\alpha+1<\kappa$である。これで(2)が示された。

(1)上の議論は$\kappa$未満のどの順序数についても成り立つので、$\kappa$はどの順序数の後続でもない。$\omega\leq\kappa$から$\kappa\neq0$であるから、§E1.16 定義 4.1により$\kappa$は極限順序数である。▨

証明. 順序数$\kappa$についての性質を「$\kappa$が無限基数ならば$\kappa\times\kappa$から$\kappa$への全単射が存在する」と取り、「超限帰納法と超限再帰」の§E1.17 定理 1.1を順序数の全体にわたる形で用いる。すなわち、無限基数$\kappa$を取り、$\kappa$未満のすべての無限基数$\mu$について$\mu\times\mu$から$\mu$への全単射が存在すると仮定して、$\kappa$について同じことを示す。

$\kappa=\omega$のときは、「等濃度と可算性」の§E1.18 補題 3.8が全単射$\omega\times\omega\to\omega$を与える。以下$\omega<\kappa$とする。

補題 2.2 (1)により、$\kappa\times\kappa$は定義 2.1の Gödel 順序$\prec$によって整列される。「順序数」の§E1.16 定理 3.1により、順序同型$f\colon(\kappa\times\kappa,\prec)\to(\theta,{\in})$をもつ順序数$\theta$がただ一つ存在する。

$\kappa<\theta$と仮定する。$f$は全射であるから、$f(\alpha,\beta)=\kappa$を満たす$(\alpha,\beta)\in\kappa\times\kappa$が存在する。$f$は順序同型であるから、$f$の$S=\{(\xi,\eta)\mid(\xi,\eta)\prec(\alpha,\beta)\}$への制限は$S$から$\{\zeta\mid\zeta<\kappa\}=\kappa$への全単射である。

$\gamma=\max(\alpha,\beta)$とおくと$\gamma<\kappa$であり、補題 2.2 (2)により$S\subseteq(\gamma+1)\times(\gamma+1)$である。補題 3.1により$\gamma+1<\kappa$である。集合$\{\xi\mid\xi\leq\gamma+1,\ \xi\text{ は }\gamma+1\text{ と等濃度}\}$は$\gamma+1$を含んで空でない順序数からなる集合であるから、§E1.16 命題 2.5 (3)により最小元$\mu_0$をもつ。$\mu_0$より小さい順序数が$\mu_0$と等濃度ならば、それは$\gamma+1$とも等濃度になって最小性に反するので、$\mu_0$は§E1.21 定義 1.1の意味の基数である。$\mu_0\leq\gamma+1<\kappa$である。

$\nu=\max(\mu_0,\omega)$とおく。$\mu_0<\kappa$かつ$\omega<\kappa$であるから$\nu<\kappa$であり、$\omega\leq\nu$である。$\nu$は基数である。実際$\omega\leq\mu_0$ならば$\nu=\mu_0$であり、$\mu_0<\omega$ならば$\nu=\omega$であって、$\omega$より小さい順序数は自然数であるから$\omega$と等濃度でない。よって$\nu$は$\kappa$未満の無限基数であり、帰納の仮定により全単射$q\colon\nu\times\nu\to\nu$が存在する。

$\gamma+1$は$\mu_0$と等濃度であり$\mu_0\subseteq\nu$であるから、単射$j\colon\gamma+1\to\nu$が存在する。したがって$(\xi,\eta)\mapsto q(j(\xi),j(\eta))$は$(\gamma+1)\times(\gamma+1)$から$\nu$への単射である。$f$の逆写像を$\kappa$へ制限したものは$\kappa$から$S$への全単射であり、これに上の単射の$S$への制限を合成すると、単射$\kappa\to\nu$を得る。一方$\nu<\kappa$から$\nu\subseteq\kappa$であり、包含は単射$\nu\to\kappa$である。「Dedekind–MacNeille 完備化」の§E1.11 定理 4.2により$\kappa$と$\nu$は等濃度となるが、$\nu<\kappa$であるから、これは§E1.21 定義 1.1により$\kappa$が基数であることに反する。よって$\theta\leq\kappa$である。

$\theta\leq\kappa$から$\theta\subseteq\kappa$であるから、$f$は単射$\kappa\times\kappa\to\kappa$である。逆に$\alpha\mapsto(\alpha,0)$は単射$\kappa\to\kappa\times\kappa$である。§E1.11 定理 4.2により全単射$p\colon\kappa\times\kappa\to\kappa$が存在する。

命題 1.3 (1)により$\lvert\kappa\rvert=\kappa$であるから、定義 1.1と$p$により$\kappa\cdot\kappa=\lvert\kappa\times\kappa\rvert=\kappa$である。$\omega\leq\kappa$から$2\leq\kappa$であり、命題 1.4 (4)と命題 1.4 (2)により

である。また命題 1.4 (3)により$\kappa\leq\kappa+\kappa$であるから、§E1.18 定義 1.1の比較と§E1.11 定理 4.2により$\kappa+\kappa=\kappa$である。▨

証明.$\kappa\leq\lambda$と命題 1.4 (2)により$\kappa+\lambda\leq\lambda+\lambda$かつ$\kappa\lambda\leq\lambda\lambda$である。定理 3.2により$\lambda+\lambda=\lambda$かつ$\lambda\lambda=\lambda$であるから、$\kappa+\lambda\leq\lambda$かつ$\kappa\lambda\leq\lambda$である。

$\kappa>0$であるから、$\kappa$と$\lambda$の役割を入れ替えて命題 1.4 (3)を用いると$\lambda\leq\lambda\kappa$かつ$\lambda\leq\lambda+\kappa$である。命題 1.4 (1)により$\lambda\kappa=\kappa\lambda$かつ$\lambda+\kappa=\kappa+\lambda$であるから、$\lambda\leq\kappa\lambda$かつ$\lambda\leq\kappa+\lambda$である。

命題 1.3 (1)により$\lvert\kappa\rvert=\kappa$、$\lvert\lambda\rvert=\lambda$であるから、命題 1.3 (2)により$\kappa+\lambda=\lvert\kappa\sqcup\lambda\rvert$、$\kappa\lambda=\lvert\kappa\times\lambda\rvert$である。以上の二つの向きの不等式は、§E1.18 定義 1.1により単射$\kappa\sqcup\lambda\to\lambda$と単射$\lambda\to\kappa\sqcup\lambda$、および単射$\kappa\times\lambda\to\lambda$と単射$\lambda\to\kappa\times\lambda$の存在を意味する。§E1.11 定理 4.2により全単射$\kappa\sqcup\lambda\to\lambda$と全単射$\kappa\times\lambda\to\lambda$が存在し、$\kappa+\lambda=\kappa\lambda=\lambda$である。▨

証明.$\mu$は基数であるから§E1.21 定理 2.2 (3)により$\lvert\mu\rvert=\mu$である。各$i\in I$について$\lvert A_i\rvert\leq\mu=\lvert\mu\rvert$であるから、単射$u_i\colon A_i\to\mu$が存在する。選択公理により、この単射をすべての$i\in I$について同時に選ぶ。さらに各$x\in\bigcup_{i\in I}A_i$に対して$x\in A_{i(x)}$を満たす$i(x)\in I$を一つ選び、$v(x)=(i(x),u_{i(x)}(x))$と定める。$v(x)=v(y)$ならば$i(x)=i(y)$であり、$u_{i(x)}$の単射性から$x=y$である。よって$v$は$\bigcup_{i\in I}A_i$から$I\times\mu$への単射である。したがって命題 1.4 (2)と定理 3.2により