整列集合の定義と比較定理
今度整列可能定理の話とかを書きたいと思ってるので、その準備。
まず、順序集合の定義から。
集合$X$と$X$上の二項関係$leq$が次の$(1),(2),(3)$を満たすとします。
$(1)forall xin X, xleq x$
$(2)forall x,yin X,xleq yland yleq xRightarrow x=y$
$(3)forall x,y,zin X,xleq yland yland zRightarrow xleq z$
このとき、$leq$を$X$の順序といい、$(X,leq)$は順序集合であるといいます。
順序が明らかなときは$(X,leq )$を単に$X$と書いたりすることもあります。
順序集合$X$の任意の元同士が比較可能のとき、つまり次の$(4)$が成り立つとき、$X$は全順序集合であるといいます。
$(4)forall x,yin X,xleq ylor yleq x$
全順序でない順序を特に半順序と呼んだりもします。
たとえば実数の普通の大小関係とかは全順序ですね。
てきとーに集合$X$を考えたとき、そのべき集合は集合の包含関係で半順序です。
あと、複素数の集合には順序が入らないみたいなことを言う人がたまにいるみたいですけど(まあ実数の普通の大小関係と同じように入れられないという意味だとは思うけど)複素数にもたとえば辞書式順序とかで全順序が入ります。
つまり、各$x=a+bi,y=c+diinmathbb{C}(a,b,c,dinmathbb{R})$で$xleq yoverset{def}{Leftrightarrow}aleq clor(a=cland bleq d)$で$leq$を定めると$(mathbb{C},leq)$は全順序集合となります。
同じ集合でも順序の入れ方はいろいろあります。
たとえば自分の同級生たちの集合に、身長順で順序を入れたり体重順で順序を入れたりできるみたいな感じです。
2つの順序集合を考えるときは、順序の構造が似てるかどうかというのをよく調べます。
順序構造が似てるかどうかというのは、元の対応で考えます。
$(X,leq_X),(Y,leq_Y)$が順序集合で$fcolon X o Y$が次の条件を満たすとき$f$は順序を保つ写像であるといいます。
$forall a,bin X,aleq_X bRightarrow f(a)leq_Y f(b)$
順序を保つ写像$f$が全単射で逆写像も順序を保つとき特に$f$を同型写像といいます。
$X$と$Y$の間に同型写像があるとき$X$と$Y$は同型であるといって、そのことを$Xcong Y$と書きます。
順序集合どうしの同型という関係は、同値関係になっています。
同型な集合同士は同じような順序構造が入っているといえます。
たとえば$mathbb{N}$と$mathbb{Z}$は普通の大小関係では同型にはなりません。
($mathbb{N}$には最小元があるけど$mathbb{Z}$には最小元がないから。)
でも、$mathbb{Z}$を${0,-1,1,-2,2,…,-n,n,…}$と並び替えたら$mathbb{N}congmathbb{Z}$となります。
今度は、整列順序というものの話をします。
$X$が(全)順序集合で、空でない任意の部分集合$Y$が最小元を持つとき、その順序を整列順序といい、$X$を整列集合といいます。
「(全)順序集合」と書いたのは、全順序を要請するのをたまに見かけるからです。
でも、実は$X$半順序集合でも、各非空部分集合が最小元を持てば勝手に全順序になります。
(各$x,yin X$について${x,y}$が最小元を持つから。)
すぐ分かるように、整列集合はその部分集合もまた整列集合になります。
整列集合のイメージは、$mathbb{N}$っぽい感じです。
$mathbb{Z}$とかもさっきみたいに並べ直すと整列集合になります。
整列集合について、次の命題があります。
$W$が整列集合で単射$fcolon W o W$が順序を保つとき、任意の$xin W$で$xleq f(x)$となる。
(証明)
$Acolon={xin X|xleq f(x)},Bcolon={xin X|f(x)<x}$とおく。
$W$は全順序だから$W=Acup B$となる。
よって、$B=emptyset$をいえばいい。
背理法で$B=emptyset$を示す。
$B eqemptyset$と仮定すると、$B$は最小元$m $をもつ。
この$m $について、$min B$より$f(m)<m $である。
$f$は単射で順序を保つので$f(f(m))<f(m)$となり、$f(m)in B$となる。
ところが$f(m)$は$m $つまり$B$の最小元より小さいので矛盾している。
従って$B=emptyset$となり、$W=A$となる。$■$
次に切片というのを紹介します。
整列集合$W$と各元$ain W$について、$a$より小さい元全体を$a$による$W$の切片と呼び、$W<a>$と書きます。
つまり$W<a>={xin W|x<a}$です。
切片は次のように特徴づけられます。
つまり、整列集合$W$と真部分集合$Lsubset W$について次が成り立ちます。
$exists ain W,L=W<a>Leftrightarrowforall xin L,W<x>subseteq L$
(証明)
$Rightarrow$は当たり前。
$Leftarrow$を確認する。
$W-L$は空でないのでその最小元$m$が存在する。
この$m $について、$W<m>subseteq L$となる。
実際、$xin W<m>$を任意にとると$x<m $であるが、もしも$x otin L$とすると$xin (W-L)$となり$(W-L)$の最小元$m $より小さいことに反するので、$xin L$となる。
逆に$Lsubseteq W<m>$も成り立つ。
実際、$yin L$を任意にとり、もし$y otin W<m>$と仮定すると$mleq y$より$min W<y>$となり条件から$min L$となるがこれは$min (W-L)$に反するので、$yin W<m>$となる。
以上から$L=W<m>$となる。$■$
整列集合$W$から$W$自身への順序をたもつ写像についての性質から、切片について次が成り立ちます。
$(1)forall xin W,W cong W<x>$
$(2)forall x,yin W,x eq yRightarrow W<x> cong W<y>$
(証明)
(1)
背理法で示す。
ある$ain W$で$Wcong W<a>$となるとする。
すると、順序同型$fcolon W o W<a>$が存在する。
$ain W$について$f(a)in W<a>$より$f(a)<a$となるが、これはさっきの命題に反する。
よって、$Wcong W<a>$となる$ain W$は存在しない。
(2)
$x,yin W,x eq y$を任意にとる。
$W$は全順序なので$x<y$としてよい。
このとき$(W<y>)<x>=W<x>$なので、(1)から$W<y> cong W<x>$となる。$■$
また、2つの同型な整列集合$V,W$について次が成り立ちます。
$(1)forall ain V,exists!bin W,V<a>cong W<b>$
$(2)$同型写像$V o W$はただひとつしか存在しない。
(証明)
(1)
$fcolon V o W$を同型写像とする。
各$ain V$に対して、$V<a>cong W<f(a)>$である。
また、$b,cin W$で$W<a>cong W<b>,W<a>cong W<c>$のとき$W<b>cong W<c>$となるのでさっきの命題から$b=c$となります。
(2)
任意の同型写像$f,gcolon V o W$を考える。
任意の$xin V$について、$W<f(x)>cong W<g(x)>$となるのでさっきの命題から$f(x)=g(x)$となる。
よって$f=g$となる。$■$
最後に、ふたつの整列集合$V,W$についての重要な定理をひとつ紹介しておきます。
整列集合の比較定理
任意の整列集合$V,W$について、次の(あ)、(い)、(う)のうちひとつが必ず成り立ち、成り立つのはひとつだけである。
(あ)$Vcong W$
(い)$exists ain V,V<a>cong W$
(う)$exists bin W,Vcong W<b>$
(証明)
$Kcolon={xin V|exists!yin W,V<x>cong W<y>}$
$Lcolon={yin W|exists!xin V,V<x>cong W<y>}$とする。
すると、$K$と$L$には自然に一対一の対応がつく。
その対応を$f$とすると$f$は順序同型である。
各$xin K$について$V<x>cong W<f(x)>$となるので、同型写像$g_xcolon V<x> o W<f(x)>$が一意的にとれる。
$K eq V$のときある$ain V$で$K=V<a>$となるので、それを示す。
任意の$xin K$を考える。
$zin V<x>$を任意にとると$g_z$の$V<z>$での制限によって$V<z>cong W<f(g_x(z))>$となり、$zin K$となる。
つまり$V<x>subseteq K$となる。
よって、さっき書いた切片の特徴から、ある$ain V$で$ K=V<a>$となる。
同様にして、$L eq W$のときある$bin W$で$L=W<b>$となる。
したがって、$V,W,K,L$について、次の4つの状況が起こり得る。
(ア)$K=V,L=W$
(イ)$K=V,L=W<b>(exists bin W)$
(ウ)$K=V<a>(exists ain V),L=W$
(エ)$K=V<a>(exists ain V),L=W<b>(exists bin W)$
ただし、実際には(エ)は起こり得ない。
(もし(エ)のような状況が起きれば、$V<a>cong W<b>$より$ain K$つまり$ain V<a>$となるがこれは切片の定義に反するから。)
$Kcong L$だから、(ア)、(イ)、(ウ)のときそれぞれ(あ)、(い)、(う)が成り立つ。
(あ)、(い)、(う)のいずれも両立しないのは、さっき書いた整列集合についての命題から分かる。$■$
おわり。
今度は、この整列集合の比較定理を使って、選択公理と整列可能定理の同値になる証明を書きます。そのうち。
参考文献
数学たん(@suugakutan)さんの一連のツイート。
