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

整列可能定理(6)

整列集合

順序集合は、その空ならざるいかなる部分集合も最初の元をもつとき、整列集合であるという。空(順序)集合 $\varnothing$ は、便宜上整列集合の特別の場合であると考える。整列集合の、空ならざる部分集合 B の最初の元を $\min B$ と書く。

(a) 整列集合の部分集合は、また整列集合である。

[証明]

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

(b) 整列集合に同型な順序集合は、また整列集合である。

[証明]

$(A, \prec)$ を整列集合、 $(B, \prec)$ を順序集合、 $f: A \to B$ を同型写像( $a_1, a_2 \in A$ 、 $a_1 \prec a_2$ ならば $f(a_1) \prec f(a_2)$ となる全単射)とします。
$a_1, a_2 \in A$ 、 $a_1 \prec a_2$ ならば $f(a_1) \prec f(a_2)$ となります。
よって $(B, \prec)$ は全順序集合となります。
$C \subseteq B$ 、 $C \ne \varnothing$ とすると $f^{-1}(C) \subseteq A$ 、 $f^{-1}(C) \ne \varnothing$ となるので $f^{-1}(C)$ は最小元 $a$ を持ちます。
$c \prec f(a)$ となる $c \in C$ があるとします。
$f^{-1}(c) \prec a$ となり、 $a$ が最小元であることに矛盾
よって $f(a)$ は $C$ の最小元となります。
よって $(B, \prec)$ は整列集合となります。

(c) $A$ を整列集合とするとき、 $a_1 \succ a_2 \succ … \succ a_n \succ …$ となるような $A$ の元の列 $a_1, a_2, …, a_n, …$ は存在しない。

[証明]

このような列が存在するとし、 $B = \{a_1, a_2, …, a_n, …\}$ とおきます。
$A$ が整列集合であることから、 $B$ の最小元 $b$ が存在します。
$b = a_n$ となる $n$ が存在します。
$b \succ a_{n+1}$ となり、 $b$ が最小元であることに矛盾
よってこのような列は存在しません。

整列集合 $A$ の元 $a$ に対して、 $a$ よりも前にある元の全体から成る $A$ の部分(順序)集合を、 $A$ の $a$ による切片といい $A(a)$ と書く：
$A(a) = \{ x \mid x \prec a, \ x \in A \}$

(d) $A$ を整列集合とし、 $a \prec b$ なる $A$ の元 $a, b$ をとれば、当然 $a \in A(b)$ である。このとき、 $A(b)$ の $a$ による切片 $A(b)(a)$ をつくれば、それは $A(a)$ と等しい: $A(b)(a) = A(a)$

[証明]

$A(a) = \{ x \mid x \prec a, \ x \in A \}$
$A(b) = \{ x \mid x \prec b, \ x \in A \}$
$A(b)(a) = \{ x \mid x \prec a, \ x \in A(b) \} = \{ x \mid x \prec a, \ x \prec b, \ x \in A \}$
$a \prec b$ のとき、 $x \prec a$ ならば $x \prec b$ となります。
よって $a \prec b$ のとき、 $x \prec a$ であることは $x \prec a$ かつ $x \prec b$ であること同値となります。
よって $A(b)(a) = \{ x \mid x \prec a, \ x \in A \} = A(a)$

(e) 整列集合 $A$ の切片 $A(a)$ のある元 $b$ よりも小さい $A$ の元は、また $A(a)$ に属する。すなわち、 $b \in A(a)$ 、 $x \prec b$ ならば $x \in A(a)$ である。

[証明]

$b \in A(a)$ 、 $x \prec b$ とします。
$x \prec b$ かつ $b \prec a$ なので $x \prec a$ となります。
よって $x \in A(a)$ となります。

(f) $B$ を整列集合 $A$ の部分集合とする。このとき、 $B$ のどの元 $b$ に対しても、それよりも小さい $A$ の元がつねにまた $B$ に属するならば、 $B$ は $A$ と等しいか、さもなければ $A$ のある切片 $A(a)$ と等しい。

[証明]

$A$ を整列集合、 $B \subseteq A$ とします。
(a) より $B$ も整列集合となります。
任意の $b \in B$ に対して、任意の $a \in A$ に対して $a \prec b$ ならば $a \in B$ であるとします。
任意の $b \in B$ に対して、 $A(b) \subseteq B$ となります。(1)
$B \ne A$ とします。
$a = \min ( A \setminus B )$ とします。
$A(a) \subseteq B$ 、 $a \notin B$ となります。(2)
であることを証明します。
- $b \in B \setminus A(a)$ をとります。
- $a \in A(b)$ となります。(3)
- (1) より $A(b) \subseteq B$ となります。
- (3) より $a \in A(b) \subseteq B$ となり、(2) $a \notin B$ に矛盾
- よって $B \subseteq A(a)$ となります。
よって $B = A(a)$ となります。

(g) $φ$ を整列集合 $A$ から整列集合 $B$ への同型対応とする。しからば、 $A$ の任意の切片 $A(a)$ の $φ$ による像 $A(a)^φ$ は、 $B$ の切片 $B(φ(a))$ に等しい。

[証明]

$a' \in A(a)$ とすると $a' \prec a$
$φ(a') \prec φ(a)$
$φ(a') \in B(φ(a))$
よって $A(a)^φ \subseteq B(φ(a))$
$b \in B(φ(a))$ とすると $b \prec φ(a)$
$φ^{-1}(b) \prec a$
$φ^{-1}(b) \in A(a)$
$b \in A(a)^φ$
よって $A(a)^φ \supseteq B(φ(a))$
よって $A(a)^φ = B(φ(a))$

定理 1. 整列集合 $A$ からその部分集合 $B$ への同型対応を $φ$ とすれば、 $A$ のいかなる元 $a$ に対しても
$φ(a) = a$ または $φ(a) \succ a$
が成立する。
[証明]

$φ(a) \prec a$ となる $a$ が存在するとします。
$a = \min \{ a \mid φ(a) \prec a \}$ とおくと $φ(a) \prec a$
両辺を $φ$ で写すと $φ$ が順序を保存することから $φ(φ(a)) \prec φ(a)$
$φ(a) \in \{ a \mid φ(a) \prec a \}$ となり $a$ が最小元であることに矛盾
よって任意の $a \in A$ に対して $φ(a) = a$ または $φ(a) \succ a$ となります。

(a) 整列集合 $A$ から $A$ 自身への同型対応は、 $A$ のいかなる元 $a$ に対しても $φ(a) = a$ となる関数 $φ$ 、すなわち $A$ 上の恒等関数以外にはあり得ない。

[証明]

定理 1 より $φ: A \to A$ を同型対応とすると、任意の $A$ の元 $a$ に対して
$φ(a) = a$ または $φ(a) \succ a$
が成り立ちます。
同様に
$φ^{-1}(a) = a$ または $φ^{-1}(a) \succ a$
が成り立ちます。
よって $φ(a) = a$ が成り立ちます。

(b) 整列集合 $A$ から整列集合 $B$ への同型対応は、あってもただ一つである。

[証明]

$f: A \to B$ 、 $g: A \to B$ を同型対応とすると、 $f \circ g^{-1}: B \to B$ は同型対応となります。
(a) より $f \circ g^{-1}$ は恒等写像
よって $f = g$

(c) 整列集合は、そのいかなる切片とも同型にはなり得ない。さらに一般に、整列集合は、そのいかなる部分集合のいかなる切片とも同型になり得ない。

[証明]

$A$ を整列集合、 $B$ をその部分集合、 $B(b)$ をその切片とします。
$f: A \to B(b)$ を同型対応とすると、(a) より $f$ は恒等写像となります。
$f(b) = b \notin B(b)$ となり矛盾
よってこのようは $f$ は存在しません。

(d) $A, B$ を整列集合とするとき、 $A$ は $B$ の二つの異なる切片と同時に同型になり得ない。

[証明]

$b_1, b_2 \in B$ 、 $b_1 \prec b_2$ とします。
$B(b_1)$ は $B(b_2)$ の切片となります。
(c) より $B(b_1)$ は $B(b_2)$ と同型になりません。
よって $A$ は $B(b_1)$ と $B(b_2)$ の両方と同型にはなりません。

(e) 整列集合 $A$ の二元 $a_1, \ a_2$ および整列集合 $B$ の二元 $b_1, \ b_2$ に対して

$A(a_1) \simeq B(b_1), \ A(a_2) \simeq B(b_2)$
が成立するとする。しかるときは、 $a_1 \prec a_2$ ならば $b_1 \prec b_2$ である。
[証明]

$f: A(a_1) \to B(b_1)$ 、 $g: A(a_2) \to B(b_2)$ を同型対応とします。
$a_1 \prec a_2$ とすると、(g) より $A(a_1)$ の $g$ による像 $A(a_1)^g$ は、 $B(b_2)$ の切片 $B(g(a_1))$ に等しい。
$g$ の $A(a_1)$ への制限 $g \restriction A(a_1)$ により $A(a_1)$ と $B(g(a_1))$ は同型となります。
(d) により $B(b_1) = B(g(a_1))$ となります。
よって $b_1 = g(a_1) \in B(b_2)$ となります。
よって $b_1 \prec b_2$ となります。

(f) $A, B$ を整列集合とする。このとき、 $A(a) \simeq B(b)$ なる $B$ の元 $b$ があるような $A$ の元 $a$ 全体の集合は、 $A$ と一致するか、さもなければ $A$ のある切片と一致する。

[証明]

$A_1 = \{ a \in A \mid \exists b \in B : A(a) \simeq B(b) \}$ とおきます。
$A_1 \ne A$ とします。
$a = \min (A \setminus A_1)$ とおきます。
$a \notin A_1$ 、 $A(a) \subseteq A_1$ となります。
$A(a) \ne A_1$ と仮定します。
$a' \in A_1 \setminus A(a)$ をとります。
$b \in B$ が存在して $A(a') \simeq B(b)$
同型 $f: A(a') \to B(b)$ が存在します。
(定理 1 の前の) (g) より $f$ による $A(a)$ の像は $B(f(a))$ となります。
$a \in A_1$ となり矛盾
よって $A(a) = A_1$ となります。

定理 2. $A, B$ を整列集合とすれば次の三つの場合のただ一つだけが成立する：
(1) $A$ は $B$ と同型
(2) $A$ は $B$ のある切片と同型
(3) $B$ は $A$ のある切片と同型

[証明]

$A_1 = \{ a \in A \mid \exists b \in B : A(a) \simeq B(b) \}$
$B_1 = \{ b \in B \mid \exists a \in A : A(a) \simeq B(b) \}$
とおきます。
(d) より任意の $a \in A_1$ に対して $A(a) \simeq B(b)$ となる $b \in B_1$ がただ一つ存在します。
この関数を $\varphi$ とおきます。
(e) より $a_1 \prec a_2$ ならば $\varphi(a_1) \prec \varphi(a_2)$
よって $A_1 \simeq B_1$
(f)より
$A_1$ は $A$ と一致するか、 $A$ のある切片と一致し、
$B_1$ は $B$ と一致するか、 $B$ のある切片と一致します。
がのある切片と一致し、
がのある切片一致することはありません。
- もしそうならば
  - $A(a) = A_1 \simeq B_1 = B(b)$
  - $a \in A_1 = A(a)$
  - $a \prec a$ となり矛盾
次の三つの場合が考えられます。
- (1) $A_1 = A$ かつ $B_1 = B$ のとき。このときは $A \simeq B$
- (2) $A_1 = A$ かつ $B_1 = B(b)$ のとき。このときは $A \simeq B(b)$
- (3) $A_1 = A(a)$ かつ $B_1 = B$ のとき。このときは $A(a) \simeq B$
これらのどの二つも両立しません。
- (1) と (2) が両立したとすると、 $B \simeq B(b)$ となって (c) に矛盾
- (1) と (3) が両立したとすると、 $A \simeq A(a)$ となって (c) に矛盾
- (2) と (3) が両立したとすると、
  - $A$ から $B(b)$ への同型対応を $\varphi$ とすると
  - それによる $A(a)$ の像は、 $B(b)$ の、したがって $B$ のある切片 $B(b')$ に等しい。
  - $B \simeq A(a) \simeq B(b')$ となって (c) に矛盾