整列可能定理

Theorem 整列可能定理

$\forall S($:Set,$\neq \emptyset),\exists \le$(:Order), such that $(S,\le)$ is 整列集合.

Proof

Let
$\mathcal{W} = \{(W_\lambda,\lt_\lambda)|W_\lambda: \text{整列集合}, W_\lambda \subset S \}$
$\mathcal{W} \neq \emptyset \because s \in S, (\{s\})$ is always 整列集合.
an order $\lt_{\mathcal{W}}$ on $\mathcal{W}$ defined as below.
for $(W_\alpha, \lt_\alpha),(W_\beta, \lt_\beta) \in \mathcal{W}$
if $\exists b \in W_\beta, W_\alpha = W_\beta \lt b \gt$ then $(W_\alpha, \lt_\alpha) \lt_{\mathcal{W}} (W_\beta, \lt_\beta)$
if $\exists a \in W_\alpha, W_\alpha \lt a \gt = W_\beta$ then $(W_\beta, \lt_\beta) \lt_{\mathcal{W}} (W_\alpha, \lt_\alpha)$
(以後 $(W_\alpha, \lt_\alpha) \lt_{\mathcal{W}} (W_\beta, \lt_\beta)$ を単に $W_\alpha \lt_{\mathcal{W}} W_\beta$ と書く)

$(\mathcal{W},\lt_{\mathcal{W}})$ is a partially ordered set.($\because$ ovious.)
$(\mathcal{W},\lt_{\mathcal{W}})$ is a recursive set.---(1)
$\therefore \exists$ 極大元 $(A_0, \lt_{A_0})$ on $\mathcal{W}$ ($\because$ ツォルンの補題)
$A_0 = S$---(5)

(Proof-(1))
$\forall \mathcal{W}_0$:全順序部分集合 of $\mathcal{W}$
($\Leftrightarrow$
$\mathcal{W}_0 \subset \mathcal{W}$ and
$(W_\alpha, \lt_\alpha),(W_\beta, \lt_\beta) \in \mathcal{W}_0 \Rightarrow$
$W_\alpha \lt_{\mathcal{W}} W_\beta$ or $W_\beta \lt_{\mathcal{W}} W_\alpha$
)
Let
$W_0 = \bigcup(W_\lambda|W_\lambda \in \mathcal{W}_0)$
then
$W_0 \in \mathcal{W}$ --- (2)
$\forall W_\lambda \in \mathcal{W}_0 \Rightarrow W_\lambda \lt_{\mathcal{W}} W_0$ or $W_\lambda = W_0$---(3)
$\therefore W_0$ is a 上界 of $\mathcal{W}_0$
$\therefore \mathcal{W}$ is a recursive set.
(end of Proof-(1))

(Proof-(2))
$\forall M \subset W_0 \quad (M \neq \emptyset)$
$\exists W_\lambda \in \mathcal{W}_0, M \cap W_\lambda \neq \emptyset$
$W_\lambda$:整列集合 and $M \cap W_\lambda \subset W_\lambda \therefore \exists m = \min M \cap W_\lambda$
$x \in M$
$x \in W_\lambda \Rightarrow x \in M \cap W_\lambda \therefore m \lt_\lambda x$
$x \notin W_\lambda \Rightarrow \exists \lambda', x \in W_{\lambda'} \in \mathcal{W}_0$
$W_\lambda \subset W_{\lambda'} \therefore W_\lambda \lt_{\mathcal{W}} W_{\lambda'} \therefore \exists a \in W_{\lambda'}, W_\lambda = W_{\lambda'} \lt a \gt$
$\therefore m \lt_{\lambda'} a \le_{\lambda'} x$
$\therefore m = \min M$
$\therefore W_0 \in \mathcal{W}$
(end of Proof-(2))

(Proof-(3))
任意の$W_\lambda \in \mathcal{W}_0$を固定する
$\forall W_\lambda' \in \mathcal{W}_0$
if $W_\lambda' \subset W_\lambda \Rightarrow W_\lambda = W_0$ is obvious.
else $W_\lambda' \not\subset W_\lambda \Rightarrow W_\lambda \subsetneq W_0 \therefore W_0 - W_\lambda \neq \emptyset \therefore \exists m = \min W_0 - W_\lambda$
$x \in W_0\lt m \gt \Rightarrow x \lt_{W_0} m \Rightarrow x \notin W_0 - W_\lambda \therefore x \in W_\lambda$
$x \in W_\lambda \Rightarrow x \lt_{W_0} m$---(4)
$\therefore x \in W_0 \lt m \gt$
$\therefore W_\lambda = W_0\lt m \gt$
$\therefore W_\lambda \lt_{\mathcal{W}} W_0$
(end of Proof-(3))

(Proof-(4))
Suppose $m \le_{W_0} x$
$\exists W_{\lambda'}, m \in W_{\lambda'} \in \mathcal{W}_0$
$W_\lambda \lt_{\mathcal{W}} W_{\lambda'}$ or $W_{\lambda'} \lt_{\mathcal{W}} W_\lambda$ or $W_\lambda = W_{\lambda'}$
if $W_{\lambda'} = W_\lambda$ contradiction ($\because m \in W_0 - W_\lambda)$
if $W_{\lambda'} \lt_{\mathcal{W}} W_\lambda \Rightarrow \exists a \in W_\lambda, W_{\lambda'} = W_\lambda \lt a \gt \Rightarrow m \in W_{\lambda'} \subset W_\lambda$ contradiction ($\because m \in W_0 - W_\lambda)$
if $W_\lambda \lt_{\mathcal{W}} W_{\lambda'} \Rightarrow \exists a \in W_{\lambda'}, W_\lambda = W_{\lambda'} \lt a \gt \Rightarrow x \in W_\lambda \subset W_{\lambda'} \Rightarrow m \le_{W_0} x \lt_{W_0} a \therefore m \in W_\lambda$ contradiction
$\therefore x \lt_{W_0} m$
(end of Proof-(4))

(Proof-(5))
for $x \in S - A_0$
$A_0' = A_0 \cup \{x\}$ and define $\lt_{A_0'}$ as $\forall a \in A_0, a \lt_{A_0'} x$
then $A_0' \in \mathcal{W}$ and is 整列集合 and $A_0 \lt_{\mathcal{W}} A_0'$ contradiction.
$\therefore A_0 = S$
(Q.E.D.)

Theorem

整列可能定理　$\Rightarrow$　選択公理
* therefore
選択公理, zornの補題, 整列可能定理 are equivalent.

Proof

$\forall \{X_\lambda|\lambda \in \Lambda, X_\lambda \neq \emptyset\}$(任意の非空集合族)
Let $Z = \bigcup_{\lambda \in \Lambda} X_\lambda$
$\exists \lt_Z$ such that $(Z, \lt_Z)$ is 整列集合.($\because$ 整列可能定理を$Z$に適用)
then
$\phi:\Lambda \rightarrow Z(=\bigcup_{\lambda \in \Lambda} X_\lambda)$
$\phi:\lambda \mapsto m(= \min X_\lambda)$
を定義することができる
$\because Z$ is 整列集合. $\Rightarrow \forall X_\lambda \subset Z, \exists \min X_\lambda$
then
$\phi$ is a 選択関数.
(Q.E.D.)