ツォルンの補題

ツォルン補題

$(X,\ge)$：帰納的半順序集合.
then
$X$ は少なくとも１つの極大元をもつ.

Proof

* $f:2^X\rightarrow X$ is 選択関数.$\quad(f(A) \in A \subset X)$
* $W \subset X$ is 整列部分集合 of $X$
* $a \in W$
* $\Delta(W,a) \overset{\mathrm{def}}{=} \{x \in X | b \in W \lt a \gt \Rightarrow b \lt x\}$
(すなわち$W \lt a \gt \quad \lt \quad \Delta(W,a)$)
* $W$ is a $f$-列 $\overset{\mathrm{def}}{\Leftrightarrow}$ $\forall a \in W, f(\Delta(W,a)) = a$

then

(1)
$W$ is a $f$-列 $\Rightarrow \min(W) = f(X)$
$\because \min W \in W$ and $W$ is a $f$-列. $\therefore \min W = f(\Delta(W,\min W))$
$W \lt \min W \gt = \emptyset \therefore \Delta(W, \min W) = X$
$\therefore \min(W) = f(X)$

(2)
Let
$a_1 = f(X), a_2 = f(\{x \in X| a_1 \lt x\})$ then $\{a_1\}, \{a_1,a_2\}$ is $f$-列.
$\therefore$ $f$-列 exists.
(3)
$W_1,W_2$ are $f$-列 $\Rightarrow W_1 = W_2, W_1 \lt w_1 \gt = W_2, W_1 = W_2 \lt w_2 \gt$.
(Proof)
$W_1,W_2$ are 整列集合, $\therefore W_1 \simeq W_2, W_1 \lt w_1 \gt \simeq W_2, W_1 \simeq W_2 \lt w_2 \gt$
Let
$W_1 \simeq W_2 \lt w_2 \gt$
$\phi:W_1 \rightarrow W_2 \lt w_2 \gt$ is 順序同型射像
then
$\phi(x) = x$ を示す.
Suppose $W_1' = \{x \in W_1 | \phi(x) \neq x\}, W_1' \neq \emptyset$
then $\exists y = \min W_1'$
$W_1 \lt y \gt = W_2 \lt \phi(y) \gt$
($\because$
$x \in W_1 \lt y \gt$
then
$x \lt y \therefore \phi(x) \lt \phi(y)$
$x \lt y = \min W_1' \therefore x \notin W_1' \therefore \phi(x) = x$
$\therefore x = \phi(x) \lt \phi(y) \therefore x \in W_2 \lt \phi(y) \gt \therefore W_1 \lt y \gt \subset W_2 \lt \phi(y) \gt$
$x \in W_2 \lt \phi(y) \gt$
$x \lt \phi(y) \therefore \phi^{-1}(x) \lt y$
$y = \min W_1' \therefore \phi^{-1}(x) \notin W_1' \therefore x = \phi(\phi^{-1}(x)) = \phi^{-1}(x)$
$\therefore x \lt y \therefore x \in W_1 \lt y \gt \therefore W_1 \lt y \gt \supset W_2 \lt \phi(y) \gt$
then
$W_1 \lt y \gt = W_2 \lt \phi(y) \gt$
)

$W_1 \lt y \gt = W_2 \lt \phi(y) \gt$ leads to $\Delta(W_1, y) = \Delta(W_2, \phi(y))$
$W_1, W_2$ is a $f$-列. $\therefore y = f(\Delta(W_1, y)) = f(\Delta(W_2, \phi(y))) = \phi(y) \therefore y \notin W_1'$ contradiction
$W_1' = \emptyset, \forall x \in W_1, \phi(x) = x$

同様にして
$W_1 \simeq W_2 \Rightarrow W_1 = W_2$
$W_1 \lt w_1 \gt \simeq W_2 \Rightarrow W_1 \lt w_1 \gt = W_2$
が導ける.

(4)
Let
$\mathcal{W} = \{W|W \text{ is f-列} \}$
$W_\infty = \bigcup (W|W \in \mathcal{W})$
then
$W_\infty$ is 整列集合.
(Proof)
Let
$M \neq \emptyset, M \subset W_\infty$
$a \in M$
$W \in \mathcal{W}, a \in W$
$m = \min M \cap W$
then
$m = \min M$を示すことで$W_\infty$ is 整列集合を示す.
(Proof)
Suppose $\exists x \in M, x \lt m$.
$x \in M \subset W_\infty \therefore \exists W' \in \mathcal{W} \text{ s.t. } x \in W'$
$x \lt m, m = \min (M \cap W) \therefore x \notin W, x \in W' - W$
$\therefore \exists b \in W' \text{ s.t. } W = W'\gt b\lt (\because (3))$
$b = \min (W' - W) \because W' - W = W' - W'\lt b \gt = W' - \{x \in W'x| x \lt b\}$
$\therefore b \le x$
$m \in W \therefore m \lt b$
$\therefore m \lt b \le x$ which contradicts to $x \lt m$.

(5)
$W \in \mathcal{W} \Rightarrow W = W_\infty$ or $\exists b \in W_\infty \text{ s.t. } W = W_\infty \lt b \gt$.
(Proof)
When $W \neq W_\infty$.
$b = \min (W_\infty - W)$
$\exists W' \in \mathcal{W} \text{ s.t. } b \in W' ( \therefore b \in W' - W)$
$b \notin W \therefore \exists a \in W', W = W' \lt a \gt (\therefore a = \min (W' - W))$
$b = \min (W_\infty - W) \therefore W_\infty \lt b \gt \subset W$
$W' \subset W_\infty \therefore W' \lt b \gt \subset W_\infty \lt b \gt$
$b \in W' - W$ and $a = \min (W' - W) \therefore a \le b \therefore W' \lt a \gt \subset W' \lt b \gt$
$\therefore W_\infty \lt b \gt \subset W = W'\lt a \gt \subset W' \lt b \gt \subset W_\infty \lt b \gt$
$\therefore W = W_\infty \lt b \gt$.
$\therefore W \neq W_\infty \Rightarrow \exists b \in W_\infty \text{ s.t. } W = W_\infty \lt b \gt$

(6)
$W_\infty$ is a $f$-列.(すなわち、$W_\infty \in \mathcal{W}$)
(Proof)
Let $a \in W_\infty$ then $\exists W \in \mathcal{W} \text{ s.t. } a \in W$
because of (5), $W = W_\infty$ or $\exists b \in W_\infty \text{ s.t. } W = W_\infty \lt b \gt$
if $W = W_\infty$ then $W_\infty \lt a \gt = W \lt a \gt$
if $\exists b \in W_\infty \text{ s.t. } W = W_\infty \lt b \gt$
$a \in W = W_\infty \lt b \gt = \{x \in W_\infty| x \lt b\} \therefore a \lt b \therefore W_\infty \lt b \gt \lt a \gt = W_\infty \lt a \gt$
$\therefore W \lt a \gt = W_\infty \lt a \gt$
$\therefore \Delta(W_\infty, a) = \Delta(W,a)$
$\therefore f(\Delta(W_\infty, a)) = f(\Delta(W,a)) = a$

(7)
$(X, \le)$:帰納的半順序集合 and $W_\infty$:整列集合(全順序部分集合)
$\therefore \exists w$:上界 of $W_\infty (\because$ the definition of 帰納的半順序集合)
$w$ is a 極大元 of $X$
(Proof)
Suppose $\exists w' \in X$ s.t. $w \lt w'$
Let $\Delta_\infty = \{x \in X | a \in W_\infty \Rightarrow a \lt x\}$
$w' \in \Delta_\infty \therefore \Delta_\infty \neq \emptyset$
Let
$z = f(\Delta_\infty)$
$W_* = W_\infty \cup \{z\}$
then

$W_*$ is 整列集合.
($\because M \subset W_*$
$z \notin M$ then $M \subset W_\infty$ so $M$ has $\min M$
$z \in M$ then $\min M - \{z\} = \min M \because \forall a \in W_\infty, a \lt z$
)
$W_\infty = W_* \lt z \gt$
$\therefore \Delta(W_*,z)$
$= \{x \in X | a \in W_* \lt z \gt \Rightarrow a \lt x \}$
$= \{x \in X | x \in W_\infty \Rightarrow a \lt x \} = \Delta_\infty$

$W_*$ is f-列. すなわち $\forall a \in W_*, f(\Delta(W_*, a)) = a$
(Proof)
when $a = z$
$\Delta(W_*,a) = \Delta(W_*,z) = \Delta_\infty$
$\therefore f(\Delta(W_*, a)) = f(\Delta_\infty) = z = a$
when $a \neq z$ すなわち $a \in W_\infty \quad \because a \in W_* = W_\infty \cup \{z\}$
$\Delta(W_*,a) = \Delta(W_\infty,a)$
$\therefore f(\Delta(W_*, a)) = f(\Delta(W_\infty, a)) = a \quad (\because W_\infty \text{ is f-列})$
$\therefore W_* \in \mathcal{W}$

$\cup \mathcal{W} = W_\infty \subsetneq W_* \in \mathcal{W}$ contradict to (6).
$\therefore \nexists w' \in X \text{ s.t. } w \lt w'$ すなわち $w$は極大.