整列可能定理が unobjectionable logical principle だと感じられるだろうか。

整列可能定理

(Zermelo) どんな集合も整列集合にできる。

証明

任意の集合 $X$ をとる。ここで $X$ の部分集合 $S$ とその整列順序 $\prec_S$ の順序対 $(S, \prec_S)$ すべてからなる集合を $\mathcal X$ とする。

  • コメント：そんなものがあるかと思ったが、少なくとも $\varnothing \in \mathcal X.$ 空集合は順序集合。
  • コメント：この時点で $(X, \prec_X) \in \mathcal X$ を主張したいということを見据える。

次に $\mathcal X$ は順序集合 $(\mathcal X, \prec_{\mathcal X})$ にできることを示す。 それには順序

\[(S_1, \prec_1) \prec_{\mathcal X} (S_2, \prec_2)\]

を次で定義すればよい。

  • $S_1$ が $S_2$ の（順序 $\prec_2$ についての）切片であり、
  • かつ $S_1$ 上の順序 $\prec_1$ が $(S_2, \prec_2)$ の部分順序集合としての順序と同じである。

これにより $\prec_{\mathcal X}$ は順序の公理を満たす。

当面の目標は順序集合 $(\mathcal X, \prec_{\mathcal X})$ が帰納的順序集合であることを示すことだ。 そのためにいろいろなものを構成する。

$\mathcal C$ を $\mathcal X$ の任意の鎖とする。これに上界が存在することを示したい。

鎖 $\mathcal C$ に含まれる集合の和集合 $C$ を考える。これに適当な順序を定義して順序集合 $(C, \prec_C)$ にできることを以下に示す：

\[\tag*{$\spadesuit$} C \coloneqq \bigcup_{(S, \prec_S) \in \mathcal C}S.\]

このとき $\mathcal C$ の任意の元 $x$ について、それを含む整列集合が $\mathcal C$ にある：

\[\forall x(x \in \mathcal C \implies \exists (S_x, \prec_x)((S_x, \prec_x) \in \mathcal C \land x \in S_x).\]

$x$ のほかに $y \in \mathcal C$ をとり、対応するものを $(S_y, \prec_y) \in \mathcal C$ とする。 鎖 $\mathcal C$ は定義（＝全順序集合）であるので、$x \ne y$ ならば次のどちらか一方のみが成り立つ：

\[\def\lessx{ \prec_{\mathcal X} } (S_x, \prec_x) \lessx (S_y, \prec_y) \lor (S_y, \prec_y) \lessx (S_x, \prec_x).\]

前者が成り立つと仮定しても一般性は損なわれない。このとき $x \prec_C y$ を次で定義する：

\[x \prec_y y \implies x \prec_C y.\]

このような $(S_y, \prec_y)$ のとり方は一意的には定まらないものの、鎖 $\mathcal C$ の全順序性から $(S_y, \prec_y)$ のとり方によらず $x \prec_y y$ が定まる。

以上で順序集合 $(C, \prec_C)$ が構成できた。

順序集合 $(C, \prec_C)$ が整列集合であることを以下に示す。

空でない部分集合 $Z \subset C$ をとる（とれる）。$\spadesuit$ より次が成り立つ：

\[Z = \bigcup_{(S, \prec_S) \in \mathcal C}(S \cap Z).\]

したがって

\[\exists (S, \prec_S)((S, \prec_S) \in C \land S \cap Z \ne \varnothing).\]

整列集合の性質より最小元 $m = \min S \cap Z = \min Z$ をとれる。

以上により $Z$ は整列集合であることが示された。

  • コメント：この性質を満たす $(S, \prec_S) \in C$ の選び方に一意性はない。 しかし、もう一つ $S^\prime \cap Z \ne \varnothing$ であるような $(S^\prime, \prec_{S^\prime})$ をとって $m^\prime = \min(S^\prime \cap Z)$ としても結局 $m = m^\prime$ であることが先ほどと同様の推論で導かれる。

整列集合 $(C, \prec_C)$ が $(\mathcal X, \prec_X)$ の上界であることを示す。つまり次を示す：

\[\forall (S, \prec_S) \in \mathcal C \implies (S, \prec_S) \prec_{\mathcal X} (C, \prec_C).\]

$S = C$ ならば $\prec_C$ の構成から $\prec_C$ と $\prec_S$ は同じ順序関係である。 必然的に $(S, \prec_S) \prec_{\mathcal X} (C, \prec_C)$ であり申し分ない。

$S \ne C$ ならば $\varnothing \ne C\setminus S \subset C.$ ここで $b = \min C\setminus S$ とおくと、$S$ は $C$ における $b$ の切片に等しい。 以下それを示す。

$x \in S, y \in C, y \prec_C x$ と仮定する。$C$ の定義から：

\[\exists (S^\prime, \prec_{S^\prime})((S^\prime, \prec_{S^\prime}) \in C \land y \in S^\prime).\]

鎖の性質から $S \subset S^\prime$ または $S^\prime \subset S.$

$S \subset S^\prime$ ならば $S = s(b)$ とできる。 したがって $x \prec_{S^\prime} b.$ 一方 $x, y \in S^\prime$ であり仮定から $y \prec_S x$ である。 推移律を適用して $y \prec_{S^\prime} b$ となり $y \in s(b) = S.$ すなわち $x \in S, y \in C, y \prec_C x \implies y \in S$ が成り立つので $S$ は切片である。

  • コメント：切片の基本的な性質を利用しているとはいえ、上の部分だけ切り取って読むとわかりにくいかもしれない。

$S^\prime \subset S$ ならば $y \in S^\prime \subset S.\quad \therefore y \in S.$

以上で $S$ は $C$ の切片であることが示された。順序の構成により $\prec_S$ は $\prec_C$ の制限になっている。

以上により、整列集合 $(C, \prec_C)$ は $(\mathcal X, \prec_X)$ の上界である。

任意の整列集合に上界があるので $(\mathcal X, \prec_X)$ は帰納的順序集合である。 Zorn の補題によれば $(\mathcal X, \prec_{\mathcal X})$ には極大元が存在する。 それを $(M, \prec_M)$ とする。

以下、この極大元の台集合 $M$ が集合 $X$ と同じであることを示す。 $M \ne X$ を仮定して矛盾を導く。

集合 $X$ にあって集合 $M$ にない要素 $x$ をとる。 このとき集合 $M \cup \lbrace x \rbrace$ を考える。 この和集合に次のように順序 $\prec$ を定義する：

\[\begin{cases} a \prec b &\iff \forall a \forall b(a \in M, b \in M \implies a \prec_M b)\\ a \prec x &\iff \forall a(a \in M). \end{cases}\]

これは整列順序であり、整列集合 $(M \cup \lbrace x \rbrace, \prec)$ が得られた：

\[(M \cup \lbrace x \rbrace, \prec) \in \mathcal X.\]

これは $(M, \prec_M)$ の延長物であり、その極大性に矛盾して

\[(M, \prec_M) \prec_{\mathcal X} (M \cup \lbrace x \rbrace, \prec)\]

であることになる。したがって $M \ne X$ であってはならず $M = X$ が結論される：順序 $\prec_M$ は $X$ の整列順序である。

参考資料

  • 第 13 章 整列集合 - GAIRON-book (?): 他の章も含めてこのテキストを欲しい。
  • Well-ordering theorem - Wikipedia: 証明のスケルトンをコンパクトにまとめてある。証明の見通しになる。
  • コメント：$\prec$ と $\preceq$ を使い分ける流儀に乗り換えるべきかもしれない。 よそのテキストを読むときにけっこう混乱した。