選択公理とツォルンの補題は同値であることを証明する。

\(\Rightarrow\)

証明が長いので分割する。

step.1

\(\left(X,\preceq\right)\)を帰納的順序集合として、選択公理は成り立つとしているので、\(f\)を集合\(X\)の空でない部分集合から1つ選ぶ選択関数\(f:2^{X}\setminus\emptyset\rightarrow X\)とする。
\(\left(X,\preceq\right)\)の整列部分集合\(W\)の元\(a\in W\)に対し\(\Delta\left(W,a\right)=\left\{ x\in X;b\in W\left\langle a\right\rangle \rightarrow b\prec x\right\} \)とする。
整列部分集合\(W\)が任意の\(a\in W\)に対し、\(a=f\left(\Delta\left(W,a\right)\right)\)が成り立つとき\(W\)は\(f\)列であると定める。
このとき、\(W\)が\(f\)列であるならば、
\begin{align*} \min W & =f\left(\Delta\left(W,\min W\right)\right)\\ & =f\left(\left\{ x\in X;b\in W\left\langle \min W\right\rangle \rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;b\in\emptyset\rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;\top\right\} \right)\\ & =f\left(X\right) \end{align*} となるので、\(\min W=f\left(X\right)\)が成り立つ。
例として、\(a_{1}=f\left(X\right),a_{2}=f\left(\left\{ x\in X;a_{1}\prec x\right\} \right)\)とする。
このとき、\(a_{2}\in\left\{ x\in X;a_{1}\prec x\right\} \)なので\(a_{1}\prec a_{2}\)となる。
また
\begin{align*} f\left(\Delta\left(\left\{ a_{1}\right\} ,a_{1}\right)\right) & =f\left(\left\{ x\in X;b\in\left\{ a_{1}\right\} \left\langle a_{1}\right\rangle \rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;b\in\emptyset\rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;\top\right\} \right)\\ & =f\left(X\right)\\ & =a_{1} \end{align*} \begin{align*} f\left(\Delta\left(\left\{ a_{1},a_{2}\right\} ,a_{1}\right)\right) & =f\left(\left\{ x\in X;b\in\left\{ a_{1},a_{2}\right\} \left\langle a_{1}\right\rangle \rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;b\in\emptyset\rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;\top\right\} \right)\\ & =f\left(X\right)\\ & =a_{1} \end{align*} \begin{align*} f\left(\Delta\left(\left\{ a_{1},a_{2}\right\} ,a_{2}\right)\right) & =f\left(\left\{ x\in X;b\in\left\{ a_{1},a_{2}\right\} \left\langle a_{2}\right\rangle \rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ x\in X;b\in\left\{ a_{1}\right\} \rightarrow b\prec x\right\} \right)\\ & =f\left(\left\{ a_{2}\right\} \right)\\ & =a_{2} \end{align*} となるので、\(\left\{ a_{1}\right\} ,\left\{ a_{1},a_{2}\right\} \)は共に\(f\)列となる。

step.2

\(W_{1},W_{2}\)が\(f\)列であるとする。
このとき、整列順序の比較定理より、\(W_{1},W_{2}\)は順序同型であるか、一方ともう一方の切片が順序同型である。
\(W_{1},W_{2}\left\langle a\right\rangle \)が順序同型であるとすると順序同型写像\(\phi:W_{1}\rightarrow W_{2}\left\langle a\right\rangle \)が存在する。
ここで背理法を使うため\(A=\left\{ x\in W_{1};\phi\left(x\right)\ne x\right\} \)とおき、\(A\ne\phi\)と仮定する。
\(A\ne\phi\)で整列集合の部分集合\(A\subseteq W_{1}\)なので\(\min A\)が存在する。
\(x\in W_{1}\left\langle \min A\right\rangle \)では\(\phi\left(x\right)=x\)が成り立ち、順序同型なので\(x\prec\min A\leftrightarrow x\preceq\min A\land x\ne\min A\leftrightarrow\phi\left(x\right)\preceq\phi\left(\min A\right)\land\phi\left(x\right)\ne\phi\left(\min A\right)\leftrightarrow x=\phi\left(x\right)\prec\phi\left(\min A\right)\)となり、\(W_{1}\left\langle \min A\right\rangle =W_{2}\left\langle \phi\left(\min A\right)\right\rangle \)が成り立つ。
このとき、\(\Delta\left(W_{1},\min A\right)=\Delta\left(W_{2},\phi\left(\min A\right)\right)\)となり、\(W_{1},W_{2}\)は\(f\)列であるので、\(\min A=\Delta\left(W_{1},\min A\right)=\Delta\left(W_{2},\phi\left(\min A\right)\right)=\phi\left(\min A\right)\)となる。
しかし、\(\min A\in A\)であるが、\(A\)の定め方より、\(\min A\notin A\)となるので矛盾。
従って、背理法より、\(A=\phi\)となり、任意の\(x\in W_{1}\)に対し、\(\phi\left(x\right)=x\)となる。
故に\(W_{1},W_{2}\left\langle a\right\rangle \)が順序同型であるならば\(W_{1}=W_{2}\left\langle a\right\rangle \)となる。
同様に\(W_{1}\left\langle a\right\rangle ,W_{2}\)が順序同型であるならば\(W_{1}\left\langle a\right\rangle =W_{2}\)となり、\(W_{1},W_{2}\)が順序同型であるならば\(W_{1}=W_{2}\)となる。

step.3

\(f\)列全体を\(\mathcal{W}\)をして\(W_{\infty}:=\bigcup\mathcal{W}=\bigcup_{W\in\mathcal{W}}W\)とする。
\(W_{\infty}\)の空でない部分集合\(M\subseteq W_{\infty}\)の元を\(a\in M\)として、元\(a\)を含む\(f\)列の1つを\(W_{a}\)とする。
このとき、ある元\(x\in M\)が存在し、\(x\prec\min\left(M\cap W_{a}\right)\)と仮定する。
すると、ある\(f\)列\(W_{x}\)が存在し\(x\)を要素にもつ。
また、\(x\in M\)なので\(x\notin W_{a}\)となり、\(x\in W_{x}\setminus W_{a}\)となる。
このとき、step.2より、ある\(b\in W_{x}\)が存在し、\(W_{a}=W_{x}\left\langle b\right\rangle \)を満たす。
これより、\(\min\left(W_{x}\setminus W_{a}\right)=\min\left(W_{x}\setminus W_{x}\left\langle b\right\rangle \right)=b\)なので、\(b\preceq x\)となり、\(\min\left(M\cap W_{a}\right)\in W_{a}=W_{x}\left\langle b\right\rangle \)なので\(\min\left(M\cap W_{a}\right)\prec b\)となる。
従って、\(\min\left(M\cap W_{a}\right)\prec b\preceq x\)となり、仮定\(x<\min\left(M\cap W_{a}\right)\)に矛盾する。
故に背理法より、任意の\(x\in M\)に対し、\(\min\left(M\cap W_{a}\right)\preceq x\)が成り立つ。
これより、\(\min\left(M\cap W_{a}\right)\preceq\min\left(M\right)\)が成り立ち、一般的に\(\min\left(M\cap W_{a}\right)\succeq\min\left(M\right)\)なので、\(\min\left(M\cap W_{a}\right)=\min\left(M\right)\)となる。
故に\(W_{\infty}\)の空でない部分集合\(M\subseteq W_{\infty}\)は最小元\(\min\left(M\right)\)をもつので、\(W_{\infty}\)は整列集合となる。

step.4

\(f\)列\(W\)が\(W\ne W_{\infty}\)として、\(\min\left(W_{\infty}\setminus W\right)\)を含む\(f\)列の1つを\(W'\)とすると、\(\min\left(W_{\infty}\setminus W\right)\in W'\)となる。
このとき、\(\min\left(W_{\infty}\setminus W\right)\notin W\)なのでstep.2からある元\(a\in W'\)が存在し、\(W=W'\left\langle a\right\rangle \)となる。
また、\(\min\left(W'\setminus W\right)=\min\left(W'\setminus W'\left\langle a\right\rangle \right)=a\)となり、\(\min\left(W_{\infty}\setminus W\right)\in W'\)かつ\(\min\left(W_{\infty}\setminus W\right)\notin W\)なので\(\min\left(W_{\infty}\setminus W\right)\in W'\)\(\setminus W\)より、\(a=\min\left(W'\setminus W\right)\leq\min\left(W_{\infty}\setminus W\right)\)となる。
これらより、
\begin{align*} W_{\infty}\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle & \subseteq W\\ & =W'\left\langle a\right\rangle \\ & \subseteq W'\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle \\ & \subseteq W_{\infty}\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle \end{align*} となるので\(W=W_{\infty}\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle \)となる。
従って、\(W\ne W_{\infty}\)のとき、\(W=W_{\infty}\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle \)となる。
故に、\(W=W_{\infty}\)または\(W=W_{\infty}\left\langle \min\left(W_{\infty}\setminus W\right)\right\rangle \)となる。

step.5

任意の元\(a\in W_{\infty}\)に対し、\(a\)を含む\(f\)列の1つを\(W_{a}\)とする。
このときstep.4より、\(W_{a}\left\langle a\right\rangle =W_{\infty}\left\langle a\right\rangle \)となるので\(\Delta\left(W_{a},a\right)=\Delta\left(W_{\infty},a\right)\)となり、\(W_{a}\)は\(f\)列なので\(a=f\left(\Delta\left(W_{a},a\right)\right)=f\left(\Delta\left(W_{\infty},a\right)\right)\)となる。
これより、\(W_{\infty}\)も\(f\)列となる。
また、\(W_{\infty}=\bigcup\mathcal{W}=\bigcup_{W\in\mathcal{W}}W\)なので\(W_{\infty}\)は最大の\(f\)列となる。

step.6

\(\left(X,\leq\right)\)は帰納的順序集合で\(W_{\infty}\)は全順序部分集合なので\(W_{\infty}\)は上界をもち、その上界の1つを\(w\)とする。
ここである元\(w'\in X\)が存在し\(w<w'\)となると仮定する。
このとき、\(\Delta_{\infty}:=\left\{ x\in X;a\in W_{\infty}\rightarrow a\prec x\right\} \)と定めると、\(w'\in\Delta_{\infty}\)なので\(\Delta_{\infty}\ne\emptyset\)となり\(f\left(\Delta_{\infty}\right)\)となる元が存在する。
また、\(W_{*}:=W_{\infty}\cup\left\{ f\left(\Delta_{\infty}\right)\right\} \)も整列集合となり\(W_{*}\left\langle f\left(\Delta_{\infty}\right)\right\rangle =\left(W_{\infty}\cup\left\{ f\left(\Delta_{\infty}\right)\right\} \right)\left\langle f\left(\Delta_{\infty}\right)\right\rangle =W_{\infty}\)であるので、\(\Delta_{\infty}=\Delta\left(W_{*},f\left(\Delta_{\infty}\right)\right)\)となるので\(f\left(\Delta_{\infty}\right)=f\left(\Delta\left(W_{*},f\left(\Delta_{\infty}\right)\right)\right)\)となる。
これより、\(W_{*}\)は\(f\)列となり\(W_{\infty}\subsetneq W_{\infty}\cup\left\{ f\left(\Delta_{\infty}\right)\right\} =W_{*}\)なのでstep.5より、\(W_{\infty}\)は最大の\(f\)列であることに矛盾。
従って背理法より、任意の元\(w'\in X\)に対し、\(w<w'\)とならないので、\(w\)は極大元となる。

\(\Leftarrow\)

空集合を元に持たない集合族\(\left\{ X_{\lambda}\right\} _{\lambda\in\Lambda}\)があり、写像を要素とする集合\(A=\left\{ g:\Sigma\rightarrow\bigcup_{\lambda\in\Lambda}X_{\lambda};\Sigma\subseteq\Lambda,\forall\lambda\in\Sigma,g\left(\lambda\right)\in X_{\lambda}\right\} \)の順序を包含関係\(\subseteq\)とする。
このとき部分集合\(B\subseteq A\)が全順序集合であるとき、\(\bigcup_{g\in B}g\in A\)は\(B\)の上界となる。
これより、\(A\)に対しツォルンの補題が使え、極大元\(f\in A\)を持つ。
このとき、始域を\(\dom\left(f\right)\ne\Lambda\)と仮定すると、\(f\)が極大であることに矛盾するので背理法より\(\dom\left(f\right)=\Lambda\)となり\(f:\Lambda\rightarrow\bigcup_{\lambda\in\Lambda}X_{\lambda},\lambda\mapsto f\left(\lambda\right)\in X_{\lambda},\)となる。
従って\(f\)は選択関数になるので選択公理となる。

-

これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので選択公理とツォルンの補題は同値である。
すなわち、選択公理が成り立つならばツォルンの補題が成り立つ。

逆は一般的に成り立たない

反例で示す。
全体集合を\(X=\left[0,1\right)^{2}\cup\left(1,1\right)\)として順序を\(\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right)\in X\)として\(\left(a_{1},b_{1}\right)\preceq\left(a_{2},b_{2}\right)\overset{\Def}{\Leftrightarrow}a_{1}=a_{2}\land b_{1}\leq b_{2}\)と定める。
このとき、\(\left(1,1\right)\in X\)は極大元となる。
しかし、\(\left(X,\preceq\right)\)は半順序集合であるが、全順序部分集合\(\left\{ \left(0,b\right);b\in\left[0,1\right)\right\} \)は\(X\)での上界をもたないので帰納的順序集合ではない。
従って、極大元をもつが帰納的順序集合ではない。
故に逆は一般的に成り立たない。