整列可能定理

以下の定理が知られています。

[ツェルメロの整列可能性定理] 　任意の集合$E$上に整列順序が存在する。

以下に証明を述べますが,

$X$が有限集合か,自然数の集合${\bf N}$との間に双射が存在するなら整列順序を入れることは 難しくありません。実際,双射

$$k: x \in E \mapsto \tau (n) \in {\bf N}$$

があれば,$E$の順序を

$$x \le y \stackrel{def}{\Leftrightarrow} k(x) \le k(y)~(x ,y \in E)$$

で定義すればこの順序関係は整列順序になります。ただし,この資料では,第5章で集合の 基数を定義して,それによって始めて自然数が定義されます。

${\bf N}$との間に双射が存在しなくても,順序を定義する方法の,アイデアの一つは,次のようなものです。

まず,$x \in E$を一つ取り出し,これを定義したい順序で,最初の要素とします。 次に $E \setminus \{x\}$から要素$y \in X$を取り出し,これを$x$の次の要素とします。さらに $E \setminus \{x,y\}$から要素$z \in X$を取り出し,これを$y$の次の要素とします。無論は$E$は無限集合で,しかも,${\bf N}$との間に双射が定義されず,１番目,２番目,…,と要素の選択を「数学的帰納法」で定義できないかもしれません。

そこで,任意の$E$部分集合$Y \subseteq X$に対して,

$$\tau(Y) \in E \setminus Y$$

となるような写像$\tau$を作ります。このような写像は,$E$のべき集合

$${\cal B}(E)=\{Y\vert Y \subseteq E\}$$

を使って造られる集合の族,

$$\begin{eqnarray*} &&({\cal P}_Y), Y \in {\cal C} \\ &&{\cal P}_{Y}=E \setminus Y \\ &&{\cal C}={\cal B}(E) \setminus \{E \} \end{eqnarray*}$$

の多重直積

$$\prod (Y \in {\cal C}) {\cal P_Y} =\{f\vert f:Y \in {\cal ... ...cal P}_Y, (\forall Y \in {\cal C})(f(Y) \in {\cal P}_Y) \}$$

の元$\tau$を使います。この集合が空集合でないことは,

$$Y \in {\cal C}={\cal B}(E) \setminus \{E \}, ~~ {\cal P}_Y=E \setminus Y \ne \phi)$$

ですので選択公理によって保証されます。

$$\tau(Y), Y \subseteq E, Y \ne E$$

の直感的な意味は,$Y$の全ての要素により(順序$R$について)真に大きい要素で,しかもそのような要素の中では,一番小さい要素です。 結局

$$\tau([\leftarrow,x))=x$$

を使って,順序が定義される区間を漸次拡張する方法を使うことになりますが,
$x \le y$のとき $[\leftarrow,x)$と $[\leftarrow,x)$ に定義された順序が矛盾の無いように定義していく必要があります。

[ツェルメロの定理の証明]

上に述べたように,

$$\begin{eqnarray*} &&({\cal P}_Y), Y \in {\cal C} \\ &&{\cal P}_{Y}=E \setminus Y \\ &&{\cal C}={\cal B}(E) \setminus \{E \} \end{eqnarray*}$$

とすると

$$Y \in {\cal C}={\cal B}(E) \setminus \{E \}, ~~ {\cal P}_Y=E \setminus Y \ne \phi)$$

であり,選択公理によって その多重直積

$$\prod_ (Y \in {\cal C}) {\cal P_Y} =\{f\vert f:Y \in {\cal... ...cal P}_Y, (\forall Y \in {\cal C})(f(Y) \in {\cal P}_Y) \}$$

は空集合ではない。この集合の元の一つを$\tau$とすると,

$$(\forall Y \in {\cal C})(\tau(Y) \in E \setminus Y)$$

ここで,以下の補題を使えば

$$(\exists F:F \subseteq E )(F \ne {\cal C} \} ~and~ Fは整列順序集合)$$

が成立ち,

$${\cal C}={\cal B}(E) \setminus \{E \}$$

だったので,

$$F =E$$

です。 [ツェルメロの定理の証明終]

[補題]

$$\begin{eqnarray*} &&{\cal C} \subseteq {\cal B}(E) \\ &&\tau : {\cal C} \righ... ...w E \\ && (\forall Y \in {\cal C})(\tau(Y) \in E \setminus Y) \end{eqnarray*}$$

このとき

$$\begin{eqnarray*} &&(\exists F:F \subseteq E)(\exists R:R \subseteq F \times F ... ...e_R x \} \\ &&で, 順序z \le_R xはRで定義される。((z,x) \in R) \end{eqnarray*}$$

[補題の証明]

$$\begin{eqnarray*} &&{\cal K} =\{ S \vert S \in E \times E ~and~ Sはdom(S)=\{x\v... ...e_S x \} \\ &&で, 順序z \le_S xはSで定義される。((z,x) \in S) \end{eqnarray*}$$

とおく。

ここで,

$$\begin{eqnarray*} &&W=\{x \in S \bigcap T \vert(\leftarrow,x)_S=(\leftarrow,x)_... ...ow,x)_S =T \bigcap (\leftarrow,x)_T \times (\leftarrow,x)_T \} \end{eqnarray*}$$

とおくと：

$x \in W,y \in dom(T)$を任意にとり,$y \le_T x$とすると$t \in W$ よって

$$(\forall x \in W)(\forall y \in dom(T)) (y \le_T x \Rightarrow y \in W)$$

$x \in W,y \in dom(S)$を任意にとり,$y \le_S x$とすると$t \in W$ よって

$$(\forall x \in W)(\forall y \in dom(S)) (y \le_S x \Rightarrow y \in W)$$

また$W$の構成法から

$$T \bigcap W \times W = S \bigcap W \times W$$

$W \ne dom(S)$かつ$W \ne dom(T)$とすると

$$x_s=\min \{ S \setminus W \},x_T=\min \{ T \setminus W \}$$

とおくと,

$$W=(\leftarrow,x_S)_S,~~W=(\leftarrow,x_T)_T$$

しかし, $S \in {\cal K}$から　

$$(\leftarrow,x_S)_S \in {\cal C},\tau((\leftarrow,x_S)_S)=x_S$$

同様に, $T \in {\cal K}$から　

$$(\leftarrow,x_T)_T \in {\cal C},\tau((\leftarrow,x_T)_T)=x_T$$

よって

$$x_T=\tau((\leftarrow,x_T)_T)=\tau(W)=\tau((\leftarrow,x_S)_S)=x_S$$

ゆえに$W$の定義から

$$x_T=x_S \in W$$

これは

$$x_s=\min \{ S \setminus W \},x_T=\min \{ T \setminus W \}$$

に矛盾。

以上から

任意の $S,T \in {\cal K}$について

$$dom(S) \subseteq dom(T) ~or~ dom(T) \subseteq dom(S) \\$$

で

$$\begin{eqnarray*} && dom(S) \subseteq dom(T) \\ &&\Rightarrow S=T \bigcap dom... ...S))(\forall y \in dom(T)) (y \le_T x \Rightarrow y \in dom(S)) \end{eqnarray*}$$

ここで,

$$\begin{eqnarray*} && F=\bigcup_{S \in {\cal K}} dom(S) \\ && R=\bigcup_{S \in {\cal K}} S \end{eqnarray*}$$

とおくと：

$$R \subseteq F \times F, dom(R)=\bigcup_{S \in {\cal K}} S=F$$

任意の$x \in F$について,

$$(\exists S \in {\cal K})(x \in S)$$

$R$の作り方から

$$(x,x) \in \bigcup_{S \in {\cal K}} S~F$$

$$(x,y),(y,z) \in R$$

とすると, $S,T \in {\cal K}$が存在して

$$(x,y)\in S, (y,z)\in T$$

が成立ち, $S \subseteq T ~or~ T \subseteq S$ から

$$(x,y), (y,z)\in T ~or~(x,y), (y,z)\in S$$

従って,

$$(x,z)\in T ~or~(x,z)\in S$$

どちらの場合でも

$$(x,z)\in R$$

$$(x,y),(y,x) \in R$$

とすると,上と全く同様に $S,T \in {\cal K}$が存在して

$$(x,y),(y,x)\in T ~or~(x,y),(y,x)\in S$$

どちらの場合でも

$$x=y$$

任意の$x,y \in F$について, $S,T \in {\cal K}$が存在して

$$x \in S ~or~y \in T$$

これについても $S \subseteq T ~or~ T \subseteq S$ から

$$x,y \in S ~or~ x,y \in T$$

$S,T \in {\cal K}$は整列順序ゆえ全順序でもあるので

$$(x,y) \in S ~or~ (y,x) \in S$$

または

$$(x,y) \in T ~or~ (y,x) \in T$$

どちらにしても,

$$(x,y) \in R ~or~ (y,x) \in R$$

結局,$R$は$F$上の全順序になる。

$$D \subseteq F$$

を任意にとると： $S \in {\cal K}$が存在して

$$dom(S) \bigcap D \ne \phi )$$

$dom(S)$は整列集合で,

$$dom(S) \bigcap D \subseteq S, dom(S) \bigcap D \ne \phi$$

から, $dom(S) \bigcap D$には最小元 $d \in dom(S) \bigcap D$が存在する。

ここで,任意の $x \in D$ について $T \in {\cal K}$が存在して

$$x \in dom(T) \bigcap D$$

で, $S \subseteq T ~or~ T \subseteq S$ から

$T \subseteq S$ のときは

$$x \in dom(T) \bigcap D \subseteq dom(S) \bigcap D$$

より,$d$は $dom(S) \bigcap D$の$S$による最小元なので,

$$(d,x) \in S ~i.e.~ d \le_S x$$

これから

$$(d,x) \in R ~i.e.~ d \le_R x$$

$S \subseteq T$ のときは

$$(\forall x \in dom(S))(\forall y \in dom(T)) (x \le_T y \Rightarrow y \in dom(S))$$

従って,

$$x \le_T d, x \ne d$$

とすると,

$$x \in dom(S) ,x \in D$$

しかし,これは$d$は $dom(S) \bigcap D$の$S$による最小元であることに矛盾
$T$は全順序だったので

$$d \le_T x$$

これから

$$d \le_R x$$

結局, ここで,任意の $x \in D$ について

$$d \le_R x$$

以上から,$R$は$F$上の整列順序になっている。

ここで, $F \in {\cal C}$とすると,$\tau$についての仮定から

$$a=\tau(F) \notin F$$

であり,

$$\begin{eqnarray*} &&F'=F \bigcup \{a \} \\ &&R'=R \bigcup \bigcup_{x \in F} \{ (x,a)\} \end{eqnarray*}$$

とおけば, 構成の仕方から,

$$F' \ne F ~and~ R' \ne R$$

にも関わらず,

$$R' \in {\cal K}$$

でこれは

$$\begin{eqnarray*} && F=\bigcup_{S \in {\cal K}} dom(S) \\ && R=\bigcup_{S \in {\cal K}} S \end{eqnarray*}$$

に矛盾する。 [補題の証明終]