基数

$x\mapsto\{x\}$ は $X$ から $\mathcal{P}(X)$ への単射なので $|X|\leq|\mathcal{P}(X)|$ である。$f\colon X\to\mathcal{P}(X)$ を任意の写像とし、$D:=\{x\in X\mid x\notin f(x)\}\in\mathcal{P}(X)$ とおく。もし $D=f(d)$ となる $d\in X$ があれば、$d\in D$ と $d\notin f(d)=D$ が同値になって矛盾する。よって $D$ は $f$ の像に属さず、$f$ は全射でない。したがって $X$ から $\mathcal{P}(X)$ への全単射は存在せず、$|X|\neq|\mathcal{P}(X)|$ である。最後の主張は $2^{\kappa}=|\mathcal{P}(\kappa)|$ による。$\square$

$f\colon A\to B$、$g\colon B\to A$ を単射とする。$A$ の部分集合の列を $A_0:=A\setminus g[B]$、$A_{n+1}:=(g\circ f)[A_n]$ で定め、$A^{*}:=\bigcup_{n\in\omega}A_n$ とおく。$a\in A\setminus A^{*}$ なら $a\notin A_0$ なので $a\in g[B]$ であり、$g$ が単射なので $g(b)=a$ となる $b\in B$ がただ一つ定まる。これを $g^{-1}(a)$ と書く。写像 $h\colon A\to B$ を
$$ h(a):=\begin{cases}f(a)&(a\in A^{*})\\ g^{-1}(a)&(a\in A\setminus A^{*})\end{cases} $$
で定める。
$h$ は単射である：$a,a'\in A^{*}$ なら $f$ の単射性から、$a,a'\in A\setminus A^{*}$ なら $g$ の単射性から従う。$a\in A^{*}$、$a'\in A\setminus A^{*}$ で $f(a)=g^{-1}(a')$ とすると、$a'=g(f(a))$ であり、$a\in A_n$ となる $n$ について $a'\in (g\circ f)[A_n]=A_{n+1}\subset A^{*}$ となって $a'\notin A^{*}$ に反する。
$h$ は全射である：$b\in B$ とする。$g(b)\notin A^{*}$ なら $h(g(b))=g^{-1}(g(b))=b$ である。$g(b)\in A^{*}$ なら $g(b)\in A_n$ となる $n$ があり、$g(b)\in g[B]$ なので $n\neq0$、よって $g(b)\in (g\circ f)[A_{n-1}]$ であり、$g$ の単射性から $b\in f[A_{n-1}]$、すなわち $b=f(a)$ となる $a\in A_{n-1}\subset A^{*}$ がある。このとき $h(a)=f(a)=b$ である。$\square$

1. $\kappa:=|X|$ とし、$\beta<\kappa$ が $\kappa$ と対等なら、$\beta$ は $X$ とも対等になり $\kappa$ の最小性に反する。よって $\kappa$ は基数である。$X$ と $Y$ が対等なら、$X$ と対等な順序数全体と $Y$ と対等な順序数全体は一致するので、その最小元 $|X|$ と $|Y|$ は等しい。逆に $|X|=|Y|$ なら $X$ と $|X|=|Y|$ と $Y$ は互いに対等である。単射について：$\kappa:=|X|$、$\lambda:=|Y|$ とおく。$\kappa\leq\lambda$（順序数として）なら $\kappa\subset\lambda$ なので、$X\to\kappa\hookrightarrow\lambda\to Y$ と単射がつながる。逆に $X$ から $Y$ への単射があれば $\kappa$ から $\lambda$ への単射がある。もし $\lambda<\kappa$ なら $\lambda\subset\kappa$ なので $\lambda$ から $\kappa$ への単射（包含）もあり、thm-cardinal-cantor-bernstein から $\lambda$ と $\kappa$ は対等となって、$\kappa$ が基数であることに反する。よって $\kappa\leq\lambda$ である。
2. 恒等写像は単射であり、単射の合成は単射である。三つ目は thm-cardinal-cantor-bernstein そのものである。
3. 整列可能定理により $A,B$ はそれぞれ順序数と対等なので、(1) から $|A|,|B|$ は基数であり、順序数として比較可能（順序数）なので $|A|\leq|B|$ または $|B|\leq|A|$ が成り立つ。基数全体は順序数のクラスの部分クラスなので $<$ で整列されている。基数全体が集合 $K$ であると仮定すると、$\lambda:=\bigcup K$ はすべての基数以上の順序数である。一方 (1) により $|\mathcal{P}(\lambda)|$ は基数であり、もし $|\mathcal{P}(\lambda)|\leq\lambda$ なら $\mathcal{P}(\lambda)$ から $\lambda$ への単射があって thm-cardinal-cantor に反するので $|\mathcal{P}(\lambda)|>\lambda$ となり、矛盾する。$\square$

1. $n$ に関する数学的帰納法。$n=0$ のとき $1=\{0\}$ から $0=\emptyset$ への写像はない。$n$ について成り立つとし、$f\colon n+2\to n+1$ が単射であると仮定する。$n\notin f[n+2]$ なら $f$ の $n+1$ への制限は $n+1$ から $n$ への単射となり帰納法の仮定に反する。$f(k)=n$ となる $k\in n+2$ があれば、$k$ と $n+1$ を入れ替える $n+2$ の全単射 $\sigma$ をとり $f':=f\circ\sigma$ とおくと、$f'$ は単射で $f'(n+1)=n$ なので、$f'$ の $n+1$ への制限は $n+1$ から $n$ への単射となり、やはり矛盾する。
2. $m< n$ が $n$ と対等なら、$m+1\subset n$（順序数）なので全単射 $n\to m$ の $m+1$ への制限が $m+1$ から $m$ への単射となり (1) に反する。よって各 $n$ は基数である。$n<\omega$ が $\omega$ と対等なら、全単射 $\omega\to n$ の $n+1\subset\omega$ への制限が $n+1$ から $n$ への単射となり (1) に反する。よって $\omega$ は基数である。
3. $|B|=n$ とし、全単射 $B\to n$ をとる。$A$ の像 $A'\subsetneq n$ について $|A'|< n$ を示せばよい。$k\in n\setminus A'$ をとり、$k$ と $n-1$ を入れ替える $n$ の全単射で $A'$ を $n-1$ の部分集合 $A''$ に写す。$A''\subset n-1$ なので $|A''|\leq n-1< n$ であり、$|A|=|A''|$ である。
4. $X$ が無限なら $|X|$ は $\omega$ の元でない基数なので $\omega\leq|X|$ である（順序数の比較可能性）。逆に $\omega\leq|X|$ で $|X|=n\in\omega$ なら $\omega\leq n<\omega$ となって矛盾する。$\square$

1. 選択公理の下で $|\mathcal{P}(\kappa)|$ は基数であり、もし $|\mathcal{P}(\kappa)|\leq\kappa$ なら $\mathcal{P}(\kappa)$ から $\kappa$ への単射があって thm-cardinal-cantor に反するので、$|\mathcal{P}(\kappa)|>\kappa$ である。$\kappa$ より大きい基数全体は順序数の空でないクラスなので最小元 $\kappa^{+}$ を持つ（順序数）。$\kappa\geq\omega$ なら $\kappa^{+}>\kappa\geq\omega$ である。
2. $\lambda:=\bigcup K$ は順序数である（順序数）。$\beta<\lambda$ が $\lambda$ と対等であると仮定する。$\beta\in\lambda=\bigcup K$ なので $\beta<\kappa$ となる $\kappa\in K$ があり、$\kappa\leq\lambda$ である。すると $\kappa\hookrightarrow\lambda\to\beta$ と $\beta\hookrightarrow\kappa$ により、thm-cardinal-cantor-bernstein から $\kappa$ と $\beta$ は対等となり、$\kappa$ が基数であることに反する。
3. $\alpha$ に関する超限帰納法（超限帰納法）。$\aleph_0=\omega$ は無限基数である（prop-cardinal-finite）。$\aleph_\alpha$ が無限基数なら (1) により $\aleph_{\alpha+1}=(\aleph_\alpha)^{+}$ は $\aleph_\alpha$ より大きい無限基数である。極限順序数 $\lambda$ について、$\{\aleph_\beta\mid\beta<\lambda\}$ は置換公理により集合であり、(2) からその上限 $\aleph_\lambda$ は基数で、$\beta<\lambda$ なら $\beta+1<\lambda$ より $\aleph_\beta<\aleph_{\beta+1}\leq\aleph_\lambda$ である。これで単調性と無限性が従う。$\alpha\leq\aleph_\alpha$ も同じ帰納法による：$0\leq\aleph_0$、$\alpha\leq\aleph_\alpha<\aleph_{\alpha+1}$ より $\alpha+1\leq\aleph_{\alpha+1}$、極限では $\lambda=\sup_{\beta<\lambda}(\beta+1)\leq\sup_{\beta<\lambda}\aleph_{\beta+1}\leq\aleph_\lambda$ である。$\square$

1. $\varphi\colon A\to A'$、$\psi\colon B\to B'$ を全単射とする（$A\cap B=A'\cap B'=\emptyset$）。$\varphi\cup\psi\colon A\cup B\to A'\cup B'$、$(a,b)\mapsto(\varphi(a),\psi(b))$、$u\mapsto\varphi\circ u\circ\psi^{-1}$（$u\colon B\to A$）はいずれも全単射である。
2. $A\cup B=B\cup A$、$(a,b)\mapsto(b,a)$、$(A\cup B)\cup C=A\cup(B\cup C)$、$((a,b),c)\mapsto(a,(b,c))$、および $A\times(B\cup C)=(A\times B)\cup(A\times C)$（$B\cap C=\emptyset$ なら右辺は非交和）から従う。
3. $B\cap C=\emptyset$ のとき、$u\colon B\cup C\to A$ に $(u|_B,u|_C)$ を対応させる写像 ${}^{B\cup C}A\to{}^{B}A\times{}^{C}A$ は全単射である。$u\colon C\to{}^{B}A$ に $(b,c)\mapsto u(c)(b)$ を対応させる写像 ${}^{C}({}^{B}A)\to{}^{B\times C}A$ は全単射である。$u\colon C\to A\times B$ に成分ごとの写像の組を対応させる写像 ${}^{C}(A\times B)\to{}^{C}A\times{}^{C}B$ は全単射である。
4. 単射 $A\to A'$、$B\to B'$ から、和・積・写像空間の間の単射が誘導される。写像空間については、$u\colon B\to A$ に対し $B'$ 上で「$B$ の像の上では $u$ を移送し、それ以外では $A'$ の固定した一点をとる」写像を対応させればよく、この構成には $A'\neq\emptyset$（$\kappa'\neq0$）が要る。$\kappa'=0$ なら仮定から $\kappa=0$、$\lambda'=0$ なので $\lambda=0$ であり、$0^{0}=1=0^{0}$ である。
5. 自然数の和・積・冪は $m+0=m$、$m+(n+1)=(m+n)+1$ などの再帰で定まり、対応する集合の構成 $A\cup(B\cup\{*\})=(A\cup B)\cup\{*\}$、$A\times(B\cup\{*\})=(A\times B)\cup(A\times\{*\})$、${}^{B\cup\{*\}}A\cong{}^{B}A\times A$ が同じ再帰を満たすので、$n$ に関する帰納法で一致する。$\square$

$\mu:=\max(\kappa,\lambda)$ とおくと $\mu$ は無限基数である。和について：$\mu$ の代表集合は和集合の部分集合なので $\mu\leq\kappa+\lambda$ であり、prop-cardinal-arithmetic-well-defined の 4 から $\kappa+\lambda\leq\mu+\mu$、また $\mu+\mu=\mu\cdot2$（$A\times\{0,1\}=(A\times\{0\})\cup(A\times\{1\})$ は非交和）、$2\leq\mu$ から $\mu\cdot2\leq\mu\cdot\mu$、そして thm-cardinal-square から $\mu\cdot\mu=\mu$ である。あわせて $\mu\leq\kappa+\lambda\leq\mu$ を得る。積について：$\kappa,\lambda\neq0$ なので、$b_0\in B$ を固定すれば $a\mapsto(a,b_0)$ は $A$ から $A\times B$ への単射であり（$\lambda$ 側も同様）、$\mu\leq\kappa\cdot\lambda\leq\mu\cdot\mu=\mu$ を得る。最後の主張は $2^{\kappa}\cdot2^{\kappa}=2^{\kappa+\kappa}=2^{\kappa}$ による。$\square$