$X$ の全順序部分集合全体からなる集合族を $\mathcal{A}$ と定め、各 $A\in \mathcal{A}$ に対して $\hat{A}$ により部分集合 $\{x\in X\mid {}^{\forall}a\in A, \ a < x\}$ を表すとします$A$ の上界全体からなる集合を $U(A)$ で表すとして $\hat{A} = U(A)\setminus A$ です。よって、$\hat{A}\neq \varnothing$ であればその元 $1$ つを $A$ に付け加えることで $A$ より真に大きな全順序部分集合が得られます。。また、\[\mathcal{A}' := \{A\mid A\in \mathcal{A}, \ \hat{A}\neq \varnothing\},\]\[\mathcal{B} := \{\hat{A}\mid A\in \mathcal{A}'\}\]と定め、選択公理 $($公理1.2.14$)$ より選択関数 $\varphi : \mathcal{B}\to X : B\mapsto \varphi(B)\in B$ を取ります。$X$ の全順序部分集合 $K$ であって次の条件を満たすもの全体を $\mathcal{K}$ とおきます。

次のことを示しますあらかじめ言っておくと、各 $K\in \mathcal{K}$ はこのあと紹介する整列集合 $($定義1.4.3$)$ になり、$\mathcal{K}$ はある $1$ つの整列部分集合とその切片全体からなります。。

(step 1) $A\in \mathcal{A}$ が $A\subset K\sqcup \{\varphi(\hat{K})\}$ かつ $(K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}\neq \varnothing$ を満たすとします。もし $\varphi(\hat{K})\in A$ とすると、$\max(K\sqcup \{\varphi(\hat{K})\}) = \varphi(\hat{K})$ と $\hat{A}$ の定義から $x\in (K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}$ に対して $x\leq \varphi(\hat{K}) < x$ となって矛盾するので $\varphi(\hat{K})\notin A$ であり、$A\subset K$ が分かります。

次のそれぞれに対して $\min ((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \varphi(\hat{A})$ を示せばよいです。

(a) $K\in \mathcal{K}$ かつ $A\subset K$ かつ $K\cap \hat{A}\neq \varnothing$ なので $\min (K\cap\hat{A}) = \varphi(\hat{A})$ であり、$\hat{K}$ の定義から $\min (K\cap \hat{A}) < \varphi(\hat{K})$ なので $\min ((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \min (K\cap \hat{A}) = \varphi(\hat{A})$ です。

(b) $K\cap \hat{A} = \varnothing$ のときは $(K\sqcup \{\varphi(\hat{K})\})\cap \hat{A} = \{\varphi(\hat{K})\}$ なので $\min((K\sqcup \{\varphi(\hat{K})\})\cap \hat{A}) = \varphi(\hat{K})$ です。よって、$\hat{A} = \hat{K}$ を示せばよいですが、$A\subset K$ よりただちに $\hat{K}\subset \hat{A}$ が分かるので、その逆の包含関係を示せばよいです。$\hat{a}\in \hat{A}$ とします。$K\cap \hat{A} = \varnothing$ は $k\in K$ であって任意の $a\in A$ に対して $a < k$ となるものが存在しないという意味であり、つまり、任意の $k\in K$ に対してある $a\in A$ が存在して $k\leq a$ となります。よって、任意の $k\in K$ に対してそのような $a\in A$ を取れば $k\leq a < \hat{a}$ であり、$\hat{a}\in \hat{K}$ です。よって、$\hat{A}\subset \hat{K}$ も分かり、$\hat{A} = \hat{K}$ です。

(step 2) $k'\in K'\setminus K$ を取ります。$A := \{x\in K\cap K'\mid x < k'\}$ と定めるとき、当然 $A\subset K'$ かつ $k'\in K'\cap \hat{A}$ なので $\varphi(\hat{A}) = \min (K'\cap \hat{A})\in K'$ であり、$\varphi(\hat{A})\leq k'$ です。

もし $K\cap \hat{A}\neq \varnothing$ とすると、$A\subset K$ と合わせて $\varphi(\hat{A}) = \min (K\cap \hat{A})\in K$ ですが、$k'\notin K$ と $\varphi(\hat{A})\leq k'$ から $\varphi(\hat{A}) < k'$ なので $\varphi(\hat{A})\in K\cap K'$ と合わせて $\varphi(\hat{A})\in A$ が従い、$\varphi(\hat{A})\in \hat{A} = U(A)\setminus A$ に矛盾します。よって、$K\cap \hat{A} = \varnothing$ であり、任意の $k\in K$ に対してある $a\in A$ が存在して $k\leq a$ となります。任意の $a\in A$ に対して $a < k'$ なので、任意の $k\in K$ に対して $k < k'$ であり、$k'\in \hat{K}$ です。以上より $K'\setminus K\subset \hat{K}$ が示されました。

(step 3) 仮に $K'\setminus K\neq \varnothing$ かつ $K\setminus K'\neq \varnothing$ であったとして $k'\in K'\setminus K$ と $k\in K\setminus K'$ を取ると(step 2)から $k < k' < k$ となって矛盾します。よって、$K'\setminus K = \varnothing$ または $K\setminus K' = \varnothing$、つまり、$K'\subset K$ または $K\subset K'$ です。

(step 4) $\tilde{K}$ が全順序部分集合であることは容易。$A\in \mathcal{A}$ が $A\subset \tilde{K}$ かつ $\tilde{K}\cap \hat{A}\neq \varnothing$ を満たしているとします。$k\in \tilde{K}\cap \hat{A}$ を取り、$k\in K$ となる $K\in \mathcal{K}$ を取ります。もし $A\setminus K\neq \varnothing$ とすると $a\in A\setminus K$ に対して $a\in K'$ となる $K'\in \mathcal{K}$ を取ることで $a\in K'\setminus K\subset \hat{K}$ から $k < a$ が従い、$k\in \hat{A}$ に矛盾するので $A\setminus K = \varnothing$、つまり、$A\subset K$ です。

いま、$A\subset K$ かつ $K\cap \hat{A}\neq \varnothing$ なので $\min (K\cap \hat{A}) = \varphi(\hat{A})\in K$ です。任意の $\tilde{k}\in \tilde{K}\setminus K$ に対して $\varphi(\hat{A}) < \tilde{k}$ なので $\min(\tilde{K}\cap \hat{A}) = \min(K\cap \hat{A}) = \varphi(\hat{A})$ です。以上で $\tilde{K}\in \mathcal{K}$ が示されました。

(step 5) もし $\tilde{K}\in \mathcal{A}'$ とすると(step 1)から $\tilde{K}\sqcup \{\varphi(\hat{\tilde{K}})\}\in \mathcal{K}$ であり、$\tilde{K}$ の定義から $\varphi(\hat{\tilde{K}})\in \tilde{K}$ ですがこれは矛盾。よって、$\tilde{K}\notin \mathcal{A}'$、つまり、$\hat{\tilde{K}} = \varnothing$ です。

$\tilde{k}$ を $\tilde{K}$ の上界とします。もし $\tilde{k} < x$ となる $x\in X$ が存在すると $x\in \hat{\tilde{K}} = \varnothing$ となり矛盾するのでそのような $x\in X$ は存在せず、$\tilde{k}$ は $X$ の極大元です。

$X$ が帰納的順序集合なので全順序部分集合である $\tilde{K}$ には上界が存在し、よって、$X$ には極大元が存在します。

(1) 任意の空でない部分集合 $B\subset A$ に対して $\leq_{X}$ に関する最小元が $\leq_{A}$ に関する最小元です。

(2) 定義より $X\langle x\rangle^{c} = \{x'\in X\mid x' <_{X} x\}^{c} = \{x'\in X\mid x\leq_{X} x'\}$ です。明らかに $x\in X\langle x\rangle^{c}$ であり、$\min X\langle x\rangle^{c} = x$ です。

(3) $A\neq X$ の場合に $A = X\langle\min A^{c}\rangle$ であることを示します。$a\in A$ とすると $A$ に課した仮定から任意の $x\in X$ に対して $x\notin A\Rightarrow a < x$ であるので、$\min A^{c}\notin A$ より $a < \min A^{c}$ となり $a\in X\langle\min A^{c}\rangle$ です。よって、$A\subset X\langle\min A^{c}\rangle$ です。$X\langle\min A^{c}\rangle\subset A$ は明らかです。

(4) $\varphi, \psi : X\to Y$ を順序同型写像とします。$\varphi\neq \psi$ として矛盾を導きます。$A := \{x\in X\mid \varphi(x)\neq \psi(x)\}$ とすれば、$\varphi\neq \psi$ より $A\neq \varnothing$ なので $a := \min A$ が取れます。$\varphi(a)\neq \psi(a)$ です。対称性より $\varphi(a) < \psi(a)$ として矛盾を導けば十分です「一般性を失わずに $\varphi(a) < \psi(a)$ としてよい。」という言い回しがされることも。つまりは、$\psi(a) < \varphi(a)$ の場合も全く同じ議論が通用するので省略しますと言ってるだけです。。

$\psi$ は全射なので、ある $b\in X$ であって $\psi(b) = \varphi(a)$ となるものが取れますが、もし $b < a$ とすると $a = \min A$ としていたことから $\varphi(b) = \psi(b) = \varphi(a)$ であり、$\varphi$ の単射性から $a = b$ となり矛盾。もし $a = b$ ならば $\varphi(a) = \psi(b) = \psi(a)$ であり $\varphi(a)\neq \psi(a)$ に矛盾。もし $a < b$ とすると $\psi(b) = \varphi(a) < \psi(a)$ から $\psi$ が順序を保たず矛盾。よって、いずれの場合も矛盾が導かれたので $\varphi = \psi$ です。つまり、整列集合の間の順序同型写像は存在すれば一意です。

(5) 順序同型写像 $\varphi : X\to X\langle x\rangle$ が存在したとして矛盾を導きます。$A := \{x'\in X\mid \varphi(x')\neq x'\}$ と定めるとき、$\varphi(x)\in X\langle x\rangle$ より $\varphi(x) \neq x$ なので $x\in A$ です。よって、$a := \min A$ が取れます。$a\leq x$ ですが、$a = x$ とすると $\varphi(X\langle a\rangle) = X\langle a\rangle = X\langle x\rangle$ となり $\varphi$ の単射性に矛盾するので $a < x$ です。この場合、$\varphi(b) = a$ となる $b\in X$ が取れますが、$b < a$ ならば $\varphi(b) = b < a = \varphi(b)$ となり矛盾。$a < b$ とすると $\varphi(b) = a < \varphi(a)$ から矛盾。$a = b$ とすると $a = \varphi(b) = \varphi(a)$ となり矛盾です。よって、いずれの場合も矛盾が導けたため、順序同型 $\varphi : X\to X\langle x\rangle$ は存在しません。

(1) 順序になっていることは簡単です。空でない部分集合 $A\subset X\sqcup Y$ について $A\cap X\neq \varnothing$ ならば $\leq_{X}$ に関する $A\cap X$ の最小元が $\leq$ に関する最小元。$A\cap X = \varnothing$ ならば $A\cap Y\neq \varnothing$ であり、$\leq_{Y}$ に関する $A$ の最小元が $\leq$ に関する最小元になります。

(2) まず順序になっていることですが、反射律は明らか。対称律は $(x_{1}, y_{1})\leq (x_{2}, y_{2})$ かつ $(x_{2}, y_{2})\leq (x_{1}, y_{1})$ のとき、関係 $\leq$ の定義から $x_{1}\leq x_{2}$ かつ $x_{2}\leq x_{1}$ が直ちに分かるので $x_{1} = x_{2}$ であり、よって、$y_{1}\leq y_{2}$ かつ $y_{2}\leq y_{1}$ となり $y_{1} = y_{2}$ も分かるので $(x_{1}, y_{1}) = (x_{2}, y_{2})$ です。推移律を示します。$(x_{1}, y_{1})\leq (x_{2}, y_{2})$ かつ $(x_{2}, y_{2})\leq (x_{3}, y_{3})$ とします。$x_{1} < x_{2}$ か $x_{2} < x_{3}$ のうち一方でも成立する場合、$x_{1} < x_{3}$ なので $(x_{1}, y_{1})\leq (x_{3}, y_{3})$ です。$x_{1} = x_{2} = x_{3}$ の場合、$y_{1}\leq y_{2}$ かつ $y_{2}\leq y_{3}$ であり、よって、$x_{1} = x_{3}$ かつ $y_{1}\leq y_{3}$ となるので $(x_{1}, y_{1})\leq (x_{3}, y_{3})$ です。つまり、推移律も満たします。

$A\subset X\times Y$ を空でない部分集合とします。$X$ 成分への射影による $A$ の像 $\pr_{X}(A)$ の最小元 $a := \min \pr_{X}(A)$ を取り、$B := \{y\in Y\mid (a, y)\in Y\}$ の最小元 $b$ を取れば $(a, b)$ が $A$ の最小元となるので $(X\times Y, \leq)$ は整列集合です。

$P(x)$ が成立しない $x\in X$ 全体からなる集合を $A$ とします。もし $A\neq \varnothing$ とすると、$X$ が整列集合であることから $\min A$ が存在しますが、$A$ の定義より任意の $x\in X\langle\min A\rangle$ に対して $P(x)$ が成立します。仮定より $P(\min A)$ が成立しますが、これは $\min A\in A$ に矛盾です。よって、$A = \varnothing$ なので任意の $x\in X$ に対して $P(x)$ が成立します。

概略だけ。$x\in X$ であって順序同型 $X\langle x\rangle\cong Y\langle y\rangle$ を成立させる $y\in Y$ が存在するもの全体からなる集合を $A\subset X$ とします。このとき、命題1.4.5から各 $x\in A$ に対してそのような $y\in Y$ が一意に対応するので常に $X\langle x\rangle\cong Y\langle f(x)\rangle$ を満たす写像 $f : A\to Y$ が構成されます。同様に、$y\in Y$ であって順序同型 $X\langle x\rangle\cong Y\langle y\rangle$ を成立させる $x\in X$ が存在するもの全体からなる集合を $B\subset Y$ とし、写像 $g : B\to X$ を構成します。

$\Img f\subset B$, $\Img g\subset A$ は明らか。また、合成について $g\circ f = \Id_{A}$ と $f\circ g = \Id_{B}$ も明らか。$f, g$ が順序を保つことも容易であり、順序同型 $A\cong B$ が成立します。

任意の $a\in A$ と $x\in X$ に対して $x\leq a\Rightarrow x\in A$ であることから $A$ は切片 $X\langle x\rangle$ か全体集合 $X$ のどちらかになり、$B$ についても同様に切片 $Y\langle y\rangle$ か全体集合 $Y$ のどちらかです。$A = X\langle x\rangle$ かつ $B = Y\langle y\rangle$ のパターンは $x\in A = X\langle x\rangle$ を導き矛盾するので、主張の $3$ つの条件のうち少なくとも $1$ つが成立することが従います。

そして、主張の $3$ つの条件のうち複数が同時に成立しないことは命題1.4.5から従います。

$\mathcal{S}$ を $X$ の部分集合 $A$ とその上の整列順序 $\leq$ の対 $(A, \leq)$ 全体からなる集合とします。$(A, \leq_{A}), (B, \leq_{B})\in \mathcal{S}$ に対し、$b\in B$ であって $(A, \leq_{A}) = (B\langle b\rangle, \leq_{B})$ となるものが存在するときに $(A, \leq_{A})\prec (B, \leq_{B})$ であるとして $\mathcal{S}$ の順序 $\preceq$ を定めますつまり、$(A, \leq_{A})\prec (B, \leq_{B})$ または $(A, \leq_{A}) = (B, \leq_{B})$ により $(A, \leq_{A})\preceq (B, \leq_{B})$ を定義。これが実際に順序を与えることは容易。。

$(\mathcal{S}, \preceq)$ が帰納的順序集合であることを示すため、全順序部分集合 $\mathcal{A}\subset \mathcal{S}$ に対して $\tilde{A} = \underset{(A, \leq_{A})\in \mathcal{A}}{\bigcup}A$ に適切な順序 $\leq$ を与えることで $\mathcal{A}$ の上界となることを示します。まずは次のことを示します。

(i) $x\in A$, $y\in B$ となる $(A, \leq_{A}), (B, \leq_{B})\in \mathcal{A}$ を取ります。$\mathcal{A}$ が全順序なので、$(A, \leq_{A})\preceq (B, \leq_{B})$ または $(B, \leq_{B})\preceq (A, \leq_{A})$ ですが、前者なら $A\subset B$ より $x, y\in B$ であり、後者なら $B\subset A$ より $x, y\in A$ です。

(ii) $(A, \preceq_{A}), (B, \preceq_{B})\in \mathcal{A}$ が比較可能なので、一方は他方の部分順序集合であり明らか。

よって、$x, y\in \tilde{A}$ に対して $x, y\in A$ を適当に固定して $x\leq y\Leftrightarrow x\leq_{A} y$ と定めることで $\tilde{A}$ の関係 $\leq$ がwell-definedに定まります。$(\tilde{A}, \leq)$ が $\mathcal{A}$ の上界になることを以下の順で示します。

(step 1) 推移律のみ示します。他も容易です。$x, y, z\in \tilde{A}$ に対して $x\leq y$ かつ $y\leq z$ であったとします。$x, y, z\in A$ となる $(A, \leq_{A})\in \mathcal{A}$ を取れば $x\leq_{A} y$ かつ $y\leq_{A} z$ から $x\leq_{A} z$ であり、よって、$x\leq z$ です。

(step 2) 空でない部分集合 $C\subset \tilde{A}$ を取ります。$A\cap C\neq \varnothing$ を満たす $(A, \leq_{A})\in \mathcal{A}$ を取り、$(A, \leq_{A})$ における $A\cap C$ の最小元 $c$ を取ります。この $c$ が $(\tilde{A}, \leq)$ に関する $C$ の最小元であることを示します。$c'\in A\cap C$ に対して $c\leq c'$ であることは明らかなので $c'\in (\tilde{A}\setminus A)\cap C$ に対して $c\leq c'$ を示せばよいです。$c'\in B$ となる $(B, \leq_{B})\in \mathcal{A}$ を取ります。$\mathcal{A}$ が全順序であることと $c'\notin A$ より $(A, \leq_{A})\prec (B, \leq_{B})$ であり、よって、ある $b\in B$ が存在して $(A, \leq_{A}) = (B\langle b\rangle, \leq_{B})$ です。よって、$c < b = \min (B\setminus B\langle b\rangle) = \min (B\setminus A)\leq c'$ です。

(step 3) $(A, \leq_{A})\in \mathcal{A}$ とします。集合として $A = \tilde{A}$ の場合、$\tilde{A}$ の順序 $\leq$ の定め方より $\leq = \leq_{A}$ なので $(A, \leq_{A}) = (\tilde{A}, \leq)$ です。集合として $A\neq \tilde{A}$ のとき、$A\subset \tilde{A}$ から $b\in \tilde{A}\setminus A$ が存在します。$b\in B$ となる $(B, \leq_{B})\in \mathcal{A}$ を取れば $(A, \leq_{A})\prec (B, \leq_{B})$ であり、ある $\tilde{a}\in B$ が存在して $A = B\langle \tilde{a}\rangle$ です。この $\tilde{a}$ に対して $B\langle \tilde{a}\rangle = \tilde{A}\langle \tilde{a}\rangle$ であることを示せばよいです。

まず、$B\langle \tilde{a}\rangle \subset \tilde{A}\langle \tilde{a}\rangle$ は明らか。逆の包含関係を示すために $x\in \tilde{A}\langle \tilde{a}\rangle\setminus B\langle \tilde{a}\rangle$ が存在したとして矛盾を導きます。$x\in C$ を満たす $(C, \leq_{C})\in \mathcal{A}$ を取ります。$x\notin B$ から $(B, \leq_{B})\prec (C, \leq_{C})$ であり、ある $c\in C$ が存在して $B = C\langle c\rangle$ です。$\tilde{a}\in B$ より $\tilde{a} < c$ であり $x\notin B$ より $c\leq x$ となりますが、これは $x < \tilde{a}$ に矛盾です。よって、$\tilde{A}\langle\tilde{a}\rangle\subset B\langle\tilde{a}\rangle$ であり $B\langle \tilde{a}\rangle = \tilde{A}\langle \tilde{a}\rangle$ です。

以上により $\mathcal{S}$ が帰納的順序集合であることが分かりました。よって、Zornの補題 $($定理1.4.1$)$ より $\mathcal{S}$ の極大元 $(A, \leq_{A})$ が取れます。もし $A\neq X$ とすると、$x\in X\setminus A$ を取って $A\sqcup \{x\}$ に明らかな整列順序 $\leq$ を入れることで $(A, \leq_{A})\prec (A\sqcup \{x\}, \leq)$ $A = (A\sqcup \{x\})\langle x\rangle$ です。なので $(A, \leq_{A})$ の極大性に矛盾。よって、$A = X$ であり主張が示されました。

ここでは集合および順序数を $x, y, z, \dots$ で表すとします。以下の補題を確認しておきます。

(i) $x\cap y$ が帰属関係に関して整列集合をなすことは整列集合の部分集合が整列集合になることからよく、あとは推移性を示せばよいですが、これは任意の $z\in x\cap y$ に対して $x, y$ の推移性から $z\subset x$, $z\subset y$ が得られ $z\subset x\cap y$ となるのでよいです。

(ii) 仮定から $z := \min x\setminus y$ が取れます。任意の $w\in y$ に対して $w\in z$ が示され$z\notin y$ なので当然 $w\neq z$ であるし、もし $z\in w$ が成立したとすると $w\subset y$ から $z\in y$ となって矛盾します。、つまりは $y\subset z$ が得られます。ここで $z'\in z\setminus y$ が取れたとすると $z'\in x\setminus y$ と $z$ の定義より $z = z'$ または $z\in z'$ が成立しますが、いずれにせよ $z\in z$ を導き矛盾します。以上により $y = z\in x$ が従います。

本題の主張を示します。

(1) 順序数 $x$ とその元 $y\in x$ に対して $y$ が順序数であることを示します。まず、$x$ の推移性から $y\subset x$ です。$y$ が帰属関係に関して整列することは整列集合の部分集合が整列集合になることから従います。$y$ の推移性を示します。$z\in y$ を取り、任意の $w\in z$ に対して $w\in y$ を示せばよいです。帰属関係に関する全順序性より $w = y$, $w\in y$, $y\in w$ のいずれかが成立しますが、最初と最後のケースはそれぞれ\[y = w\in z\in y,\]\[y\in w\in z\in y\]を導き、いずれにせよ推移性より $y\in y$ が得られ、非反射性に矛盾します。よって、$w\in y$ です。以上により $y$ は順序数です。

(2) 非自明なのは全順序性のみであり、それを示します。順序数 $x, y$ を取ります。(i)より $x\cap y$ は順序数であり、これがもし $x, y$ のいずれとも異なるとすると(ii)より $x\cap y\in x$ かつ $x\cap y\in y$ となり、これは $x\cap y\in x\cap y$ を導き矛盾です。よって、$x\cap y$ は $x, y$ のいずれかに等しく、これからただちに全順序性が分かります。

(3) 任意の順序数 $x, y$ に対して $y\subset x \Leftrightarrow x = y\vee y\in x$ であることに注意すれば(2)より容易に分かります。

(4) 空でない順序数の集まり $U\subset \Ord$ を取ります。適当な元 $x\in U$ を取れば $\min ((x\cup \{x\})\cap U)$ が $U$ の最小元になります。

(5) まず、順序数 $y\in x$ に対して\[y = \{z\in x\mid z\in y\} = x\langle y\rangle\]であるので、比較定理 $($定理1.4.9$)$ より相異なる順序数は互いに順序同型にはなりません。つまり、主張の一意性が得られました。

あとは与えられた整列集合 $X$ に対して順序同型な順序数が存在することを示せばよいです。$X$ を切片として持つ整列集合 $A$ を取り、各 $a\in A$ に対して条件 $P(a)$ を「 $A\langle a\rangle$ に順序同型な順序数が存在する」と定め、これが全ての $a\in A$ に対して成立することを超限帰納法により証明します。

$a_{0}\in A$ を取り、全ての $a < a_{0}$ に対して $P(a)$ が成立していたとして $P(a_{0})$ を示します。各 $a < a_{0}$ に対して $A\langle a\rangle$ に順序同型な順序数を対応させる写像 $f : A\langle a_{0}\rangle\to \Ord$ を取ります。$f(A\langle a_{0}\rangle)$ が順序数であることを示します。$f(A\langle a_{0}\rangle)$ が帰属関係に関して整列集合をなすことは明らかなので、あとは推移性を示せばよいです。$x\in f(A\langle a_{0}\rangle)$ とします。ある $a < a_{0}$ が存在して順序同型写像 $g_{x} : A\langle a\rangle\to x$ が取れます。任意の $y\in x$ に対して制限 $g_{x} : A\langle g_{x}^{-1}(y)\rangle\to x\langle y\rangle = y$ は順序同型であり $y\in f(A\langle a_{0}\rangle)$ が得られます。以上により $x\subset f(A\langle a_{0}\rangle)$ であり、推移性が確かめられました。制限 $f : A\langle a_{0}\rangle\to f(A\langle a_{0}\rangle)$ は明らかに全単射であり、順序数との間の順序同型を定め、$P(a_{0})$ が成立します。

(6) 省略。

(7) 省略。

代表元を取って具体的に順序同型を与えるだけです。

両方向の不等号がそれぞれ示せます。

代表元を取って具体的に順序同型を与えるだけです。

省略。(そのうち書きます。)

(1) 恒等写像 $\Id_{X} : X\to X$ は単射なのでそう。

(2) $X$ の部分集合による減少列 $X_{0}\supset X_{1}\supset X_{2}\supset \cdots$ を $X_{0} := X$, $X_{k + 1} := (g\circ f)(X_{k})$ により定め、同様に $Y$ の部分集合による減少列 $Y_{0}\supset Y_{1}\supset Y_{2}\supset \cdots$ を $Y_{0} := Y$, $Y_{k + 1} := (f\circ g)(Y_{k})$ により定めます。また、$X_{\infty} := \bigcap_{k\in\N}X_{k}$, $Y_{\infty} := \bigcap_{k\in\N}Y_{k}$ とおきます。このとき、

が成立しています。次のことを示せばよいです。

つまり、これらが $X, Y$ の直和分解の各成分の間の全単射となっているので、明らかな方法で全体の全単射 $h : X\to Y$ が構成されます。

(i) 次のことを示します。

これが示されれば、$X_{k}\setminus X_{k + 1} = X_{k}\setminus g(Y_{k})\sqcup g(Y_{k})\setminus X_{k + 1}$ と $Y_{k}\setminus Y_{k + 1} = Y_{k}\setminus f(X_{k})\sqcup f(X_{k})\setminus Y_{k + 1}$ から $h_{k} : X_{k}\setminus X_{k + 1}\to Y_{k}\setminus Y_{k + 1}$ を\[h_{k} : x\mapsto \left\{\begin{array}{ll}h'_{k}(x) & (x\in X_{k}\setminus g(Y_{k})) \\(h''_{k})^{-1}(x)& (x\in g(Y_{k})\setminus X_{k + 1})\end{array}\right.\]と定めることで全単射 $h_{k}$ が構成されます。

(a)$f$ が単射なので $f(X_{k}\setminus g(Y_{k})) = f(X_{k})\setminus Y_{k + 1}$ を示せばよいです。$y\in f(X_{k}\setminus g(Y_{k}))$ とします。$f(x) = y$ を満たす $x\in X_{k}\setminus g(Y_{k})$ を取ります。$f(x)\in f(X_{k})$ です。$f(x)\notin Y_{k + 1}$ を背理法より示します。$f(x)\in Y_{k + 1}$ とします。$Y_{k + 1} = f(g(Y_{k}))$ よりある $x'\in g(Y_{k})$ であって $f(x') = f(x)$ となるものが取れます。$f$ が単射なので $x' = x\notin g(Y_{k})$ であり矛盾です。よって、$f(x)\notin Y_{k + 1}$ が分かり、$y = f(x)\in f(X_{k})\setminus Y_{k + 1}$ です。従って、$f(X_{k}\setminus g(Y_{k}))\subset f(X_{k})\setminus Y_{k + 1}$ です。

$y\in f(X_{k})\setminus Y_{k + 1}$ とします。$y\in f(X_{k})$ から $f(x) = y$ となる $x\in X_{k}$ を取ります。$x\in g(Y_{k})$ であったとすると、$y = f(x)\in f(g(Y_{k})) = Y_{k + 1}$ となって矛盾するので $x\notin g(Y_{k})$ です。よって、$x\in X_{k}\setminus g(Y_{k})$ であり、$y = f(x)\in f(X_{k}\setminus g(Y_{k}))$ です。従って、$f(X_{k})\setminus Y_{k + 1}\subset f(X_{k}\setminus g(Y_{k}))$ です。

両方の向きの包含関係が示されたので $f(X_{k}\setminus g(Y_{k})) = f(X_{k})\setminus Y_{k + 1}$ です。

(b) (a)と同じです。

(ii) $h_{\infty}$ の単射性は明らか。全射性を示します。$y\in Y_{\infty}$ とします。任意の $k\in \N$ に対し、$y\in Y_{k + 1} = g(f(Y_{k}))\subset g(X_{k})$ により $x_{k}\in X_{k}$ であって $f(x_{k}) = y$ となるものが取れます。任意の $k\in \N$ に対して $f$ の単射性と $f(x_{0}) = y = f(x_{k})$ から $x_{0} = x_{k}\in X_{k}$ であり、$x_{0}\in X_{\infty}$ です。$x_{0}\in X_{\infty}$ かつ $h_{\infty}(x_{0}) = f(x_{0}) = y$ です。よって、$h_{\infty}$ の全射性が示されました。

(3) 単射どうしの合成は単射なのでそうです。

(4) 整列定理 $($定理1.4.10$)$ と比較定理 $($定理1.4.9$)$ から明らかです。

集合 $X, Y$ を $\#X = \mathfrak{n}$, $\#Y = \mathfrak{m}$ となるように取っておきます。

(1) 明らかに写像 $X\to 2^{X} : x\mapsto \{x\}$ は単射であるので $\mathfrak{n}\leq 2^{\mathfrak{n}}$ です。等号が成立していたとして矛盾を導きます。全単射 $f : X\to 2^{X}$ を取ります。部分集合 $A := \{x\in X\mid x\notin f(x)\}$ を考えるとき、$f^{-1}(A)\in A$ とすると $A$ の定義から $f^{-1}(A)\notin A$ となり矛盾。$f^{-1}(A)\notin A$ としても $A$ の定義から $f^{-1}(A)\in A$ となり矛盾します。よって、いずれにせよ矛盾が導かれることから $\mathfrak{n}\neq 2^{\mathfrak{n}}$ が従いますこのような議論は対角線論法と呼ばれます。。

(2) 集合 $\Lambda$ であって $Y\sim \Lambda\times \N$ となるものを構成します。これができれば、$\N\sim\N\sqcup \N$ から\[Y\sim \Lambda\times \N\sim \Lambda\times (\N\sqcup \N)\sim (\Lambda\times \N)\sqcup (\Lambda\times \N)\sim Y\sqcup Y\]なので $\mathfrak{m}\leq \mathfrak{n} + \mathfrak{m}\leq \mathfrak{m} + \mathfrak{m} = \mathfrak{m}$ となり、$\mathfrak{n} + \mathfrak{m} = \mathfrak{m}$ です。

まず、$Z = 2^{Y}$ に整列順序を与えて整列集合とみなします$Z$ は $Y$ の濃度より大きい濃度を持てばなんでもいいです。。$z\in Z$ と単射 $f : Z\langle z\rangle\times \N\to Y$ の対 $(z, f)$ 全体からなる集合 $\mathcal{S}$ を考えます。$\mathcal{S}$ に対して\[(z, f)\leq (w, g) :\Leftrightarrow z\leq w\wedge g|_{Z\langle z\rangle\times \N} = f\]による順序を定めれば帰納的順序集合になるため$\mathcal{S}$ の全順序部分集合 $\mathcal{A}$ が与えられたとき、そこに属する写像たちを全て明らかな方法で「重ね合わせる」ことで上界が作れます。この重ね合わせて作った写像の定義域が $Z\langle z\rangle\times \N$ の形であること $($$Z\times \N$ でないこと$)$ も要確認ですが、これは $\#Y < \#(Z\times \N)$ から分かります。、Zornの補題 $($定理1.4.1$)$ よりその極大元 $(z_{0}, f_{0})$ が取れますが、その極大性より $N := Y\setminus \Img f_{0}$ は有限集合であり $Y\sim (Z\langle z_{0}\rangle\times \N)\sqcup N$ が得られます$\#Y < \#(Z\times \N) = \#((Z\setminus \{z_{0}\})\times \N)$ より $z_{0}$ は最大元ではないので $Z\langle z_{1}\rangle = Z\langle z_{0}\rangle\sqcup \{z_{0}\}$ となる $z_{1}\in Z$ が取れます。もし $N := Y\setminus \Img f_{0}$ が無限集合とすると $f_{0}$ は単射 $f_{1} : Z\langle z_{1}\rangle\to Y$ に拡張でき、これについて $(z_{0}, f_{0}) < (z_{1}, f_{1})$ となり極大性に矛盾です。。$Y$ が無限集合であることから $\min Z < z_{0}$ であり、$\{\min Z\}\times \N\sqcup N\sim \{\min Z\}\times \N$ から有限集合 $N$ を $\Img f_{0}$ に組み込めば $Y\sim Z\langle z_{0}\rangle\times \N$ が得られます。

(3) まず、$\N\sim \N\times \N$ が全単射\[\varphi : \N\times \N\to \N : (n, m)\mapsto \tfrac{1}{2}(n + m)(n + m + 1) + m\]により確かめられ、よって、空でない有限集合 $M$ に対して $\N^{M}\sim \N\sim \N^{M}\times \N^{M}$ が分かります。また、無限集合 $M$ に対しては(2)より $\N^{M}\sim \N^{M\sqcup M}\sim \N^{M}\times \N^{M}$ です。つまり、任意の空でない集合 $M$ に対して $\N^{M}\sim \N^{M}\times \N^{M}$ となります。

集合 $M$ であって $Y\sim \N^{M}$ となるものを構成します。これができれば、上記のことから\[Y\sim \N^{M}\sim \N^{M}\times \N^{M}\sim Y\times Y\]なので $\mathfrak{m}\leq \mathfrak{n}\mathfrak{m}\leq \mathfrak{m}\mathfrak{m} = \mathfrak{m}$ となり、$\mathfrak{n}\mathfrak{m} = \mathfrak{m}$ です。

まず、$Y$ に整列順序を与えて整列集合とみなし、それを $Z$ と書くことにします。そして、各切片 $Z\langle z\rangle$ に対して単射 $\N^{Z\langle z\rangle}\to \N^{Z}$ を\[(a_{z})_{z\in Z\langle z\rangle}\mapsto (a_{z})_{z\in Z\langle z\rangle}\sqcup (0)_{z\in Z\setminus Z\langle z\rangle}\]と取ることにより $\N^{Z\langle z\rangle}\subset \N^{Z}$ とみなしておきます。$z\in Z$ と単射 $f : \N^{Z\langle z\rangle}\to Y$ の対 $(z, f)$ 全体からなる集合 $\mathcal{S}$ を考えます。$\mathcal{S}$ に対して\[(z, f)\leq (w, g) :\Leftrightarrow z\leq w\wedge g|_{\N^{Z\langle z\rangle}} = f\]による順序を定めれば帰納的順序集合になるため、その極大元 $(z_{0}, f_{0})$ が取れますが、その極大性より $\#Y\setminus \Img f_{0} < \#\Img f_{0} = \#\N^{Z\langle z_{0}\rangle}$ であり\[Y = \Img f_{0}\sqcup (Y\setminus \Img f_{0})\sim \Img f_{0}\sim \N^{Z\langle z_{0}\rangle} \]が得られます。細かい部分はだいたい(2)と一緒です。

(4) (3)から $2^{\mathfrak{m}} = 2^{\mathfrak{m}\mathfrak{m}} = (2^{\mathfrak{m}})^{\mathfrak{m}}$ であり、$2\leq \mathfrak{n}\leq \mathfrak{m}\leq 2^{\mathfrak{m}}$ と合わせて $2^{\mathfrak{m}}\leq \mathfrak{n}^{\mathfrak{m}}\leq (2^{\mathfrak{m}})^{\mathfrak{m}} = 2^{\mathfrak{m}}$ です。よって、$\mathfrak{n}^{\mathfrak{m}} = 2^{\mathfrak{m}}$ が成立します。

(5) (3)の繰り返し適用により示されます。

$\#\N = \#\Z$ は写像 $f : \N\to \Z$ を\[f(n) = \left\{\begin{array}{ll}n/2 & (n : \text{even}) \\-(n + 1)/2 & (n : \text{odd})\end{array}\right.\]により定めれば全単射なのよいです。

$\#\N = \#\Q$ を示します。正整数 $n\in \N_{+}$ に対して部分集合 $A_{n}\subset \Q$ を\[A_{n} = \{p/q\mid p, q\in\Z, \ 1\leq q\leq n, \ |p|\leq nq\}\]により定めますつまり、有理数 $r$ であって $|r|\leq n$ かつ既約分数で表したときの分母 $q$ が $n$ 以下であるもの全体からなる集合。。$A_{n}$ は有限集合かつ部分集合の列として単調増加であり、$\underset{n\in\N_{+}}{\bigcup}A_{n} = \Q$ です。よって、添字 $n$ の小さい $A_{n}$ に属する有理数から順番に $\N$ の元を対応させていけば全単射 $\N\to \Q$ が構成されます。(いろいろ準備したので、写像 $\Z\times \Np\to \Q : (p, q)\mapsto p/q$ の全射性から $\#\Q\leq \#(\Z\times \Np) = \#\N$ というのが単純ですが。)