整列順序 - イガブロギュ

線形順序 $(P,<)$ が整列順序(well-ordered set)であるとは, $P$ の任意の空でない部分集合が最小元を持つこと.
整列順序は互いにその"長さ"を比較可能です.
順序数とも関係があります.

補題
$(W,<)$ が整列順序で $f:W \rightarrow W$ が増加関数であるとき, 任意の $x \in W$ について $f(x) \geq x$ .

証明
$f(x) < x$ なる $x \in W$ が存在すると仮定すると, [tex:X=\{x \in W:f(x)
系
整列順序の自己同型は恒等写像のみ.

証明
$f$ を整列順序 $W$ の自己同型とすると, 任意の $x \in W$ について
(i) $f(x) \geq x$ .
(ii) $f^{-1}(x) \geq x$ であることから, それぞれに $f$ を適用すると $f$ が順序を保つことから $x \geq f(x)$ .
以上により $f(x) = x$ .

系
二つの整列順序 $W_1$ , $W_2$ が同型のとき, 同型写像はユニーク.

証明
$f$ , $g$ が $W_1$ から $W_2$ への同型写像とすると, $g^{-1} \circ f$ は $W_1$ から $W_1$ への同型写像になるので恒等写像である.
よって, $f=g$ .

整列順序 $W$ と $u \in W$ に対し, その始切片(initial segment)を次のように定義します.
$W(u) = \{x \in W:x < u\}$ .

補題
整列順序はそれ自身の始切片とは同型にならない.

証明
$f$ を整列順序 $W$ からその始切片 $W(u)$ への同型写像とすると, [tex:f(u) \in \rm{ran}(f) = W(u) = \{x \in W:x
定理
整列順序 $W_1$ , $W_2$ について, 次の三つのうちのいずれか一つのみが成り立つ.
(i) $W_1$ と $W_2$ は同型.
(ii) $W_1$ のある始切片と $W_2$ が同型.
(iii) $W_1$ と $W_2$ のある始切片が同型.

証明
$f = \{(x,y) \in W_1 \times W_2 : W_1(x)$ と $W_2(y)$ が同型 $\}$
と定義します.
まず, $f$ が関数で単射であることを示します.
$(x,y) \in f$ かつ $(x,z) \in f$ とすると, $W_2(y)$ と $W_2(z)$ が同型になります.
これらのうちのいずれかがもう一方の始切片になりますが, 自身の始切片への同型写像は存在しないことから $W_2(y) = W_2(z)$ であり, 結局 $y=z$ です.
したがって, $f$ は関数です.
全く同様にして, $(x,y) \in f$ かつ $(x',y) \in f$ であるならば, つまり $f(x)=f(x')$ ならば, $x=x'$ であることが示されます.
したがって, $f$ は単射です.
次に, $f$ が順序を保つことを示します.
[tex:x'