Zornの補題⇔Tukeyの補題

$\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$の極大元である．