読者です 読者をやめる 読者になる 読者になる

ぱいおつ日記

ぱいおつは終わりました。

整列可能定理

ひかるさんのアドベントカレンダー企画の3日目の記事です.

www.adventar.org

 

 

 

このあいだの記事で整列集合のことを少し書きました.

paiotunoowari.hatenadiary.jp

 

$\mathbb{N}$は普通の大小関係で整列集合になってます.

$\mathbb{Z}$とかも普通の大小関係は整列順序じゃないけど$0<-1<1<-2<2<...<-n<n<...$と並べ直したら整列集合になってます.

 

こんなふうに,ある順序で整列集合でないような集合でも別の順序では整列集合になっていたりします.

 

有名ですが,じつは,どんな集合にも整列順序が入れられるというのは選択公理と同値です.

つまり,次の2つが同値です.

 

選択公理

任意の集合族$\{X_{\alpha}|\alpha\in A\}$に対して,各$\alpha\in A$で$\varphi(\alpha)\in X_{\alpha}$となる写像$\varphi\colon A\to\underset{\alpha\in A}{\cup}X_{\alpha}$(選択関数)が存在する.

 

整列可能定理

任意の集合はある順序で整列集合になる.

 

じゃあ,証明していきます.

 

 

(選択公理⇒整列可能定理の証明)

任意の集合$X$を考える.

$\varphi\colon 2^X\colon X$を選択関数とする.つまり,各$Y\subseteq X$で$\varphi(Y)\in Y$とする.

 

$X$の各部分集合$Y$に関する次の2つの性質を合わせてPと呼ぶことにする.

(P1)$Y$は整列順序を入れられる.

(P2)任意の$y\in Y$で$y=\varphi(X-Y<y>)$である.

 

性質Pをみたす集合全体を$A$で添え字づけて$\{Y_{\alpha}|\alpha\in A\}$としておく.

また,$Y\colon=\underset{\alpha\in A}{\cup}Y_{\alpha}$とする.

 

 

次の3つのステップに分けて証明を進めていきます.

 

ステップ1

各$\alpha,\beta\in A$について次のいずれかひとつが成り立ち,成り立つのはひとつだけである.

(ア)$Y_{\alpha}=Y_{\beta}$.

(イ)$Y_{\alpha}<a>=Y_{\beta}(\exists a\in Y_{\alpha})$.

(ウ) $Y_{alpha}=Y_{\beta}<b>(\exists b\in Y_{\beta})$.

 

ステップ2

$Y$は性質Pをみたす.

 

ステップ3

じつは$Y=X$である.

 

 

じゃあ順番に示していきます.

 

(ステップ1)

各$\alpha,\beta\in A$で$Y_{\alpha},Y_{\beta}$は整列集合なので,前の記事で書いた比較定理より次のいずれかが成り立ち,成り立つのはひとつだけである.

(あ)$Y_{\alpha}\cong Y_{\beta}$

(い)$Y_{\alpha}<a>\cong Y_{\beta}(\exists a\in Y_{\alpha})$

(う)$Y_{\alpha}\cong Y_{\beta}<b>(\exists b\in Y_{\beta})$

この(あ),(い),(う)に対応してそれぞれ(ア),(イ),(ウ)が成り立つ.

 

(あ)が成り立つときを見てみる.

順序同型写像$f\colon Y_{\alpha}\to Y_{\beta}$を任意にとる.

すると,じつは$f$は恒等写像となるのでそれを背理法で示す.

$f$が恒等写像でないと仮定する.

つまり,$S\colon=\{y\in Y_{\alpha}|f(y)\neq y\}$として$S\neq\emptyset$と仮定する.

すると,$Y_{\alpha}$の性質(P1)より$S$は$\leq_{Y_{\alpha}}$での最小元$m $を持つ.

このときじつは$Y_{\alpha}<m>=Y_{\beta}<f(m)>$となる.

実際,$y\in Y_{\alpha}<m>$を任意にとると$y<_{Y_{\alpha}}m $より$y=f(y),f(y)<_{Y_{\beta}}$となり$y<_{Y_{\beta}}f(m)$となるので$y\in Y_{\beta}<f(m)>$となり$Y_{\alpha}<m>\subseteq Y_{\beta}<f(m)>$となるし,逆に$Y_{\beta}<f(m)>\subseteq Y_{\alpha}<m>$も同様に成り立つ.

よって,$m $について$Y_{\alpha},Y_{\beta}$の性質(P2)より,$m=\varphi(X-Y_{alpha}<m>)=\varphi(X-Y_{\beta}<f(m)>)=f(m)$となる.

ところがこれは$m\in S$つまり$f(m)\neq m$に反する.

よって$f$は恒等写像となり,$Y_{\alpha}=Y_{\beta}$となる.

 

(い)から(イ),(う)から(ウ)も同様に分かる.

 

 

(ステップ2)

まず,$Y$にいれる順序を決める.

$y,z\in Y$を任意にとると,ステップ1より,ある$\alpha\in A$で$y,z\in Y_{\alpha}$となる.

そこで,そのような$\alpha$を$\alpha(y,z)$と書くことにする.

そして,$Y$の順序を,各$y,z\in Y$について$y\leq_{Y}z\overset{def}{\Leftrightarrow}y<_{Y_{\alpha(y,z)}}z$で定める.

 

次は,この順序で$Y$が(P1)をみたすことを見ていく.

空でない任意の$Z\subseteq Y$を考える.

$Z$が$\leq_{Y}$で最小元を持つことを示せばいい.

$z\in Z$を任意にとる.

すると,ある$\alpha\in A$で$z\in Y_{\alpha}$となる.

この$\alpha$で$Z_{\alpha}\colon=Z\cap Y_{alpha}$とする.

$Y_{\alpha}$の性質(P1)より$Z_{\alpha}$は$\leq_{Y_{\alpha}}$での最小元$m $をもつ.

じつはこの$m $は$Z$の$\leq_{Y}$における最小元となるので,それを背理法で示す.

 

$m $が$Z$の$\leq_Y$における最小元でないと仮定する.

すると,ある$x\in Z$で$x<m $となる.

この$x$は,$Y_{\alpha}$の元でない.

実際,$x\in Y_{\alpha}$とすると$x\in Z_{\alpha}$となるがこれは$x<_{Y}m $に矛盾してしまう.

よって,ある$\beta\in A,Y_{\alpha}\neq Y_{\beta}$で$x\in Y_{\beta}$となる.

このとき,ステップ1の結果より,ある$b\in Y_{\beta}$で$Y_{\alpha}=Y_{\beta}<b>$となる.

すると,$m\in Z_{\alpha}\subseteq Y_{\alpha}=Y_{\beta}<b>$より$m<_{Y_{\beta}}b$である.

また,$x\in Y_{\beta},x\notin Y_{\alpha}=Y_{\beta}<b>$より,$b\leq_{Y_{\beta}}x$である.

したがって$m<_{Y_{\beta}}b\leq_{Y_{\beta}}x$となるが,これは$x\leq_{Y}m $に反する.

ゆえに仮定は誤りで,$m $は$Z$の$\leq_{Y}$における最小元である.

 

よって$Y$は整列集合となる.

 

最後に,$Y$が性質(P2)をみたすことを確認する.

任意の$y\in Y$を考える.

すると,ある$\alpha\in A$で$y\in Y_{\alpha}$である.

このとき,じつは$Y_{\alpha}<y>=Y<y>$となるので,それを示す.

.

まず,$Y_{\alpha}<y>\subseteq Y<y>$はいい.($Y_{\alpha}\subseteq Y$だから.)

逆に$Y<y>\subseteq Y_{\alpha}<y>$を示す.

そのためには,$Y<y>\subseteq Y_{\alpha}$を示せば十分であるので,これを背理法で示す.

つまり,$Y<y>\nsubseteq Y_{\alpha}$と仮定する.

すると,$x\in Y<y>-Y_{\alpha}$がとれる.

このとき,ある$\beta\in A,Y_{\alpha}\neq Y_{\beta}$で$x\in Y_{\beta}$となる.

この$\beta$について,ステップ1の結果より,ある$b\in Y_{\beta}$で$Y_{\alpha}=Y_{\beta}<b>$となる.

この$b$について,$x<_{Y_{\beta}}b$または$b\leq_{Y_{\beta}}x$である.

$x<_{Y_{\beta}}b$のときは,$x\in Y_{\beta}<b>=Y_{\alpha}$となって$x\notin Y_{\alpha}$に矛盾する.

$b\leq_{Y_{\alpha}}x$のときは,$y\in Y_{\alpha}=Y_{\beta}<b>$より$y<_{Y_{\beta}}b\leq_{Y_{\beta}}x$となるがこれは$x\in Y<y>$に矛盾する.

よって仮定は誤りで,$Y<y>\subseteq Y_{\alpha}$となる.

つまり$Y<y>\subseteq Y_{\alpha}<y>$となる.

以上から$Y_{\alpha}<y>=Y<y>$となる.

 

よって,$Y_{\alpha}$の性質(P2)に注意して$y=\varphi(X-Y_{\alpha}<y>)=\varphi(X-Y<y>)$となる.

つまり$Y$は性質(P2)をみたす.

 

 

(ステップ3) 

$Y\subseteq X$はいいので,$X\subseteq Y$を背理法で示す. 

つまり,$X\nsubseteq Y$と仮定する.

すると,$a\colon=\varphi(X-Y)$がとれる.

$Z\colon=Y\cup{a}$として,$Z$に次のように順序を入れる.

各$z,w\in Z$で$z<_{Z}w\overset{def}{\Leftrightarrow}z<_{Y}w(z,w\in Y)\lor w=a$.

すると,この順序で$Z$は性質Pをみたす.

よって,ある$\alpha\in A$で$Z=Y_{\alpha}$と表せて$Z\subseteq Y$となる.

したがって$a\in Y$となる.

ところが$a$は定義から$X-Y$の元なので矛盾する. 

よって仮定は誤りで$X\subseteq Y$となる.

以上から,$X=Y$となる.

 

ステップ2の結果より$Y$は整列集合なので,$X$も整列集合である.$■$

 

 

じゃあ逆向きも示していきます.

選択公理から整列定理を導くのは少し長かったけど,逆はわりとスッキリ示せます.

 

 

(整列可能定理⇒選択公理の証明)

任意の非空集合族$\{X_{\alpha}|\alpha\in A\}$を考える.

整列可能定理を用いて$\underset{\alpha\in A}{\cup}X_{\alpha}$に整列順序を入れる.

すると,各$\alpha\in A$で$X_{\alpha}$は最小元$m_{\alpha}$を持つ.

そこで,写像$\varphi\colon A\to \underset{\alpha}{\cup}X_{\alpha}$を$\varphi(\alpha)=m_{\alpha}(\forall\alpha\in A)$で定める.

するとこの$\varphi$が選択関数となっている.$■$ 

 

 

なんか特にオチとかもないけど,終わります.  

 

 

参考文献

集合論入門』(ちくま学芸文庫)赤攝也著