Hausdorffの極大原理

$P$ 上の整列順序 $\sqsubseteq$ をとる（整列可能定理。$\le$ とは無関係の順序である）。$q\sqsubset p$ は「$q\sqsubseteq p$ かつ $q\ne p$」を表す。$\sqsubseteq$ に沿った再帰により、部分集合 $B_1\subset P$ を次で定める。各 $p\in P$ について
$$ D_p:=C_0\cup\{q\in B_1\mid q\sqsubset p\} $$
とおき、
$$ p\in B_1\iff D_p\cup\{p\}\text{ が鎖である} $$
とする。$p$ の採否は $p$ より $\sqsubseteq$ で前の元の採否だけから決まるので、この定義は正当である。$B:=C_0\cup B_1$ とおく。
$B$ は鎖である。 $x,y\in B$ を相異なる 2 元とする。3 つの場合に分ける。

• $x,y\in C_0$ のとき：$C_0$ が鎖なので比較可能である。
• $x\in C_0$、$y\in B_1$ のとき：$y\in B_1$ の定義により $D_y\cup\{y\}$ は鎖であり、$x\in C_0\subset D_y$ なので、$x$ と $y$ は比較可能である。
• $x,y\in B_1$ のとき：$\sqsubseteq$ は全順序なので $x\sqsubset y$ としてよい。すると $x\in D_y$ であり、$D_y\cup\{y\}$ が鎖なので $x$ と $y$ は比較可能である。

$B$ は極大鎖である。 定義の直後の言い換えにより、$B\cup\{x\}$ が鎖となる $x\in P$ が $B$ に属することを示せばよい。$D_x\subset B$ なので $D_x\cup\{x\}\subset B\cup\{x\}$ であり、鎖の部分集合は鎖なので $D_x\cup\{x\}$ は鎖である。$B_1$ の定義により $x\in B_1\subset B$ である。
$C_0\subset B$ は $B$ の定義から明らかである。$\square$

$C_0$ を $P$ の鎖とし、$C_0$ を含む $P$ の鎖全体の集合を $\mathcal Q$ とおく。$C_0\in\mathcal Q$ なので $\mathcal Q$ は空でない。$\mathcal Q$ を包含で順序づけ、極大原理により $\mathcal Q$ の極大鎖 $\mathcal K$ をとる。
$\mathcal K$ は空でない。空なら $\{C_0\}$ が $\mathcal Q$ の鎖で $\mathcal K$ を真に含むからである。$B:=\bigcup\mathcal K$ とおく。$B$ は $P$ の鎖である。実際 $x,y\in B$ なら $x\in K$、$y\in K'$ となる $K,K'\in\mathcal K$ があり、$\mathcal K$ は包含について鎖なので大きい方が $x,y$ を両方含み、それが $P$ の鎖なので $x,y$ は比較可能である。$C_0\subset B$ なので $B\in\mathcal Q$ である。$\mathcal K$ のどの元も $B$ に含まれるので、$\mathcal K\cup\{B\}$ は $\mathcal Q$ の鎖であり、$\mathcal K$ の極大性から $B\in\mathcal K$ である。
$B$ が $P$ の極大鎖であることを示す。$B\cup\{x\}$ が $P$ の鎖だとする。これは $C_0$ を含むので $\mathcal Q$ に属し、$\mathcal K$ のどの元も $B\subset B\cup\{x\}$ に含まれるので、$\mathcal K\cup\{B\cup\{x\}\}$ は $\mathcal Q$ の鎖である。$\mathcal K$ の極大性から $B\cup\{x\}\in\mathcal K$ であり、$\mathcal K$ の元は $B$ に含まれるので $B\cup\{x\}\subset B$、すなわち $x\in B$ である。定義の直後の言い換えにより、$B$ は極大鎖である。$\square$

1 ⇒ 2 は thm-hmp-main である（選択公理から整列可能定理が従うことは 選択公理 の定理「整列可能定理との同値」による）。2 ⇒ 3 は $C_0=\emptyset$ とすればよい。
3 ⇒ 1 を示す。$(X_i)_{i\in I}$ を空でない集合の族とする。$I$ の部分集合 $J$ 上で定義され、各 $i\in J$ で $f(i)\in X_i$ となる写像 $f$ を 部分選択関数 と呼び、その全体を $\mathcal F$ とする。写像を順序対の集合とみて、$\mathcal F$ を包含で順序づける。$f\subset g$ は「$g$ が $f$ の拡張である」ことである。定義域が空な写像が $\mathcal F$ に属するので、$\mathcal F$ は空でない。
極大原理により $\mathcal F$ の極大鎖 $\mathcal K$ をとり、$g:=\bigcup\mathcal K$ とおく。$\mathcal K$ の 2 元はどちらかが他方の拡張なので、$(i,x),(i,y)\in g$ なら両方を含む $\mathcal K$ の元があり、それが写像なので $x=y$ である。よって $g$ は写像で、定義域は $\mathcal K$ の元の定義域の合併 $J\subset I$ であり、$g(i)\in X_i$ を満たす。すなわち $g\in\mathcal F$ である。$\mathcal K$ のどの元も $g$ に含まれるので $\mathcal K\cup\{g\}$ は鎖であり、極大性から $g\in\mathcal K$ である。
$J\ne I$ と仮定する。$i_0\in I\setminus J$ をとり、$X_{i_0}$ は空でないので元 $x_0$ を一つとる（一つの集合から一つの元をとるだけなので選択公理は要らない）。$h:=g\cup\{(i_0,x_0)\}$ は $\mathcal F$ に属し、$\mathcal K$ のどの元も $g\subsetneq h$ に含まれる。$h\in\mathcal K$ なら $h\subset g$ となるが、$(i_0,x_0)\notin g$ なので $h\notin\mathcal K$ である。よって $\mathcal K\cup\{h\}$ は $\mathcal K$ を真に含む鎖となり、$\mathcal K$ の極大性に反する。したがって $J=I$ であり、$g$ は選択関数である。$\square$

$s:=\bigvee S$ とおき、$s$ が $C$ のどの元 $c$ とも比較可能であることを示す。$c$ が $S$ の上界なら、上限の定義により $s\le c$ である。$c$ が $S$ の上界でないなら、$x\not\le c$ となる $x\in S$ がある。$x$ と $c$ はともに $C$ の元なので比較可能であり、$x\not\le c$ から $c< x$ である。$x\le s$ なので $c< s$ である。
よって $C\cup\{s\}$ は鎖であり、$C$ の極大性から $s\in C$ である。下限については順序を逆にして同じ議論をする。$S=\emptyset$ とすると、$\bigvee\emptyset$ は $L$ の最小元、$\bigwedge\emptyset$ は最大元なので、これらが $C$ に属する。$C$ の部分集合の $L$ での上限と下限が $C$ に属するので、それは $C$ の中での上限と下限でもあり、$C$ は完備束である。$\square$

1. $\mathcal D(\preceq)$ が鎖であること：下集合 $D,E$ が比較不能なら、$y\in D\setminus E$ と $x\in E\setminus D$ がある。$\preceq$ は全順序なので $x\preceq y$ か $y\preceq x$ である。前者なら $D$ が下集合なので $x\in D$、後者なら $E$ が下集合なので $y\in E$ となり、どちらも矛盾する。
極大であること：$S\subset X$ が $\mathcal D(\preceq)$ のどの元とも比較可能だとして、$S$ が下集合であることを示す。$y\in S$、$x\preceq y$ とし、$x\notin S$ と仮定する。$S$ と ${\downarrow}x$ は比較可能で、$x\in{\downarrow}x\setminus S$ なので ${\downarrow}x\not\subset S$、したがって $S\subset{\downarrow}x$ である。すると $y\in S$ から $y\preceq x$ となり、$x\preceq y$ と反対称律から $x=y\in S$ となって矛盾する。よって $S\in\mathcal D(\preceq)$ であり、定義の直後の言い換えにより $\mathcal D(\preceq)$ は極大鎖である。
$\preceq_{\mathcal D(\preceq)}=\;\preceq$ であること：$x\preceq y$ なら、$y$ を含む下集合は $x$ も含むので $x\preceq_{\mathcal D(\preceq)}y$ である。逆に $x\preceq_{\mathcal D(\preceq)}y$ なら、$y$ を含む下集合 ${\downarrow}y$ が $x$ を含むので $x\preceq y$ である。
2. $\preceq_{\mathcal C}$ が反射的かつ推移的であることは定義から明らかである。
全順序性：$x\preceq_{\mathcal C}y$ でも $y\preceq_{\mathcal C}x$ でもないとすると、$y\in C$、$x\notin C$ となる $C\in\mathcal C$ と、$x\in C'$、$y\notin C'$ となる $C'\in\mathcal C$ がある。$C$ と $C'$ は比較可能なはずだが、$C\subset C'$ なら $y\in C'$、$C'\subset C$ なら $x\in C$ となり、どちらも矛盾する。
反対称性：$x\ne y$ で、$x\preceq_{\mathcal C}y$ かつ $y\preceq_{\mathcal C}x$ と仮定する。すなわち、$\mathcal C$ の各元は $x,y$ を両方含むか、両方含まない。$U:=\bigcup\{C\in\mathcal C\mid x\notin C\}$ とおくと、prop-hmp-complete-lattice により $U\in\mathcal C$ であり、$x\notin U$ である。$V:=U\cup\{x\}$ が $\mathcal C$ のどの元 $C$ とも比較可能であることを示す。$x\notin C$ なら $C\subset U\subset V$ である。$x\in C$ なら、$x\notin U$ なので $C\not\subset U$ であり、$C$ と $U$ は比較可能なので $U\subset C$、したがって $V\subset C$ である。$\mathcal C$ の極大性から $V\in\mathcal C$ である。$V$ は $x$ を含むので、仮定により $y$ も含み、$y\ne x$ から $y\in U$ である。すると $y\in C$、$x\notin C$ となる $C\in\mathcal C$ があり、仮定に反する。
$\mathcal D(\preceq_{\mathcal C})=\mathcal C$ であること：$C\in\mathcal C$、$y\in C$、$x\preceq_{\mathcal C}y$ なら、定義から $x\in C$ なので、$C$ は $\preceq_{\mathcal C}$ の下集合である。よって $\mathcal C\subset\mathcal D(\preceq_{\mathcal C})$ である。1 により右辺は鎖であり、$\mathcal C$ は極大鎖なので、両者は一致する。
1 と 2 から、二つの対応は互いに逆である。$\square$