Zornの補題⇔Tukeyの補題

選択公理

588

Zornの補題とTukeyの補題の同値性を示します．言うまでもないと思いますが，この二つの命題はさらに選択公理と同値です．

$(X, \leq)$ を順序集合とする．部分集合 $C \subset X$ が $\leq$ に関して全順序となるとき， $C$ は $X$ の鎖であるという．
順序集合 $(X, \leq)$ が帰納的であるとは，任意の $X$ の鎖が $X$ に上界をもつことをいう．
集合 $X$ が有限性をもつとは，「 $x \in X ⟺$ 任意の有限部分集合 $y \subset x$ に対し $y \in X$ 」が成り立つことをいう．

次は同値である．

(Zornの補題)：帰納的順序集合 $(X, \leq)$ は極大元をもつ．
(Tukeyの補題)：有限性をもつ集合 $F$ は包含関係に関して極大元をもつ．

Zorn

⟹

Tukey

$F$ を有限性をもつ集合とし，包含関係によって順序集合とみなす． $(F, \subset)$ が帰納的であることを示す． $C$ を任意の $F$ の鎖とする． $A = ⋃ C$ とおき，任意の有限部分集合 $Y = {x_{1}, \dots, x_{n}} \subset A$ をとる．任意の $1 \leq i \leq n$ に対し $x_{i} \in A_{i}$ を満たす $A_{i} \in C$ が存在するので， $C$ が全順序であることから，ある $1 \leq α \leq n$ が存在して $Y \subset A_{α} \in F$ となる．ゆえに $F$ が有限性をもつことから $Y \in F$ であり， $Y$ は任意であったから，さらに $A \in F$ である．したがって $A$ は $C$ の上界なので， $F$ は帰納的である．Zornの補題より $F$ は極大元をもつ．

Tukey

⟹

Zorn

$(X, \leq)$ を帰納的順序集合とし， $C$ を $X$ の鎖全体の集合とする． $C$ が有限性をもつことを示す． $C \in C$ ならば任意の有限部分集合 $F \subset C$ が $F \in C$ であることは明らか．逆に $C \in P (X)$ に対し，任意の有限部分集合 $F \subset C$ が $F \in C$ を満たすとする．このとき，任意の $x, y \in C$ に対し， ${x, y} \in C$ であるから $x \leq y$ または $y \leq x$ が成り立つ．ゆえに $C \in C$ となる．これで $C$ が有限性をもつことが示された．Tukeyの補題より $C$ は極大元 $C_{0} \in C$ をもつ．また， $(X, \leq)$ が帰納的であることから， $C_{0}$ は $X$ に上界 $a \in X$ をもつ．もし $a < x$ となる $x \in X$ が存在するとすると， $x \notin C_{0}$ であり $C_{0} ⊊ C_{0} \cup {x}$ は $X$ の鎖となるので $C_{0}$ の極大性に反する．ゆえに， $a$ は $X$ の極大元である．