選択公理と整列可能定理が同値であることを証明する。

\(\Rightarrow\)

集合\(X\)があり、順序数\(\lambda\)が\(\left|X\right|<\left|\lambda\right|\)を満たすようにとる。
選択公理を仮定しているので、\(X\)の空集合ではない部分集合から要素を1つ選ぶ選択関数\(f_{0}:2^{X}\setminus\emptyset\rightarrow X\)が存在する。
このとき\(X\)の要素でない\(a\notin X\)を選び\(f_{0}\left(\emptyset\right)\rightarrow a\)と定めると\(f_{0}\)を拡張して\(f:2^{X}\rightarrow X\cup\left\{ a\right\} \)とできる。
また写像\(g:\lambda\rightarrow X\)を\(g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\)とする。
ここで、ある\(\alpha,\beta<\lambda\)が存在し\(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\)と仮定する。
\(\alpha\ne\beta\)として\(\beta<\alpha\)とすると、\(g\left(\alpha\right)\ne a\)なので選択関数\(f\)の決め方より、\(a\ne g\left(\alpha\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)=f_{0}\left(X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となる。
これより、\(g\left(\alpha\right)\in X\setminus\left\{ g\left(\beta\right);\beta<\alpha\right\} \)となり、\(g\left(\alpha\right)\notin\left\{ g\left(\beta\right);\beta<\alpha\right\} \)なので\(g\left(\alpha\right)\ne g\left(\beta\right)\)となり矛盾。
従って背理法より、任意の\(\alpha,\beta<\lambda\)に対し、\(\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\land\alpha\ne\beta\right)\Leftrightarrow\lnot\left(g\left(\alpha\right)=g\left(\beta\right)\ne a\right)\lor\alpha=\beta\Leftrightarrow g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)となる。
これより、\(g\left(\alpha\right)\ne a\)のときは\(g\)は単射となる。
ここで、任意の\(\alpha<\lambda\)に対し、\(g\left(\alpha\right)\ne a\)となると仮定する。
そうすると、\(g\left(\alpha\right)=g\left(\beta\right)\ne a\rightarrow\alpha=\beta\)より、\(g:\lambda\rightarrow X\)は単射となるが、\(\left|X\right|<\left|\lambda\right|\)なので矛盾。
従って背理法より、ある\(\alpha<\lambda\)が存在し、\(g\left(\alpha\right)=a\)となる。
これより、\(\gamma=\min\left\{ \alpha<\lambda;g\left(\alpha\right)=a\right\} \)とおくと、\(a=g\left(\gamma\right)=f\left(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} \right)\)より、\(X\setminus\left\{ g\left(\beta\right);\beta<\gamma\right\} =\emptyset\)となる。
従って、\(g\)を\(\gamma\)より小さいものに制限したものを\(g\mid_{\gamma}\)と書くと\(g\mid_{\gamma}\):\(\gamma\rightarrow X\)は全射となり、また単射でもあるので、全単射となる。
故に\(X\)は整列可能となるので\(\Rightarrow\)が成り立つ。

\(\Leftarrow\)

空集合を要素に持たない集合族を\(\left\{ X_{\lambda}\right\} _{\lambda\in\Lambda}\)とする。
整列可能定理より、\(\bigcup_{\lambda\in\Lambda}X_{\lambda}\)から適当な順序\(\preceq\)を定め整列集合\(\left(\bigcup_{\lambda\in\Lambda}X_{\lambda},\preceq\right)\)を作る。
このとき、\(f:\lambda\rightarrow\bigcup_{\lambda\in\Lambda}X_{\lambda},f\left(\lambda\right)=\min\left(X_{\lambda}\right)\)とすれば\(f\)は選択関数となる。
故に選択公理を満たすので\(\Leftarrow\)は成り立つ。

-

これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。