備忘録：整列可能定理

$A = \{ x \in X \mid f(x) < x \}$ と定義する．$A$ が空でないと仮定すると，$X$ は整列集合であるから $a = \min A$ が存在する．$f(a) < a$ が成り立つが，$f$ は順序を保つ単射であるから $f(f(a)) < f(a)$ となる．したがって $f(a) \in A$ となるがこれは $a$ の最小性に矛盾する．
よって仮定が誤りであり $A$ は空であることが判った．

1. $f : X \xrightarrow\simeq X \langle a \rangle$ とすると $f(a) \in X \langle a \rangle$ より $f(a) < a$ となるが，これは補題1に矛盾する．
2. $a < b$ としても一般性を失わない．$X \langle a \rangle = (X \langle a \rangle)\langle b \rangle$ となることから，1.の $X$ を $X \langle b \rangle$ に置換することで証明を帰着できる．
3. 先に $X \langle a \rangle \simeq Y \langle f(a) \rangle$ を証明しよう．これは $f(X \langle a \rangle) = Y \langle f(a) \rangle$ となることから簡単に従う（$f$ を $X \langle a \rangle$ に制限した写像が順序同型写像となる）．$f,g : X \xrightarrow\simeq Y$ とする．このとき，先ほど得た結果から $Y \langle f(a) \rangle \simeq Y \langle g(a) \rangle$ を得るが，2.より $f(a) = g(a)$ が導かれる．$a \in X$ は任意であったから $f = g$ である．

集合 $X',Y'$ を次のように定義する．
\begin{align} X' &= \{ a \in X \mid \exists b \in Y , \ X \langle a \rangle \simeq Y \langle b \rangle \} \\ Y' &= \{ b \in Y \mid \exists a \in X , \ X \langle a \rangle \simeq Y \langle b \rangle \} \end{align}
まず，$X' \simeq Y'$ を証明する．
$a \in X'$ とすると $X'$ の定義より $X \langle a \rangle \simeq Y \langle b \rangle$ となる $b \in Y$ が存在し，特に $b \in Y'$ である．定理2.2よりこのような $b$ は一意に定まるから，写像 $\varphi : X' \rightarrow Y'$ が定まる．$X',Y'$ を逆にして議論を行えば逆写像 $\varphi^{-1}$ が簡単に得られるから， $\varphi$ は全単射．また，$\varphi,\varphi^{-1}$ は明らかに順序を保つから $\varphi$ は順序同型写像．
$X'$ が空である場合は $Y'$ もまた空であるから，いずれにせよ $X' \simeq Y'$ が成り立つ．
次に，$X'$ は $X$ の切片もしくは $X$ 自身であることを証明する．
$X' = \emptyset \ \text{または} \ X$ のときはよい．そうでないときは $a_1 = \min X \setminus X'$ と定義することで $X \langle a_1 \rangle = X'$ となることを示す．その前に準備をしておく．
$a \in X'$ とすると，ある $b \in Y$ が存在して $f : X \langle a \rangle \xrightarrow\simeq Y \langle b \rangle$ となる．定理2.3より任意の $a' \in X \langle a \rangle$ に対して $X \langle a' \rangle \simeq Y \langle f(a') \rangle$ が成立するから $X \langle a \rangle \subset X'$ である．すなわち，「$a \in X' \Rightarrow X \langle a \rangle \subset X'$」．
話を戻そう．
$a_1$ の定義より $a_1$ より小さな元はみな $X'$ に属するから $X \langle a_1 \rangle \subset X'$．$a_2 \in X' \setminus X \langle a_1 \rangle$ が存在するとすれば，$a_2 \ge a_1$ かつ $a_1 \not\in X'$ より $a_2 > a_1$ となる．$a_2 \in X'$ と「準備」も踏まえると $a_1 \in X \langle a_2 \rangle \subset X'$ が導かれ，$a_1 \in X'$ となって矛盾してしまうから，$a_2$ の存在を仮定したのがそもそも誤りだったのだとわかる．よって $X' \setminus X \langle a_1 \rangle = \emptyset$ であり，　$X \langle a_1 \rangle = X'$．
よって $X'$ は $X$ の切片または $X$ 自身である．$Y'$ も同様．
最後に定理を示す．ここまでの議論から $X',\ Y'$ がともに切片となる場合はありえないことを言えばいい．$X' = X \langle a \rangle , \ Y' = Y \langle b \rangle$ とすると，$X \langle a \rangle \simeq Y \langle b \rangle$．$X'$ の定義より $a \in X'$ となるがこれは $a \in X \langle a \rangle$ を意味し矛盾する．よって，$X',\ Y'$ はともに切片にはならず，1,2,3のいずれかが成り立つ．定理2.1,2.2よりこれらが両立しないのは明らか．

集合 $X$ に対し，$X$ の部分集合 $A$ とその上の整列順序の組 $(A, \le_{\alpha})$ 全体の集合を $\mathcal{X}$ とする．
$\mathcal{X}$ の元 $(A, \le_{\alpha}), \ (B, \le_{\beta})$ に対し
$$(A, \le_{\alpha}) \le (B, \le_{\beta}) \xLeftrightarrow{\mathrm{def}} (A, \le_{\alpha}) \ \text{が} \ (B, \le_{\beta}) \ \text{に一致する，または} \ (B, \le_{\beta}) \ \text{の切片に一致する．}$$
と $\le$ を定義するとき，$(\mathcal{X}, \le)$ は帰納的半順序集合となる．
$\le$ が半順序となることは簡単なため省略する．
$\mathcal{Y} \subset \mathcal{X}$ を鎖として，$Y_\infty = \bigcup \mathcal{Y}$　に以下のような順序 $\le_{\infty}$ を定めよう．
「$a \le_{\infty} b \xLeftrightarrow{\mathrm{def}} a \in (A, \le_{\alpha}) , \ b \in (B,\le_{\beta}), \ (A, \le_{\alpha}) \le (B, \le_{\beta}) \ \text{であり} a \le_{\beta} b$ 」
$\le_{\infty}$ が全順序なのは易しい．$M \subset Y_{\infty}$ を任意にとり， $\min M$ が存在することを証明しよう．$M \cap Y \neq \emptyset$ となる $Y \in \mathcal{Y}$ を適当に一つとる．すると $M \cap Y$ は $Y$ の空でない部分集合だから最小元 $\min M \cap Y$ が存在する．実はこれが $\min M$ となる．仮に $M$ に $\min M \cap Y$ より小さな元 $m$ が存在したとする．このとき，$m$ を元にもつ $Y_m \in \mathcal{Y}$ が存在するはずだが，$Y_m$ と $Y$ は $\le$ で比較不能になってしまう．なぜなら，$m \notin Y$ より $Y_m \le Y$ とはなり得ないし，$Y_m$ のいかなる切片も $m$ の存在のせいで決して $Y$ には一致しないため $Y \le Y_m$ ともならないからだ．これは $\mathcal{Y}$ が鎖だという前提に反するため $\min M = \min M \cap Y$ となるのだ．以上より $Y_{\infty}$ の空でない部分集合は必ず最小元を持つため，$(Y_{\infty}, \le_{\infty})$ は整列集合．
これが $\mathcal{Y}$ の上界となることから $(\mathcal{X},\le)$ が帰納的半順序集合であることがいえるのである．
ツォルンの補題により， $(\mathcal{X},\le)$ には極大元 $(X_0,\le_{X_0})$ が存在する．$X \neq X_0$ と仮定すると $a \in X \setminus X_0$ を適当に一つとって $X_0$ に最大元として追加することができてしまい，$X_0$ の極大性に反するから $X = X_0$．
従って $X$ は $\le_{X_0}$ によって整列可能であることが示された．