整列可能定理(3) - 非専門的シンギュラリティー研究所

『公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』の整列可能定理の証明を書き直していきます。そのための補題を追加します。

補題 1 $X$ を順序数からなる集合とすると、 $\gamma = \min \{ \alpha \in \mathbf{Ord} \mid X \subseteq \alpha \}$ が存在します。
[証明]

$\alpha \in X$ ならば $\alpha \subseteq \sup X$
よって $\alpha \in X$ ならば $\alpha = \sup X$ または $\alpha \in \sup X$ となります。
$X \subseteq \sup X \cup \{ \sup X \}$ となります。
$\gamma = \begin{cases} \sup X & (\sup X \notin X のとき) \\ \sup X + 1 & (\sup X \in X のとき) \\ \end{cases}$ とおきます。
のとき
- $X \subseteq \sup X = \gamma$ となります。
- をとなる順序数とすると
  - 任意の $\alpha \in X$ に対して $\alpha \in \beta$
  - $\gamma$ は $X$ の上限なので $\gamma \le \beta$
のとき
- $X \subseteq \sup X \cup \{ \sup X \} = \gamma$ となります。
- をとなる順序数とすると
  - $\sup X \in X \subseteq \beta$
  - $\gamma = \sup X \cup \{\sup X\} \subseteq \beta$ となります。
よって $\gamma = \min \{ \alpha \in \mathbf{Ord} \mid X \subseteq \alpha \}$ となります。

整列可能定理の証明(1)

定理 2.11 (整列可能定理) どんな集合 $A$ に対しても、 $A$ 上の二項関係 $R$ で、 $(A, R)$ が整列集合となるものが存在する。

以下の主張を証明すれば良いので、これを証明します。

集合 $A \ne \varnothing$ に対して順序数 $\gamma$ と全単射 $f: \gamma \to A$ が存在する。

[証明]

$a_0 \in A$ をとります。
選択公理より選択関数 $c: \mathfrak{P}(A) \setminus \{\varnothing\} \to A$ があります。
を定義します。
- 各順序数に対して集合を
  
  と定義できます。
  - ここで $\restriction$ は関数の制限、 $\mathrm{ran}$ は関数の値域
の像をとします。
- $B = \{ G(\alpha) \mid \alpha \in \mathbf{Ord} \}$
- $B$ は集合です。
を定義します。
- $B$ の各元 $b$ に対して順序数 $g(b)$ を
  $g(b) = \min \{ \alpha \mid G(\alpha) = b \}$
  と定義します。
の像をとします。
- $X = \{ g(b) \mid b \in B \}$
- $X$ は順序数からなる集合となります。
補題 1 より $\gamma = \min \{ \alpha \in \mathbf{Ord} \mid X \subseteq \alpha \}$ が存在します。
とするとが全単射となります。これは後で証明します。

整列可能定理の証明(2)

$\gamma = \min \{ \alpha \in \mathbf{Ord} \mid X \subseteq \alpha \}$ が存在するので、以下の議論は集合 $\gamma + 1$ についての議論となります。

補題を追加します。

補題 2 $\gamma = \min \{ \delta \in \mathbf{Ord} \mid B \subseteq \mathrm{ran}(G \restriction \delta) \}$
[証明]

$\begin{eqnarray*} X \subseteq \delta &\iff& \forall \alpha \in X (\alpha \in \delta) \\ &\iff& \forall \alpha \in \mathbf{Ord} (g(G(\alpha)) \in \delta) \\ \end{eqnarray*}$
$\begin{eqnarray*} g(G(\alpha)) \in \delta &\iff& \min \{ \beta \in \mathbf{Ord} \mid G(\alpha) = G(\beta) \} \in \delta \\ &\iff& \exists \beta \in \delta (G(\alpha) = G(\beta)) \\ \end{eqnarray*}$
$\begin{eqnarray*} B \subseteq \mathrm{ran}(G \restriction \delta) &\iff& \forall a \in B (a \in \mathrm{ran}(G \restriction \delta)) \\ &\iff& \forall \alpha \in \mathbf{Ord} (G(\alpha) \in \mathrm{ran}(G \restriction \delta)) \\ \end{eqnarray*}$
$G(\alpha) \in \mathrm{ran}(G \restriction \delta) \iff \exists \beta \in \delta (G(\alpha) = G(\beta))$
$X \subseteq \delta \iff B \subseteq \mathrm{ran}(G \restriction \delta)$
よって
$\min \{ \delta \in \mathbf{Ord} \mid X \subseteq \delta \} = \min \{ \delta \in \mathbf{Ord} \mid B \subseteq \mathrm{ran}(G \restriction \delta) \}$

補題 3 $\eta = \min \{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \} \le \gamma$ が存在します。
[証明]

$\begin{eqnarray*} \gamma &=& \min \{ \delta \in \mathbf{Ord} \mid X \subseteq \delta \} \\ &=& \min \{ \delta \in \mathbf{Ord} \mid \forall \alpha \in \mathbf{Ord} \exists \beta \in \delta (G(\alpha) = G(\beta)) \} \\ \end{eqnarray*}$
$\begin{eqnarray*} \eta &=& \min \{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \} \\ &=& \min \{ \delta \in \mathbf{Ord} \mid \exists \beta \in \delta (G(\delta) = G(\beta)) \} \\ \end{eqnarray*}$
$\{ \delta \in \mathbf{Ord} \mid X \subseteq \delta \} \subseteq \{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \}$
よって $\eta$ は存在します、
また $\eta \le \gamma$ です。

補題 4 $\eta = \min \{ \delta \in \mathbf{Ord} \mid A = \mathrm{ran}(G \restriction \delta) \}$
[証明]

$\begin{eqnarray*} A = \mathrm{ran}(G \restriction \delta) &\iff& G(\delta) \in G \restriction \delta \\ &\iff& g(G(\delta)) < \delta \\ \end{eqnarray*}$
よって $\eta = \min \{ \delta \in \mathbf{Ord} \mid A = \mathrm{ran}(G \restriction \delta) \}$

補題 5 $\delta$ を $G(\delta) = G(\beta)$ を満たす $\beta \in \delta$ が存在する順序数とします。すると任意の順序数 $\alpha \ge \delta$ に対して $G(\alpha) = G(\beta)$ を満たす $\beta \in \alpha$ が存在します。
[証明]

とすると
- $G$ の定義より $G(\delta) \in A \setminus \mathrm{ran}(G \restriction \delta)$ です。
- $\beta < \delta$ ならば $G(\beta) \in \mathrm{ran}(G \restriction \delta)$ なので $G(\delta) \ne G(\beta)$
  よって $G(\delta) = G(\beta)$ となる $\beta \in \delta$ は存在しません。
- これは $\delta$ の仮定に反します。
よって $A = \mathrm{ran}(G \restriction \delta)$ です。
とすると
- $\mathrm{ran}(G \restriction \delta) \subseteq \mathrm{ran}(G \restriction \alpha)$ なので $A = \mathrm{ran}(G \restriction \alpha)$
- $G$ の定義より $G(\alpha) \in \mathrm{ran}(G \restriction \alpha)$ です。
- よって $G(\alpha) = G(\beta)$ となる $\beta \in \alpha$ が存在します。
よって $\alpha \ge \delta$ ならば $G(\alpha) = G(\beta)$ となる $\beta \in \alpha$ が存在します。

補題 6 任意の順序数 $\alpha$ に対して $G(\alpha) = G(\beta)$ を満たす $\beta \in \eta$ が存在します。
[証明]

$\alpha \ge \eta$ ならば補題 5 から成り立ちます。
ならば
- $\eta$ の最小性から任意の $\beta \in \alpha$ に対して $G(\alpha) \ne G(\beta)$
- $A \setminus \mathrm{ran}(G \restriction \alpha) = \varnothing$ のときは $G(\alpha) \in \mathrm{ran}(G \restriction \alpha)$ なのでこのようなことは起こりません。
- よって $A \setminus \mathrm{ran}(G \restriction \alpha) \ne \varnothing$ となります。
- よって $g(G(\alpha)) = \alpha$ となります。
- よって $G(\alpha) = G(\beta)$ を満たす $\beta \in \eta$ が存在します。
よって任意の順序数 $\alpha$ に対して $G(\alpha) = G(\beta)$ を満たす $\beta \in \eta$ が存在します。

補題 7 $\gamma = \eta$
[証明]

補題 6 から
$\{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \} \subseteq \{ \delta \in \mathbf{Ord} \mid X \subseteq \delta \}$
よって
$\min \{ \delta \in \mathbf{Ord} \mid X \subseteq \delta \} \le \min \{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \}$
よって $\gamma \le \eta$
補題 3 より $\gamma = \eta$ となります。

整列可能定理の証明(3)

$f = G \restriction \gamma$ は全単射となることを証明します。
[証明]

は全射であることを示します。
- 補題 7 と補題 4 から $\gamma = \min \{ \delta \in \mathbf{Ord} \mid A = \mathrm{ran}(G \restriction \delta) \}$
- よって $A = \mathrm{ran}(f)$ となって $f$ は全射です。
は単射であることを示します。
- 補題 7 から $\gamma = \min \{ \delta \in \mathbf{Ord} \mid g(G(\delta)) < \delta \}$
- よって $\alpha \in \gamma$ ならば $g(G(\alpha)) = \alpha$
- $f(\alpha) = f(\beta)$ ならば $g(f(\alpha)) = g(f(\beta))$
- よって $\alpha = \beta$ となります。
- よって $f$ は単射です。
よって $f$ は全単射となります。