証明路開発支援システム(30) - 非専門的シンギュラリティー研究所

整列可能定理(9)

まず『公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』の必要な部分を引用しておきます。

定義 1.5 (3) 全順序集合 $(A, < )$ が以下を満たすとき、 $(A, < )$ は整列集合であるという：
$A$ のどんな部分集合 $X$ に対しても、 $X$ が空でなければ、( $<$ についての) $X$ の最小元が存在する。
つまり、 $a_0 \in X$ であって、どんな $X$ の元 $b$ に対しても、 $b$ が $a_0$ と異なれば $a_0 < b$ となるものが存在する。
整列集合 $(A, < )$ と $A$ の元 $a$ に対して
$a \downarrow = \{ b \in A \mid b < a \}$
定義 1.8 (整列集合上の再帰的定義) $(A, < )$ を整列集合とする。
$A$ の各元 $a$ と各集合 $X$ に対して、集合 $F(a, X)$ が与えられているとする。
このとき、以下の二つを満たす関数 $g$ がただ一つ存在する：
(1) $g$ の定義域は $A$ である。
(2) すべての $a \in A$ に対して $g(a) = F(a, g \restriction a \downarrow)$ が成り立つ。
定義 1.9 (順序数) 集合 $\alpha$ が以下の二つの性質を満たすとき、 $\alpha$ は順序数であるという：

$\alpha$ は推移的である。つまり、 $x \in \alpha$ と $y \in x$ を任意にとると、 $y \in \alpha$ である。

$(\alpha, \in)$ は整列集合である。

補題 2.1 (1) $\alpha$ を順序数として $x \in \alpha$ とすると、 $x$ も順序数である。
(2) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \in \beta$ と $\alpha \subsetneq \beta$ は同値になる。
(3) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \subseteq \beta$ あるいは $\beta \subseteq \alpha$ が成り立つ。
(3) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \in \beta$ 、 $\alpha = \beta$ 、 $\beta \in \alpha$ のいずれか一つのみが成り立つ。
(4) $X$ を順序数からなる集合とすると、 $\displaystyle \sup X = \bigcup_{\alpha \in X} \alpha$ も順序数となる。
(5) $X$ を順序数からなる空でない集合とすると、 $\displaystyle \inf X = \bigcap_{\alpha \in X} \alpha$ も順序数となる。
定理 2.7 $(A, < )$ を整列集合とする。このとき、順序数 $\alpha$ と順序同型 $g: (A, < ) \to (\alpha, \in)$ が存在する。さらに、このような $\alpha, \ g$ は整列集合 $(A, < )$ に対してただ一つしかない。

「整列可能定理(2)」に書いた証明を書き直します。

$\gamma$ の定義は『公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』の通りにするとうまくいかないようです。 $\gamma = \sup X$ とすると $B = \mathrm{ran}(G \restriction \gamma)$ が成り立つとなっていますが以下のようになります。

「フォン・ノイマンの順序数」で考えます。
- $0 = \varnothing$
- $1 = \{0\} = \{\varnothing\}$
- $2 = \{0,1\} = \{\varnothing,\{\varnothing\}\}$
$A = \{0, 1\} = 2$ の場合を考えます。
$B = \{0, 1\} = 2$
$X = \{0, 1\} = 2$
$\gamma = \sup X = \bigcup_{\alpha \in \{0, 1\}} \alpha = 0 \cup 1 = 0 \cup (0 \cup \{0\}) = 0 \cup \{0\} = \{0\} = 1$
$\mathrm{ran}(G \restriction \gamma) = \{0\} = 1$
よって $B = \mathrm{ran}(G \restriction \gamma)$ は成り立ちません。

よって $\gamma$ の定義を変更する必要があります。前回書いたものは間違っていたのでやり直します。

集合 $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$ は順序数からなる集合となります。
とおきます。
- ここで $\displaystyle \sup X = \bigcup_{\alpha \in X} \alpha$
- $\alpha \in X$ ならば $\alpha \subseteq \sup X$
- $\alpha \in X$ ならば $\alpha \le \sup X$
- よって $\alpha \in X$ ならば $\alpha = \sup X$ または $\alpha \in \sup X$ となります。
- となるが存在しないとき
  - $\alpha \in X$ ならば $\alpha \in \sup X$ となります。
  - $X \subseteq \sup X$ となります。
- となるが存在するとき
  - $X \subseteq \sup X \cup \{ \sup X \}$ となります。
とおきます。
- であることを証明します。
  - のとき
    - $X \subseteq \sup X = \eta$ となります。
  - のとき
    - $X \subseteq \sup X \cup \{ \sup X \} = \eta$ となります。
$\eta \in \{ \alpha \mid X \subseteq \alpha \}$ となります。
$\gamma = \min \{ \alpha \mid X \subseteq \alpha \}$ とおきます。
するととの定義よりが成り立ちます。
- を示します。
  - をとります。を示します。
    - $g(b) = \min \{ \alpha \mid G(\alpha) = b \}$ より $b = G(g(b))$
    - $g(b) \in X \subseteq \gamma$ より $g(b) \in \gamma$
    - $G(g(b)) = b$ より $b \in \mathrm{ran}(G \restriction \gamma)$
- を示します。
  - としてを示します。
    - $a \in \mathrm{ran}(G \restriction \gamma)$ より順序数 $\alpha$ が存在して $a = G(\alpha)$
    - よって $a = G(\alpha) \in B$
はとなる順序数で最小のものです。
- ならばであることを示します。
  - $B = \mathrm{ran}(G \restriction \delta)$ とします。
  - ならばであることを示します。
    - $\alpha \in X$ をとると $b \in B$ が存在して $\alpha = g(b)$
    - $B \subseteq \mathrm{ran}(G \restriction \delta)$ より $\beta \in \delta$ が存在して $b = G(\beta)$
    - $\alpha$ は $b = G(\alpha)$ となる最小のものなので $\alpha \le \beta$
    - よって $\alpha \in \delta$
  - よって $X \subseteq \delta$
- $\gamma$ は $X \subseteq \gamma$ となる最小のものなので $\gamma \le \delta$
を示します。
- なのでと仮定して矛盾を導きます。
  - $B = \mathrm{ran}(G \restriction \gamma)$ なので $A \setminus \mathrm{ran}(G \restriction \gamma) \ne \varnothing$ となります。
  - $G$ の定義より
    $G(\gamma) = c(A \setminus \mathrm{ran}(G \restriction \gamma))$
  - $c$ が $\mathfrak{P}(A) \setminus \{\varnothing\}$ の選択関数であるから
    $G(\gamma) \in A \setminus \mathrm{ran}(G \restriction \gamma) = A \setminus B$
  - これは $B$ の定義( $G(\gamma) \in B$ )に反します。
- したがって $B = A$ となります。
以上より $\gamma$ が $A = \mathrm{ran}(G \restriction \delta)$ となる順序数 $\delta$ で最小のものであることがわかります。
とするとが全単射となることがの定義との最小性からわかります。
- $A = \mathrm{ran}(G \restriction \gamma)$ より $f$ は全射です。
- が単射であることを証明します。
  - $\delta = \min \{ \alpha \mid g(G(\alpha)) \ne \alpha \}$ とします。
  - を示します。
    - を示します。
      - $A \setminus \mathrm{ran}(G \restriction \delta) \ne \varnothing$ と仮定すると $g(G(\delta)) = \delta$ となることを示します。
        
        $G$ の定義より $G(\delta) \in A \setminus \mathrm{ran}(G \restriction \delta)$ となります。
        
        $\alpha < \delta$ ならば $G(\alpha) \in \mathrm{ran}(G \restriction \delta)$ なので $G(\alpha) \ne G(\delta)$ です。
        
        よって $g(G(\delta)) = \min \{ \alpha \mid G(\alpha) = G(\delta) \} = \delta$ となります。
      - これは $g(G(\delta)) \ne \delta$ に矛盾するので $A = \mathrm{ran}(G \restriction \delta)$ となります。
    - $\gamma$ は $A = \mathrm{ran}(G \restriction \gamma)$ となる最小の順序数なので $\gamma \le \delta$
    - $X \subseteq \gamma$ なので $\gamma \notin X$ です。
    - しかし $g(G(\gamma)) \in X$ なので $g(G(\gamma)) \ne \gamma$
    - $\delta$ は $g(G(\delta)) \ne \delta$ となる最小の順序数なので $\delta \le \gamma$
    - よって $\delta = \gamma$ となります。
  - よって $\gamma = \min \{ \alpha \mid g(G(\alpha)) \ne \alpha \}$ となります。
  - $\alpha < \gamma$ ならば $g(G(\alpha)) = \alpha$ となります。
  - $\alpha < \gamma$ ならば $g(f(\alpha)) = \alpha$ となります。
  - $f(\alpha) = f(\beta)$ ならば $g(f(\alpha)) = g(f(\beta))$ 、よって $\alpha = \beta$ となります。
  - よって $f$ は単射です。