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

『公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』から少し追加します。

定理 1.6 (超限帰納法) 整列集合 $(A, <)$ と $A$ の元 $a$ についての命題 $φ(a)$ が与えられているとする。すべての $a \in A$ に対して、「どんな $b < a$ に対しても $φ(b)$ が成り立てば、 $φ(a)$ が成り立つ」という条件が成り立っているとする。このとき、すべての $a \in A$ に対して、 $φ(a)$ が成り立つ。
[証明]

$φ(a)$ が成り立たない $a \in A$ が存在すると仮定します。
すると $(A, <)$ が整列集合であることから $φ(a)$ が成り立たない最小の $a \in A$ が存在します。
すると定理の仮定から $φ(a)$ が成り立つことになり、 $φ(a)$ が成り立たないことに矛盾します。
よってすべての $a \in A$ に対して、 $φ(a)$ が成り立ちます。

定義整列集合 $(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)$ が成り立つ。

補題 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$ が成り立つ。
(4) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \in \beta$ 、 $\alpha = \beta$ 、 $\beta \in \alpha$ のいずれか一つのみが成り立つ。
(5) $X$ を順序数からなる集合とすると、 $\displaystyle \sup X = \bigcup_{\alpha \in X} \alpha$ も順序数となる。
(6) $X$ を順序数からなる空でない集合とすると、 $\displaystyle \inf X = \bigcap_{\alpha \in X} \alpha$ も順序数となる。

定義 2.2 順序数全体を $\mathbf{Ord}$ と書き、順序数 $\alpha, \ \beta$ に対して $\alpha \in \beta$ が成り立っているとき、 $\alpha < \beta$ と書く。

補題 2.3 (1) $\alpha$ の順序数とすると、 $S(\alpha) = \alpha \cup \{\alpha\}$ は $\alpha < \beta$ となる最小の順序数 $\beta$ である。
[証明]

は順序数であることを証明します。
- ならばであることを証明します。
  - $y \in \alpha \cup \{\alpha\}$ ならば $y \in \alpha$ または $y = \alpha$
  - $y \in \alpha$ のときは $\alpha$ は順序数なので推移律より $x \in \alpha$ となります。
  - $y = \alpha$ のときは $x \in y = \alpha$ となります。
- は整列集合であることを証明します。
  - が全順序集合であることを証明します。
    - は、、のどれかを満たすことを証明します。
      - $\beta \in \alpha$ または $\beta = \alpha$ 、 $\gamma \in \alpha$ または $\gamma = \alpha$ です。
      - $\beta \in \alpha$ 、 $\gamma \in \alpha$ のときは $\alpha$ が全順序集合であることから成り立ちます。
      - $\beta = \alpha$ 、 $\gamma = \alpha$ のときは $\beta = \gamma$ です。
      - $\beta \in \alpha$ 、 $\gamma = \alpha$ のときは $\beta \in \gamma$ です。
      - $\gamma \in \alpha$ 、 $\beta = \alpha$ のときは $\gamma \in \beta$ です。
    - はかつならばであることを証明します。
      - $\delta \in \alpha$ または $\delta = \alpha$ です。
      - $\delta \in \alpha$ のときは $\alpha$ が全順序集合であることから成り立ちます。
      - $\delta = \alpha$ のときは $\alpha$ が順序数であることから成り立ちます。
  - の空でない部分集合に最小元があることを証明します。
    - $X = (X \cap \alpha) \cup (X \cap \{\alpha\})$ となります。
    - $X \cap \alpha = \varnothing$ のときは $X \subseteq \{\alpha\}$ となり、 $X$ は空集合ではないので $X = \{\alpha\}$ となって $\alpha$ が最小元となります。
    - $X \cap \alpha \ne \varnothing$ のときは $\alpha$ が整列集合であることから $\mu = \min ( X \cap \alpha )$ が存在します。
    - $\mu \in \alpha$ なので $\mu = \min ( X \cap (\alpha \cup \{\alpha\}) )$ となります。
- 以上により $\alpha \cup \{\alpha\}$ は順序数です。
$\alpha \in \alpha \cup \{\alpha\}$ なので $\alpha < \alpha \cup \{\alpha\}$ です。
$\beta$ を $\alpha < \beta$ となる順序数とします。
$\beta \in \alpha \cup \{\alpha\}$ とすると $\beta \in \alpha$ または $\beta = \alpha$ です。
しかし補題 2.1 (4) よりこのようになることはありません。
よって補題 2.1 (4) より $\alpha \cup \{\alpha\} \le \beta$ となります。
よって $S(\alpha) = \alpha \cup \{\alpha\}$ は $\alpha < \beta$ となる最小の順序数 $\beta$ です。

$S(\alpha)$ のことを $\alpha + 1$ と書くことにします。

(2) $X$ を順序数からなる集合とすると、 $\sup X$ は $X$ の上限である。
[証明]

$\beta = \sup X$ とおきます。
ならばである( はの上界である)ことを証明します。
- $\alpha \in X$ とします。
- $X$ に最大元があれば $\beta$ が最大元なので $\alpha \le \beta$ です。
- $X$ に最大元がなければ $\alpha < \alpha'$ となる $\alpha' \in X$ が存在します。
- $\alpha \in \alpha' \subseteq \bigcup_{\alpha \in X} \alpha = \beta$
- よって $\alpha \le \beta$ となります。
ならばとなるが存在する( ならばはの上界ではない)ことを証明します。
- $\gamma < \beta$ とします。
- $\gamma \in \beta = \bigcup_{\alpha \in X} \alpha$
- $\gamma \in \alpha$ となる $\alpha \in X$ が存在します。
- よって $\gamma < \alpha$ となる $\alpha \in X$ が存在します。
よって $\sup X$ は $X$ の上限となります。