選択公理

(1 ⇒ 2) $\mathcal{A}$ を空でない集合だけからなる集合とする。$I:=\mathcal{A}$、$X_A:=A$（$A\in\mathcal{A}$）とおくと $(X_A)_{A\in\mathcal{A}}$ は空でない集合の族であり、$\bigcup_{A\in\mathcal{A}}X_A=\bigcup\mathcal{A}$ である。選択公理が与える写像 $f\colon\mathcal{A}\to\bigcup\mathcal{A}$ は $f(A)\in A$ を満たすので、これが求める $g$ である。
(2 ⇒ 3) $\mathcal{A}:=\mathcal{P}(X)\setminus\{\emptyset\}$ は空でない集合だけからなる集合であり、$\bigcup\mathcal{A}\subset X$ である。2 の選択関数 $g\colon\mathcal{A}\to\bigcup\mathcal{A}\subset X$ が求めるものである。
(3 ⇒ 1) $(X_i)_{i\in I}$ を空でない集合の族とし、$X:=\bigcup_{i\in I}X_i$ とおく。3 により $g\colon\mathcal{P}(X)\setminus\{\emptyset\}\to X$（$g(A)\in A$）がとれる。各 $i\in I$ について $X_i$ は $X$ の空でない部分集合なので $X_i\in\mathcal{P}(X)\setminus\{\emptyset\}$ であり、$f(i):=g(X_i)$ と定めれば $f(i)\in X_i$ である。$f$ は $i\mapsto X_i\mapsto g(X_i)$ という写像の合成なので $\mathsf{ZF}$ の中で集合として定まり、これが族 $(X_i)_{i\in I}$ の選択関数である。
(1 ⇔ 4) 直積の定義により、$\prod_{i\in I}X_i$ の元とは族 $(X_i)_{i\in I}$ の選択関数のことである。したがって「選択関数が存在する」と「直積が空でない」は、どの族についても同じ主張である。
(1 ⇒ 5) $p\colon A\to B$ を全射とする。各 $b\in B$ に対し逆像 $p^{-1}(b):=\{a\in A\mid p(a)=b\}$ は $p$ の全射性により空でない。族 $(p^{-1}(b))_{b\in B}$ に選択公理を適用して選択関数 $f\colon B\to\bigcup_{b\in B}p^{-1}(b)=A$ をとり、$s:=f$ とおく。$s(b)\in p^{-1}(b)$ より $p(s(b))=b$、すなわち $p\circ s=\mathrm{id}_B$ である。
(5 ⇒ 1) $(X_i)_{i\in I}$ を空でない集合の族とする。分出公理により
$$ A:=\Bigl\{(i,x)\in I\times\bigcup_{j\in I}X_j\ \Big|\ x\in X_i\Bigr\} $$
は集合であり、第一成分への射影 $p\colon A\to I$、$(i,x)\mapsto i$ を考える。各 $i\in I$ に対して $X_i\neq\emptyset$ なので、ある $x\in X_i$ があり $(i,x)\in A$、$p(i,x)=i$ となる。よって $p$ は全射である（ここで使ったのは「$X_i$ が空でないなら元が存在する」という一つの $i$ ごとの事実であり、選択公理ではない）。5 により $s\colon I\to A$ で $p\circ s=\mathrm{id}_I$ となるものがある。$s(i)$ は $A$ の元なので、ある $i'$ と $x\in X_{i'}$ により $s(i)=(i',x)$ と書け、$p(s(i))=i$ より $i'=i$、よって $x\in X_i$ である。そこで $f(i):=$（$s(i)$ の第二成分）と定めると $f(i)\in X_i$ であり、$f$ は $(X_i)_{i\in I}$ の選択関数である。$\square$

$W$ を、$A\subset X$ と $A$ 上の整列順序 $R\subset A\times A$ の組 $(A,R)$ 全体の集合とする（$W$ は $\mathcal{P}(X)\times\mathcal{P}(X\times X)$ から分出公理で得られる）。各 $(A,R)\in W$ は順序数 $\operatorname{ord}(A,R)$ とただ一通りに順序同型であり、置換公理により $H:=\{\operatorname{ord}(A,R)\mid (A,R)\in W\}$ は順序数の集合である。$H$ は下に閉じている：$\alpha\in H$、$\beta<\alpha$ なら、$\alpha$ と同型な $(A,R)$ の、$\beta$ に対応する元より前の始切片を取ることで $\beta\in H$ である。順序数の集合で下に閉じたものは推移的集合なので、$H$ 自身が順序数である。そこで $\theta:=H$ とおく。順序数は自分自身の元でないので $\theta\notin H$ である。もし単射 $j\colon\theta\to X$ があれば、$A:=j[\theta]$ に $j(\beta)\,R\,j(\gamma)\iff\beta<\gamma$ で整列順序を移すと $(A,R)\in W$、$\operatorname{ord}(A,R)=\theta$ となり $\theta\in H$、矛盾である。$\square$

(2 ⇒ 1) $(X_i)_{i\in I}$ を空でない集合の族とし、$X:=\bigcup_{i\in I}X_i$ 上の整列順序 $\preceq$ をとる。各 $X_i$ は $X$ の空でない部分集合なので $\preceq$ に関する最小元 $\min_\preceq X_i$ をもつ。$f(i):=\min_\preceq X_i$ と定めれば、$f$ は $\preceq$ から一意に定まる写像であり、$f(i)\in X_i$ を満たす選択関数である。
(1 ⇒ 2) $X$ を集合とする。prop-ac-equivalent-forms の 3 により選択関数 $g\colon\mathcal{P}(X)\setminus\{\emptyset\}\to X$、$g(A)\in A$ をとる。lem-ac-hartogs により、$\theta$ から $X$ への単射が存在しない順序数 $\theta$ をとる。$X$ に属さない対象を一つ固定し $\ast$ と書く（たとえば $\ast:=X$ でよい。正則性公理により $X\notin X$）。超限再帰により、$\alpha<\theta$ に対して
$$ x_\alpha:= \begin{cases} g\bigl(X\setminus\{x_\beta\mid\beta<\alpha\}\bigr) & (X\setminus\{x_\beta\mid\beta<\alpha\}\neq\emptyset),\\ \ast & (\text{それ以外}) \end{cases} $$
と定める。$x_\alpha\neq\ast$ ならば $x_\alpha\in X\setminus\{x_\beta\mid\beta<\alpha\}$ なので、$\beta<\alpha$ かつ $x_\alpha\neq\ast$ なら $x_\beta\neq x_\alpha$ である。また $x_\beta=\ast$ かつ $\beta<\alpha$ なら、$X\subset\{x_\gamma\mid\gamma<\beta\}\subset\{x_\gamma\mid\gamma<\alpha\}$ より $x_\alpha=\ast$ である。
ある $\alpha<\theta$ で $x_\alpha=\ast$ となることを示す。そうでなければ $\alpha\mapsto x_\alpha$ は $\theta$ から $X$ への写像で、上の観察により単射となり、$\theta$ の取り方に反する。そこで $x_{\alpha_0}=\ast$ となる最小の $\alpha_0<\theta$ をとる。$\alpha_0$ の最小性により $\beta<\alpha_0$ では $x_\beta\in X$ であり、$x_{\alpha_0}=\ast$ の定義から $X\setminus\{x_\beta\mid\beta<\alpha_0\}=\emptyset$、すなわち $X=\{x_\beta\mid\beta<\alpha_0\}$ である。したがって $\beta\mapsto x_\beta$ は $\alpha_0$ から $X$ への全単射であり、$x_\beta\preceq x_\gamma\iff\beta\le\gamma$ と定めれば $\preceq$ は $X$ 上の整列順序である。$\square$

(1 ⇒ 2) 選択公理から Zorn の補題を導く証明は、記事 Zornの補題 に完全な形で置かれている（選択関数と lem-ac-hartogs に相当する順序数、超限再帰を用いる）。本記事では繰り返さない。
(2 ⇒ 1) $(X_i)_{i\in I}$ を空でない集合の族とする。部分選択関数、すなわち定義域 $\operatorname{dom}(p)\subset I$ をもつ写像 $p$ で、すべての $i\in\operatorname{dom}(p)$ に対し $p(i)\in X_i$ を満たすもの全体を $P$ とする（$P$ は $\mathcal{P}(I\times\bigcup_{i\in I}X_i)$ から分出公理で得られる集合である）。$P$ を写像のグラフの包含関係 $\subset$ で順序づける。空写像 $\emptyset$ は $P$ の元なので $P\neq\emptyset$ である。
$C\subset P$ を鎖とする。$u:=\bigcup C$ が写像であることを示す。$(i,x),(i,x')\in u$ とすると $(i,x)\in p$、$(i,x')\in p'$ となる $p,p'\in C$ があり、$C$ が鎖なので $p\subset p'$ または $p'\subset p$、いずれにせよ $(i,x),(i,x')$ は同じ写像に属するので $x=x'$ である。$u$ の定義域は $\bigcup_{p\in C}\operatorname{dom}(p)\subset I$ であり、$i\in\operatorname{dom}(p)$ なら $u(i)=p(i)\in X_i$ である。よって $u\in P$ であり、$u$ は $C$ の上界である（$C=\emptyset$ のときは $u=\emptyset\in P$ で、これも上界である）。
Zorn の補題により $P$ は極大元 $m$ をもつ。$\operatorname{dom}(m)=I$ を示す。$i_0\in I\setminus\operatorname{dom}(m)$ が存在したとすると、$X_{i_0}\neq\emptyset$ なので元 $x\in X_{i_0}$ があり（ここで使うのは一つの集合についての事実であって選択公理ではない）、$m':=m\cup\{(i_0,x)\}$ は $P$ の元で $m\subsetneq m'$ となり、$m$ の極大性に反する。よって $\operatorname{dom}(m)=I$ であり、$m$ は $(X_i)_{i\in I}$ の選択関数である。$\square$

(1 ⇒ 2) thm-ac-well-ordering により $X$ と $Y$ を整列し、それぞれと順序同型な順序数を $\alpha,\beta$ とする。順序数は比較可能なので $\alpha\le\beta$ または $\beta\le\alpha$ であり、$\alpha\le\beta$ なら $\alpha\subset\beta$ なので、$X\cong\alpha\hookrightarrow\beta\cong Y$ により $X$ から $Y$ への単射が得られる。$\beta\le\alpha$ の場合も同様である。
(2 ⇒ 1) thm-ac-well-ordering により、任意の集合 $X$ が整列可能であることを示せばよい。lem-ac-hartogs により $\theta$ から $X$ への単射が存在しない順序数 $\theta$ をとる。2 により $X$ から $\theta$ への単射 $j$ が存在する。$x\preceq y\iff j(x)\le j(y)$ と定めると、$j$ が単射なので $\preceq$ は $X$ 上の全順序であり、空でない $A\subset X$ に対し $j[A]\subset\theta$ の最小元 $j(a)$ をとれば $a$ が $A$ の $\preceq$-最小元である。よって $\preceq$ は整列順序である。$\square$

1 と 2 は Zornの補題 を、それぞれ線型独立な部分集合の全体、真のイデアル（環のイデアル）の全体（包含順序）に適用して得られる。3 は超フィルターまたは有限交差性をもつ族の極大元を Zornの補題 で取る議論による。4 は部分空間上の拡張の全体に Zornの補題 を適用する。5 は自由群の逆理的分解と prop-ac-equivalent-forms の 2 による軌道からの代表の選択を組み合わせる。6 は可算個の集合から一斉に元または全射を選ぶ箇所に可算選択公理を用いる（ex-ac-countable-choice）。いずれも本記事では証明を与えず、上に挙げた文献に委ねる。

$\mathsf{AC}\Rightarrow\mathsf{DC}$：$X$、$R$ を仮定のとおりとする。各 $x\in X$ に対し $S_x:=\{y\in X\mid x\,R\,y\}$ は空でないので、族 $(S_x)_{x\in X}$ の選択関数 $h\colon X\to X$（$x\,R\,h(x)$）をとる。$X\neq\emptyset$ なので $x_0\in X$ を一つとり、$\mathbb{N}$ 上の再帰で $x_{n+1}:=h(x_n)$ と定めれば $x_n\,R\,x_{n+1}$ である。
$\mathsf{DC}\Rightarrow\mathsf{AC}_\omega$：$(X_n)_{n\in\mathbb{N}}$ を空でない集合の族とする。$S$ を、ある $k\in\mathbb{N}$ について定義域 $\{0,\dots,k-1\}$ をもち $s(i)\in X_i$（$i< k$）を満たす有限列 $s$ の全体とする（$S$ は $\bigcup_{k}\prod_{i< k}X_i$ であり、ex-ac-finite-family により各 $\prod_{i< k}X_i$ は空でない。特に空列 $\emptyset\in S$）。$s\,R\,t$ を「$t$ は $s$ を長さ $1$ だけ延長した列である」と定める。$s\in S$ の長さを $k$ とすると $X_k\neq\emptyset$ なので $s$ を延長する $t\in S$ があり、$R$ は $\mathsf{DC}$ の仮定を満たす。$\mathsf{DC}$ により $s_n\,R\,s_{n+1}$ を満たす列 $(s_n)_{n\in\mathbb{N}}$ がとれる。$s_0$ の長さを $k_0$ とすると $s_n$ の長さは $k_0+n$ であり、$m\le n$ なら $s_m\subset s_n$ である。そこで $f(n):=s_{n+1}(n)$ と定めると、$s_{n+1}$ の長さは $k_0+n+1>n$ なのでこれは定義され、$f(n)\in X_n$ である。よって $f$ は $(X_n)_{n\in\mathbb{N}}$ の選択関数である。
$\mathsf{AC}\Rightarrow\mathsf{BPI}$ は Zornの補題 を素イデアルを含まない真のイデアルの全体に適用する標準的な議論による（Jech73 第2章）。逆向きの含意が $\mathsf{ZF}$ で証明できないことは、それぞれ選択公理の適当な弱い形だけが成り立つ $\mathsf{ZF}$ のモデルを構成して示される。証明は本記事では割愛し、Jech73 第5章・第7章・第8章、HR98 に委ねる。$\square$

この定理は Gödel による（Godel38a、Godel38b、Godel40）。証明は、$\mathsf{ZF}$ の中で構成可能宇宙 $L$ を定義し、$\mathsf{ZF}$ の任意のモデルの中で $L$ が $\mathsf{ZF}+\mathsf{AC}+\mathsf{GCH}$ のモデルになることを示すという内モデルの方法による。すなわち $\mathsf{ZF}$ は「$L$ において $\mathsf{ZF}$ の各公理と $V=L$ が成り立つ」ことと「$V=L$ ならば $\mathsf{AC}$ かつ $\mathsf{GCH}$」を証明する。現代的な記述は Jech03 第13章、Kunen11 にある。本記事はこの定理を引用のみで用い、証明は割愛する。

この定理は Cohen による（Cohen63、Cohen64、Cohen66）。Cohen の論文の題名は連続体仮説の独立性を主題とするが、同じ論文で選択公理の独立性も扱われている。証明は強制法により $\mathsf{ZF}$ のモデルを拡大し、その中で選択関数をもたない集合の族が現れる部分モデル（対称モデル）を切り出すことによる。強制法の標準的な記述は Kunen11 にあり、対称モデルによる記述は Jech73 第5章、Jech03 第14章・第15章にある。本記事はこの定理も引用のみで用い、証明は割愛する。

$\mathsf{ZF}$ が無矛盾であるとする。もし $\mathsf{ZF}$ が $\mathsf{AC}$ を証明すれば、$\mathsf{ZF}+\lnot\mathsf{AC}$ は $\mathsf{AC}$ と $\lnot\mathsf{AC}$ を共に証明して矛盾するが、これは thm-ac-cohen に反する。もし $\mathsf{ZF}$ が $\lnot\mathsf{AC}$ を証明すれば、$\mathsf{ZFC}=\mathsf{ZF}+\mathsf{AC}$ が矛盾し、thm-ac-godel に反する。$\square$