Zornの補題⇔Tukeyの補題
Zornの補題とTukeyの補題の同値性を示します．言うまでもないと思いますが，この二つの命題はさらに選択公理と同値です．
- $(X,\leq)$を順序集合とする．部分集合$C\subset X$が$\leq$に関して全順序となるとき，$C$は$X$の鎖であるという．
- 順序集合$(X,\leq)$が帰納的であるとは，任意の$X$の鎖が$X$に上界をもつことをいう．
- 集合$X$が有限性をもつとは，「$x\in X\Longleftrightarrow$任意の有限部分集合$y\subset x$に対し$y\in X$」が成り立つことをいう．
次は同値である．
- (Zornの補題)：帰納的順序集合$(X,\leq)$は極大元をもつ．
- (Tukeyの補題)：有限性をもつ集合$\mathcal{F}$は包含関係に関して極大元をもつ．
$\mathcal{F}$を有限性をもつ集合とし，包含関係によって順序集合とみなす．$(\mathcal{F},\subset)$が帰納的であることを示す．$C$を任意の$\mathcal{F}$の鎖とする．$A=\bigcup C$とおき，任意の有限部分集合$Y=\{x_1,\cdots,x_n\}\subset A$をとる．任意の$1\leq i\leq n$に対し$x_i\in A_i$を満たす$A_i\in C$が存在するので，$C$が全順序であることから，ある$1\leq\alpha\leq n$が存在して$Y\subset A_\alpha\in\mathcal{F}$となる．ゆえに$\mathcal{F}$が有限性をもつことから$Y\in\mathcal{F}$であり，$Y$は任意であったから，さらに$A\in\mathcal{F}$である．したがって$A$は$C$の上界なので，$\mathcal{F}$は帰納的である．Zornの補題より$\mathcal{F}$は極大元をもつ．
$(X,\leq)$を帰納的順序集合とし，$\mathcal{C}$を$X$の鎖全体の集合とする．$\mathcal{C}$が有限性をもつことを示す．$C\in\mathcal{C}$ならば任意の有限部分集合$F\subset C$が$F\in\mathcal{C}$であることは明らか．逆に$C\in\mathcal{P}(X)$に対し，任意の有限部分集合$F\subset C$が$F\in\mathcal{C}$を満たすとする．このとき，任意の$x,y\in C$に対し，$\{x,y\}\in\mathcal{C}$であるから$x\leq y$または$y\leq x$が成り立つ．ゆえに$C\in\mathcal{C}$となる．これで$\mathcal{C}$が有限性をもつことが示された．Tukeyの補題より$\mathcal{C}$は極大元$C_0\in\mathcal{C}$をもつ．また，$(X,\leq)$が帰納的であることから，$C_0$は$X$に上界$a\in X$をもつ．もし$a< x$となる$x\in X$が存在するとすると，$x\notin C_0$であり$C_0\subsetneq C_0\cup\{x\}$は$X$の鎖となるので$C_0$の極大性に反する．ゆえに，$a$は$X$の極大元である．