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

「証明路開発支援システム(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)$ は整列集合である。

定理整列集合の部分集合は、整列集合である。
[証明]

$(A, \prec)$ を整列集合、 $B \subseteq A$ とします。
$(B, \prec)$ は全順序集合となります。
$C \subseteq B$ 、 $C \ne \varnothing$ とすると $C \subseteq A$ となるので $C$ は最小元を持ちます。
よって $(B, \prec)$ は整列集合となります。

補題 2.1 (1) $\alpha$ を順序数として $x \in \alpha$ とすると、 $x$ も順序数である。
[証明]

ならばであることを証明します。
- $\alpha$ は順序数なので推移律より $z, \ y \in \alpha$ です。
- $(\alpha, \in)$ が順序集合であることから $z \in x$ が成り立ちます。
は整列集合であることを証明します。
- はの部分集合であることを証明します。
  - $y \in x$ とすると $\alpha$ は順序数なので推移律より $y \in \alpha$ です。
  - よって $x$ は $\alpha$ の部分集合です。
- $x$ は整列集合 $\alpha$ の部分集合なので整列集合となります。
以上により $x$ は順序数です。

(2) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \in \beta$ と $\alpha \subsetneq \beta$ は同値になる。
[証明]

ならばであることを証明します。
- $\alpha \in \beta$ とします。
- (1) の証明と同様に $\alpha \subseteq \beta$ となります。
- $\alpha \in \beta$ なので $\alpha \ne \beta$ です。
- よって $\alpha \subsetneq \beta$ となります。
ならばであることを証明します。
- $\alpha \subsetneq \beta$ とします。
- $\gamma = \min ( \beta \setminus \alpha )$ とします。
- を証明します。
  - $x \in \gamma$ とすると $\gamma$ の最小性から $x \in \alpha$
  - よって $\gamma \subseteq \alpha$ となります。
  - $\gamma \subsetneq \alpha$ と仮定して $\delta \in \alpha \setminus \gamma$ をとります。
  - 、、は全順序集合なので
    またはまたは
    が成り立ちます。
    - $\gamma \in \delta$ とすると $\gamma \in \delta \in \alpha$ より $\gamma \in \alpha$ となり $\gamma \notin \alpha$ に矛盾
    - $\gamma = \delta$ とすると $\gamma = \delta \in \alpha$ より $\gamma \in \alpha$ となり $\gamma \notin \alpha$ に矛盾
    - $\gamma \ni \delta$ とすると $\delta \notin \gamma$ に矛盾
  - よって $\delta \in \alpha \setminus \gamma$ となる $\delta$ は存在しません。
  - よって $\gamma = \alpha$ となります。
- よって $\alpha = \gamma \in \beta$ となります。
よって $\alpha \in \beta$ と $\alpha \subsetneq \beta$ は同値となります。

(3) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \subseteq \beta$ あるいは $\beta \subseteq \alpha$ が成り立つ。
[証明]

は順序数であることを証明します。
- ならばであることを証明します。
  - $x \in y \in \alpha \cap \beta \subseteq \alpha$ 、 $\alpha$ は順序数なので推移律より $x \in \alpha$ です。
  - $x \in y \in \alpha \cap \beta \subseteq \beta$ 、 $\beta$ は順序数なので推移律より $x \in \beta$ です。
  - よって $x \in \alpha \cap \beta$ が成り立ちます。
- は整列集合であることを証明します。
  - $\alpha \cap \beta$ は整列集合 $\alpha$ の部分集合なので整列集合となります。
- 以上により $\alpha \cap \beta$ は順序数です。
かつならば矛盾となることを証明します。
- $\alpha \not\subseteq \beta$ ならば $\alpha \cap \beta \subsetneq \alpha$ となります。
- (2) より $\alpha \cap \beta \in \alpha$ となります。
- $\beta \not\subseteq \alpha$ ならば $\alpha \cap \beta \subsetneq \beta$ となります。
- (2) より $\alpha \cap \beta \in \beta$ となります。
- よって $\alpha \cap \beta \in \alpha \cap \beta$ となり矛盾。
よって $\alpha \subseteq \beta$ または $\beta \subseteq \alpha$ となります。

(4) $\alpha$ と $\beta$ を順序数とすると、 $\alpha \in \beta$ 、 $\alpha = \beta$ 、 $\beta \in \alpha$ のいずれか一つのみが成り立つ。
[証明]

$\alpha$ と $\beta$ を順序数とすると、(3) より $\alpha \subseteq \beta$ または $\beta \subseteq \alpha$ となります。
よって $\alpha \subsetneq \beta$ または $\alpha = \beta$ または $\beta \subsetneq \alpha$ となります。
よって (2) より $\alpha \in \beta$ または $\alpha = \beta$ または $\beta \in \alpha$ となります。

(5) $X$ を順序数からなる集合とすると、 $\displaystyle \sup X = \bigcup_{\alpha \in X} \alpha$ も順序数となる。
[証明]

ならばであることを証明します。
- $y \in \alpha$ となる $\alpha \in X$ が存在します。
- $\alpha$ は順序数なので推移律より $x \in \alpha$ です。
- よって $x \in \alpha \subseteq \sup X$ となります。
は整列集合であることを証明します。
- が全順序集合であることを証明します。
  - は、、のどれかを満たすことを証明します。
    - $\beta, \ \gamma \in \alpha$ となる $\alpha \in X$ が存在します。
    - $\alpha$ は全順序集合なので $\beta \in \gamma$ 、 $\beta = \gamma$ 、 $\beta \ni \gamma$ のどれかを満たします。
  - はかつならばであることを証明します。
    - $\beta, \ \gamma, \ \delta \in \alpha$ となる $\alpha \in \sup X$ が存在します。
    - $\alpha$ は全順序集合なので $\beta \in \gamma$ かつ $\gamma \in \delta$ ならば $\beta \in \delta$ となります。
- の空でない部分集合に最小元があることを証明します。
  - $\beta \in S$ をとります。
  - $\beta \in \alpha$ となる $\alpha \in X$ が存在します。
  - $\gamma = \min ( \alpha \cap S )$ とおきます。
  - がならばであることを証明します。
    - (4) より $\gamma \ne \delta$ ならば $\gamma \in \delta$ または $\delta \in \gamma$ となります。
    - $\delta \in \gamma$ ならば $\delta \in \gamma \in \alpha$ より $\delta \in \alpha$
    - $\delta \in \alpha \cap S$ となり $\gamma$ の最小性から $\gamma = \delta$ または $\gamma \in \delta$ となって矛盾
  - よって $\gamma$ は $S$ の最小元となります。
以上により $\sup X$ は順序数です。

(6) $X$ を順序数からなる空でない集合とすると、 $\displaystyle \inf X = \bigcap_{\alpha \in X} \alpha$ も順序数となる。
[証明]

ならばであることを証明します。
- 任意の $\alpha \in X$ に対して $y \in \alpha$ となります。
- $\alpha$ は順序数なので推移律より $x \in \alpha$ です。
- よって任意の $\alpha \in X$ に対して $x \in \alpha$ となります。
- よって $x \in \inf X$ となります。
は整列集合であることを証明します。
- $\alpha \in X$ が存在し、 $\inf X$ は整列集合 $\alpha$ の部分集合なので整列集合となります。
以上により $\inf X$ は順序数です。