選択公理とZornの補題
本稿においては選択公理からZornの補題を簡潔に証明する。
定義1（順序集合）
$X$ を空でない集合とする。$X$ の二項関係 $\leq$ が次を満たすとき、$\leq$ を $X$ の順序と言う。
- (反射律) 任意の $x\in X$ に対し $x\leq x$。
- (推移律) $x\leq y$ かつ $y\leq z$ なる任意の $x,y,z\in X$ に対し $x\leq z$。
- (反対称律) $x\leq y$ かつ $y\leq x$ なる任意の $x,y\in X$ に対し $x=y$。
$X$ の順序 $\leq$ がさらに次を満たすとき、$\leq$ を $X$ の全順序と言う。
- (全順序性) 任意の$x,y\in X$ に対し $x\leq y$ か $y\leq x$ が成り立つ。
$\leq$ が順序であるとき、$x\leq y$ であることを $y\geq x$ とも表す。また $x\leq y$ かつ $x\neq y$ であることを $x<y$ もしくは $y>x$ と表す。順序が定義された集合を順序集合と言う。全順序が定義された集合を全順序集合と言う。
定義2（上界、下界）
$X$ を順序集合、$E\subset X$、$E\neq \emptyset$ とする。$y\in X$ が $E$ の上界であるとは、任意の $x\in E$ に対し $x\leq y$ が成り立つことを言う。また $y\in X$ が $E$ の下界であるとは、任意の $x\in E$ に対し $y\leq x$ が成り立つことを言う。
定義3（最大元、最小元）
$X$ を順序集合、$E\subset X$、$E\neq\emptyset$ とする。$y\in E$ が $E$ の最大元であるとは、任意の $x\in E$ に対し $x\leq y$ が成り立つことを言う。また $y\in E$ が $E$ の最小元であるとは、任意の $x\in E$ に対し $y\leq x$ が成り立つことを言う。
順序の反対称律より、$E$ が最大元を持つときそれは唯一つである。最小元についても同様である。
定義4（整列順序集合）
順序集合 $X$ が整列順序集合であるとは、$X$ の任意の空でない部分集合が最小元を持つことを言う。
$X$ が整列順序集合であるとき、任意の $x,y\in X$ に対し $\{x,y\}$ は最小元を持つから、$x\leq y$ か $y\leq x$ が成り立つ。よって整列順序集合は全順序集合である。
順序集合 $X$ の部分集合は、$X$ の順序をそのまま受け継ぎ順序集合とみなす。
定義5（帰納的順序集合）
順序集合 $X$ が帰納的順序集合であるとは、任意の全順序部分集合が上界を持つことを言う。
定義6（極大元）
$X$ を順序集合とする。$\omega\in X$ が $X$ の極大元であるとは、$\omega <x$ なる $x\in X$ が存在しないことを言う。
定義7（選択公理、選択関数）
$X$ を空でない集合とする。$2^X$ を $X$ の部分集合全てからなる集合とする。関数 $$ c:2^X\backslash \{\emptyset\}\rightarrow X $$ で、任意の $E\in 2^X\backslash \{\emptyset\}$ に対し $c(E)\in E$ を満たすものを $X$ 上の選択関数と言う。任意の空でない集合 $X$ に対し $X$ 上の選択関数が存在すると言う主張を選択公理と言う。
選択公理を認めてZornの補題を証明する。
定理8（Zornの補題）
任意の帰納的順序集合は極大元を持つ。
Proof.
$X$ を帰納的順序集合とし、$c:2^X\backslash \{\emptyset\}\rightarrow X$ を選択関数とする。 任意の $E\subset X$ に対し、 $$ {\rm maj}(E):=\{y\in X: \forall x\in E, x<y\}, \quad {\rm min}(E):=\{y\in X: \forall x\in E, y<x\} $$ と定義する。ただし${\rm maj}(\emptyset)={\rm min}(\emptyset)=X$ である。 $C\subset X$ が次を満たすとき、$C$ をチェインと呼ぶこととする。
- (1) $C$ は（$X$ の順序を受け継いで）整列順序集合である。
- (2) 任意の $x\in C$ に対し $c({\rm maj}(C\cap {\rm min}\{x\}))=x$が成り立つ。
$\{c(X)\}$ は明らかにチェインであるからチェインは少なくとも一つは存在する。これから最大のチェインが存在し、その上界が $X$ の極大元であることを示す。$4$ つのステップに分ける。
ステップ1
$C_1,C_2$ がチェインであり、$C_1\backslash C_2\neq \emptyset$ ならば、$C_1\backslash C_2$ の最小元 $x_1$ に対し、 $$ C_1\cap {\rm min}\{x_1\}=C_2 $$ が成り立つ。
(ステップ1の証明)
$x_1$ は $C_1\backslash C_2$ の最小元であるから、 $$ C_1\cap {\rm min}\{x_1\}\subset C_2\quad\quad(*) $$ である。$(*)$ の $\subset $ が $=$ でないと仮定する。$C_2\backslash (C_1\cap {\rm min}\{x_1\})$ は $C_2$ の空でない部分集合であるからその最小元 $x_2$ が取れる。このとき、 $$ C_2\cap {\rm min}\{x_2\}\subset C_1\cap {\rm min}\{x_1\}\quad\quad(**) $$ である。$(**)$ の $\subset$ が $=$ でないと仮定する。$(C_1\cap {\rm min}\{x_1\})\backslash(C_2\cap {\rm min}\{x_2\})$ は $C_1$ の空でない部分集合であるからその最小元 $y$ が取れる。このとき $y<x_1$ より、 $$ C_1\cap {\rm min}\{y\}\subset C_1\cap {\rm min}\{x_1\} $$であり、$y$ が $(C_1\cap {\rm min}\{x_1\})\backslash(C_2\cap {\rm min}\{x_2\})$ の最小元であることから、 $$ C_1\cap {\rm min}\{y\}\subset C_2\cap {\rm min}\{x_2\}\quad\quad(***) $$ である。$y\in C_1\cap {\rm min}\{x_1\}\subset C_2$、$x_2\in C_2$ であり、$C_2$ は整列順序集合であるから $y<x_2$ か $x_2\leq y$ であるが、$y\notin C_2\cap {\rm min}\{x_2\}$ であるから、$x_2\leq y$ である。よって $(***)$ の逆の包含関係が成り立つ。よってチェインの条件 $(2)$ より、 $$ y=c({\rm maj}(C_1\cap {\rm min}\{y\}))=c({\rm maj}(C_2\cap {\rm min}\{x_2\}))=x_2 $$ となるが、$y\in C_1\cap {\rm min}\{x_1\}$、$x_2\notin C_1\cap {\rm min}\{x_1\}$ なので矛盾する。よって $(**)$ の $\subset $ は $=$ である。よって再びチェインの条件 $(2)$ より、 $$ x_2=c({\rm maj}(C_2\cap {\rm min}\{x_2\}))=c({\rm maj}(C_1\cap {\rm min}\{x_1\}))=x_1 $$ となるが、$x_1\in C_1\backslash C_2$、$x_2\in C_2$ なので矛盾する。よって $(*)$ の $\subset$ は $=$ である。
(ステップ1の証明終)
ステップ2
チェイン全体からなる集合を $\{C_j\}_{j\in J}$ とすると、$C=\bigcup_{j\in J} C_j$ はチェインである。
(ステップ2の証明)
まず $C$ が整列順序集合であることを示す。$E$ を $C$ の空でない部分集合とする。$E\cap C_j\neq\emptyset$ なる $j\in J$ を取り、$E\cap C_j$ の最小元を $x_0$ とする。このとき $x_0$ は $E$ の最小元であることを示す。任意の $x\in E$ を取る。$x\in C_j$ ならば $x\geq x_0$ である。 $x\notin C_j$ とする。$x\in C_i\backslash C_j$ なる $i\in J$ を取れば、ステップ1より、$C_i\backslash C_j$ の最小元 $x_i$ に対し、 $$ C_i\cap {\rm min}\{x_i\}=C_j $$ である。よって $x_0<x_i\leq x$ であるから $x_0$ は $E$ の最小元である。次に $C$ がチェインの条件 $(2)$ を満たすことを示す。任意の $x\in C$ を取る。$x\in C_j$ のとき、 $$ C\cap {\rm min}\{x\}=C_j\cap {\rm min}\{x\}\quad\quad(****) $$ が成り立つことを示そう。任意の $y\in C\cap {\rm min}\{x\}$ を取り、$y\in C_j$ であることを示せばよい。$y\notin C_j$ であると仮定する。$y\in C_i\backslash C_j$ なる $i\in J$ を取り、$C_i\backslash C_j$ の最小元を $x_i$ とすると、ステップ1より、 $$ C_i\cap {\rm min}\{x_i\}=C_j $$ である。よって $y<x<x_i\leq y$ となり矛盾する。よって $(****)$ が成り立つ。$C_j$ はチェインであるから、 $$ c({\rm maj}(C\cap {\rm min}\{x\}))=c({\rm maj}(C_j\cap {\rm min}\{x\}))=x $$ である。よって $C$ はチェインである。
(ステップ2の証明終)
ステップ3
ステップ $2$ の最大のチェイン $C$ に対し、${\rm maj}(C)=\emptyset$ である。
(ステップ3の証明)
${\rm maj}(C)\neq\emptyset$ と仮定する。$\omega=c({\rm maj}(C))\in {\rm maj}(C)$ とおき、 $\widetilde{C}=C\cup\{\omega\}$ とおく。このとき$\widetilde{C}$ は明らかに整列順序集合である。また 任意の $x\in C$ に対し、 $$ \widetilde{C}\cap {\rm min}\{x\}=C\cap {\rm min}\{x\} $$ であり、 $$ \widetilde{C}\cap {\rm min}\{\omega\}=C $$ であるから、$\widetilde{C}$ はチェインの条件 $(2)$ を満たす。$C$ は最大のチェインであるから $\widetilde{C}\subset C$ となるが、$\omega\notin C$ なので矛盾する。よって ${\rm maj}(C)=\emptyset$ である。
(ステップ3の証明終)
ステップ4
$X$ は極大元を持つ。
(ステップ4の証明)
ステップ $2$ の最大のチェイン $C$ を考える。$C$ は整列順序集合ゆえ全順序集合であるから $C$ は上界 $x\in X$ を持つ。ステップ3より ${\rm maj}(C)=\emptyset$ であるから $x<y$ なる $y\in X$ は存在しない。よって $x$ は $X$ の極大元である。
(ステップ4の証明終)
□
