テューキーの補題

選択公理とツォルンの補題は同値なので、ツォルンの補題とテューキーの補題が同値なのを証明する。

\(\Rightarrow\)

集合族\(\mathcal{A}\)を有限性をもち空でなく、包含関係\(\subseteq\)を順序とする半順序集合\(\left(\mathcal{A},\subseteq\right)\)とする。
このとき\(\mathcal{A}\)の任意の鎖を\(\mathcal{C}\)として\(C=\bigcup\mathcal{C}\)とおき、任意の有限部分集合\(D=\left\{ d_{1},d_{2},\cdots,d_{n}\right\} \subseteq C\)をとる。
すると、任意の\(i\in\left\{ 1,2,\cdots,n\right\} \)に対しある\(A_{i}\in\mathcal{C}\)が存在して、\(d_{i}\in A_{i}\)となる。
また、\(\mathcal{C}\)は包含関係\(\subseteq\)を順序とする全順序集合なのでその部分集合\(A_{1},A_{2},\cdots,A_{n}\)も全順序集合となり、ある\(j\in\left\{ 1,2,\cdots,n\right\} \)が存在して、\(D\subseteq A_{j}\)となる。
これより、\(A_{j}\in\mathcal{C}\)\(\subseteq\mathcal{A}\)から\(A_{j}\in\mathcal{A}\)であり、集合族\(\mathcal{A}\)は有限性をもつので\(D\subseteq A_{j}\in\mathcal{A}\)より\(D\in\mathcal{A}\)となり、\(D\)の任意性より\(C\in\mathcal{A}\)となる。
従って半順序集合\(\left(\mathcal{A},\subseteq\right)\)の任意の鎖\(\mathcal{C}\)に対して、\(C=\bigcup\mathcal{C}\)は上界となるので\(\mathcal{A}\)は帰納的となる。
故にツォルンの補題より\(\mathcal{A}\)は極大元をもつのでテューキーの補題が成り立つ。

\(\Leftarrow\)

\(\left(X,\preceq\right)\)を帰納的順序集合として\(\mathcal{C}\)を\(X\)の鎖全体の集合とすると\(\mathcal{C}\)は空集合ではない。
このとき、\(C\in\mathcal{C}\)ならば任意の有限部分集合\(A\subseteq C\)は\(A\in\mathcal{C}\)を満たす。
また、部分集合\(C\subseteq X\)に対し、任意の有限部分集合\(A\subseteq C\)が\(A\in\mathcal{C}\)を満たすならば\(A\)の任意性より、\(C\in\mathcal{C}\)となる。
これより、\(C\in\mathcal{C}\Leftrightarrow A\subseteq C\land\left|A\right|<\infty\rightarrow A\in\mathcal{C}\)となるので\(\mathcal{C}\)は有限性をもち、\(\left(\mathcal{C},\subseteq\right)\)にテューキーの補題を使うと、\(\mathcal{C}\)は極大元\(C_{0}\in\mathcal{C}\)をもつ。
また\(\left(X,\preceq\right)\)は帰納的で\(C_{0}\)は鎖なので\(C_{0}\)は\(X\)に上界\(x\in X\)をもつ。
このとき、ある\(y\in X\)が存在し、\(x\prec y\)を満たすと仮定すると、\(y\notin C_{0}\)となるので\(C_{0}\cup\left\{ y\right\} \supsetneq C_{0}\)も全順序集合\(\left(C_{0}\cup\left\{ y\right\} ,\preceq\right)\)となり\(X\)の鎖となるが\(C_{0}\)が\(\left(\mathcal{C},\subseteq\right)\)の極大元であることに矛盾。
従って、背理法より任意の\(y\in X\)に対し、\(x\prec y\)を満たさないので\(x\)は極大元となる。
すなわち、帰納的順序集合\(\left(X,\preceq\right)\)は極大元\(x\in X\)をもつ。
故にツォルンの補題が成り立つので\(\Leftarrow\)が示される。

-

これらより、\(\Rightarrow\)と\(\Leftarrow\)が示されたので\(\Leftrightarrow\)となり、ツォルンの補題とテューキーの補題が同値であることが示された。
また、選択公理とツォルンの補題は同値なので、選択公理とテューキーの補題が同値であることが示される。