# 整列集合

## Proposition 1

### Proof

$S$:整列集合 $\forall a,b \in S$ に対して $\{a,b\} \subset S$
$a = \min\{a,b\}$ or $b = \min\{a,b\}$
$\therefore a \le b$ or $a \ge b$.

## Theorem 2

Suppose
$(X, \le)$:整列集合
$\phi:X \rightarrow X$:順序を保つ単射
then
$x \le \phi(x)$

### Proof

Let
$A = \{x \in X|x \gt \phi(x)\}$
$a = \min A$
then
$a \gt \phi(a)$
$\phi(a) \gt \phi(\phi(a))$
$\therefore \phi(a) \in A$
$\phi(a) \lt a = \min A \Rightarrow$ contradiction

## Proposition 3

Suppose $(X, \le_X)$, $(Y, \le_Y)$:整列集合
$X \simeq Y$
$\phi:X \rightarrow Y$:順序同型写像
then
$\forall a \in X \Rightarrow X \lt a \gt \simeq Y \lt \phi(a) \gt$

### Proof

Let
$\phi':X \lt a \gt \rightarrow Y$
$\phi' = \phi|_{X \lt a \gt} \quad (\phi'(x) = \phi(x))$
then

$\phi'(X \lt a \gt) = Y \lt \phi(a) \gt$を示す.
(i)$y \in \phi'(X \lt a \gt)$
$\Rightarrow \exists x \lt a, s.t. \phi'(x) = y$
$\Rightarrow \phi(x) \lt \phi(a)$
$\Rightarrow y = \phi'(x) = \phi(x) \in Y \lt \phi(a) \gt$
(ii)$y \in Y \lt \phi(a) \gt$
$\Rightarrow y \lt \phi(a)$
$\Rightarrow \phi^{-1}(y) \lt a$
$\Rightarrow \phi^{-1}(y) \in X \lt a \gt$
$\Rightarrow y \in \phi(X \lt a \gt) = \phi'(X \lt a \gt)$
(i),(ii)$\therefore \phi'(X \lt a \gt) = Y \lt \phi(a) \gt$

## Theorem 4

Let
$(X, \le_X)$, $(Y, \le_Y)$:整列集合
$X_1 = \{x \in X| \exists y \in Y s.t. X\lt x \gt \simeq Y\lt y \gt\}$
then
$X_1 = X$ or
$\exists a \in X s.t. X_1 = X\lt a \gt$

### Proof

Let
$a \in X_1$,
$\phi:X\lt a \gt \rightarrow Y \lt b \gt \quad (X\lt a \gt \simeq Y \lt b \gt)$.
then
$x \in X \lt a \gt \Rightarrow X \lt x \gt \simeq Y \lt \phi(x) \gt$
$\therefore x \in X_1$
$\therefore a \in X_1 \Rightarrow X \lt a \gt \subset X_1$
Suppose $X - X_1 \neq \emptyset$
then $\exists a_1 = \min(X - X_1)$
(i)$a_1 \notin X_1, X \lt a_1 \gt \subset X_1 (\because a_1 = \min (X - X_1))$
(ii)$a \in X_1 \Rightarrow a \in X \lt a_1 \gt(\because a_1 \lt a \Rightarrow a_1 \in X \lt a \gt \subset X_1) \therefore X_1 \subset X \lt a \gt$
(i),(ii)$\therefore X \lt a_1 \gt = X_1$

## Proposition 5

$X$:整列集合
then
(i)$\nexists a \in X, s.t. X = X \lt a \gt$
(ii)$\nexists a, b \in X, s.t. (a \neq b \Rightarrow X \lt a \gt \simeq X \lt b \gt)$

### Proof

Suppose
$\phi:X \rightarrow X$ 順序を保つ単射
$a,b \in X, a \lt b$
(i)$a \le \phi(a) \therefore \phi(a) \notin X \lt a \gt \therefore \nexists a \in X \simeq X \lt a \gt$
(ii)$a \le \phi(a) \therefore \phi(a) \notin X \lt a \gt \therefore X \lt b \gt \simeq X \lt a \gt$

## Theorem 6 整列集合の比較定理

Let
$(X, \le_X)$, $(Y, \le_Y)$:整列集合
then

(1) $X$と$Y$ は順序同型
(2) $X$と$Y$のある切片は順序同型
(3) $X$のある切片と$Y$は順序同型

### Proof

Let
$X_1 = \{a \in X| \exists b \in Y s.t. X\lt a \gt \simeq Y\lt b \gt\}$
$Y_1 = \{b \in Y| \exists a \in X s.t. X\lt a \gt \simeq Y\lt b \gt\}$
$\phi:X_1 \rightarrow Y_1$
$\phi:x \mapsto y \quad X \lt x \gt \simeq Y \lt y \gt$
then $\phi$ is well-defined and $\phi$ は順序同型射像. すなわち $X_1 \simeq Y_1$
$\because x \in X_1 \Rightarrow \exists y \in Y_1 s.t. X \lt x \gt \simeq Y \lt y \gt$ and $y$ is unique.($\because X \lt x \gt \simeq Y \lt y_1 \gt, X \lt x \gt \simeq Y \lt y_2 \gt \Rightarrow y_1 = y_2$)
$\therefore \phi$ is well-defined
Let
$a \in X_1, b = \phi(a)$ すなわち $X \lt a \gt \simeq Y \lt b \gt$
then $c \lt a \Rightarrow \exists d \in Y \lt b \gt s.t. X \lt c \gt \simeq Y \lt d \gt (\because$ Proposition 3).
$\therefore \phi(c) = d \lt b$
$\therefore \phi$ は順序を保つ射像.
$\phi$が全単射であることは明らか.
$\therefore \phi$ は準同型射像であり$X_1 \simeq Y_1$. because of Theorem 4,
$X_1 = X$ or
$\exists a \in X, X_1 = X \lt a \gt$
$Y_1 = Y$ or
$\exists b \in Y, Y_1 = Y \lt b \gt$
if
$X_1 = X \lt a \gt$ and $Y_1 = Y \lt b \gt$
at the same time, then
$X \lt a \gt = X_1 \simeq Y_1 = Y \lt b \gt$
$\therefore a \in X_1, b \in Y_1 \Rightarrow$ contradiction.
$\therefore$
(1) $X$と$Y$ は順序同型
or
(2) $X$と$Y$のある切片は順序同型
or
(3) $X$のある切片と$Y$は順序同型
(1) and (2) $\Rightarrow Y \simeq X \simeq Y \lt b \gt \Rightarrow$ contradiction.
(1) and (3) $\Rightarrow X \simeq Y \simeq X \lt a \gt \Rightarrow$ contradiction.
(2) and (3) $\Rightarrow$
$f:X \simeq Y \lt b \gt$
$g:Y \simeq X \lt a \gt$
$g\circ f:X \rightarrow X$ is a injection.
$\therefore g \circ f(a) \lt a \Rightarrow$ contradiction($\because$ Theorem 2).

## Theorem 7 超限帰納法

Let
$(A, \le)$:整列集合
$P:a \in A \mapsto \{true,false\}$ then
(1)$P(\min A) = true$
(2)$\forall a \in A, \forall x \in A \lt a \gt, P(x) = true \Rightarrow P(a) = true$
(1),(2)$\Rightarrow \forall a \in A, P(a) = true$

### Proof

Let $A_1 = \{x \in A| P(x) = false \}$.
Suppose $A_1 \neq \emptyset$
$\Rightarrow\exists a_1 = \min A_1$
$P(a_1) = flase, \therefore a_1 \neq \min A$ ($\because$ (1))
$\Rightarrow A \lt a_1 \gt \neq \emptyset$ and $P(A \lt a_1 \gt) = true$
$P(A \lt a_1 \gt) = true \Rightarrow P(a_1) = true$ ($\because$ (2))
$\Rightarrow$ contradiction $\therefore A_1 = \emptyset$