ツォルンの補題
こんにちは,ぱいです.
寒いですね.寒いのに雪が降らない.
雪が降れば寒くてもちょっとワクワクするのにね.こんなこと言ったら雪国の人たちに殴られそうだけど.
にゃーんって感じです.
そういえばなんかツイッターのアカウントが消えてますけどまあ寂しくなったら多分また復活します.
にゃーん.
ところで,
年末ぐらいに,選択公理⇔Zornの補題 の証明を書こーってツイートした記憶があるので,忘れないうちに書いておきますね.
とりあえず主張を.
任意の非空集合族$\{X_{\alpha}|\alpha\in A\}$に対して,$\varphi(\alpha)\in X_{\alpha}(\forall\alpha\in A)$となる写像$\varphi:A\to \underset{\alpha\in A}{\cup}X_{\alpha}$(選択関数)が存在する.
任意の帰納的順序集合は極大元をもつ.
帰納的とか極大とかの定義をたぶん前までの記事で書いてないので書いときます.
順序とかの定義はたぶんどこかで書きました.わからなかったら過去記事を漁ってください.
順序集合$X$が帰納的である.$\overset{def}{\Leftrightarrow}$任意の全順序集合$Y\subseteq X$が$X$で上限をもつ.
(順序集合$X$で)$m\in X$が極大である.$\overset{def}{\Leftrightarrow}$$m\leq a\Rightarrow m=a(\forall a\in X)$.
最大と極大ってなんかややこしいですよね.
僕は最初のころどう違うのかよく分かんなかったです()
最大元はどの元と比べても一番大きいやつで,極大元は比べられる元たちの中では一番大きいものという感じです.
さて、次の定理を考えてゆきましょー.
定理.
この定理を示していく前に,ひとつ命題を紹介しておきます.
任意の半順序集合は(包含関係で)極大な整列部分集合を含む.
(この命題を☆と呼ぶことにします.)
この命題☆について,次が成り立ちます.
この補題を使うと定理の証明が少し楽になる(気がする)ので,まずはこれから考えてゆきましょー.
細かい記号とかは前の記事とかを参照してください.$W<a>$で切片とか.
(補題の証明)
任意の帰納的集合$X$を考える.
$X$の整列部分集合全体の集合を$\mathbb{A}$とすると,☆の条件から$\mathbb{A}$は包含関係での極大元$M $をもつ.
いま$X$は帰納的なので,$M $は上界$a$をもつ.
このとき,じつは$a\in M $となる.
それを背理法で示す.
$a\notin M $と仮定する.
$N:=M\cup\{a\}$に次のように順序を入れる.
$\forall x,y\in N,x<_{N}y\overset{def}{\Leftrightarrow}x<_{M}y\lor y=a.$
すると$N$は整列集合となり$N<a>=M$となるが,これは$M $の極大性に反する.
よって$a\in M $である.
したがって,$a$は$M $の最大元である.
また,$a<_{X}b$となる$b\in X$が存在すると仮定すると,$M\cup\{b\}$でさっきと同じ議論をして矛盾が出てくる.
よって,この$a$が$X$の極大元である.$■$
はいじゃあ今度は定理のほうを証明していきましょー.
いま示した補題を使ったら,このあいだの記事で選択公理から整列定理を示したのとほとんど同じやり方で証明ができます.
任意の半順序集合$X$を考える.
$\varphi:2^X\to X$を選択関数とする.つまり,$\forall Y\subseteq X, \varphi(Y)\in Y$.
また,$X$の整列部分集合全体を$\mathbb{W}$として,$A$で添え字づけて$\mathbb{W}=\{W_{\alpha}|\alpha\in A\}$としておく.
そして$W=\underset{\alpha\in A}{\cup}W_{\alpha}$としておく.
あと,各部分集合$Y\subseteq X$についての次の性質をPと呼ぶことにする.
(P1)$Y$は整列集合である.
(P2)各$y\in Y$について$P_{Y}(y):=\{x\in X|\forall p\in Y<y>,p<_{Y}y\}$として,$y=\varphi(P_{Y}(y))$となる.
性質Pをみたす集合全体を$\mathbb{Y}$として,$\mathbb{Y}$を$\Lambda$で添え字づけて$\mathbb{Y}={Y_{\lambda}|\lambda\in\Lambda}$としておく.
また,$Y=\underset{\lambda\in\Lambda}{\cup}Y_{\lambda}$とする.
整列定理のときみたいに,3つのステップに分けて考えていきます.
ステップ1
各$\lambda,\mu\in\Lambda$について次のうち1つのみが必ず成り立つ.
(ア)$Y_{\lambda}=Y_{\mu}$.
(イ)$\exists l\in Y_{\lambda},Y_{\lambda}<l>=Y_{\mu}$.
(ウ)$\exists m\in Y_{\mu},Y_{\lambda}=Y_{\mu}<m>$.
ステップ2
$Y$は性質Pをみたす.
ステップ3
$Y$は$\mathbb{W}$の極大元である.
じゃあ,順番に示していきます.
(ステップ1)
整列集合の比較定理から,各$\lambda,\mu\in\Lambda$について次のうち1つのみが必ず成り立つ.
(あ)$Y_{\lambda}\cong Y_{\mu}$.
(い)$\exists l\in Y_{\lambda},Y_{\lambda}<l>\cong Y_{\mu}$.
(う)$\exists m\in Y_{\mu},Y_{\lambda}\cong Y_{\mu}<m>$.
まず(あ)が成り立つ場合を考える.
$f:Y_{\lambda}\to Y_{\mu}$を順序同型写像とすると,$f$は恒等写像となる.
それを背理法で示す.
$f$が恒等写像でないと仮定する.
すると,$S:=\{y\in Y_{\lambda}|f(y)\neq y\}$として$S\neq\emptyset$となる.
そこで$S$の$\leq_{Y_{\lambda}}$での最小元$m $が取れる.
ここで,整列定理のときの証明と同じようにして$Y_{\lambda}<m>=Y_{\mu}<f(m)>$とわかる.
このとき,$P_{Y_{\lambda}}(m)=P_{Y_{\mu}}(f(m))$となり$m=\varphi(P_{Y_{\lambda}}(m))=\varphi(P_{Y_{\mu}}(f(m)))=f(m)$となる.
ところがこれは$m\in S$に反する.
よって$f$は恒等写像となる.
したがって(ア)が成り立つ.
同様にして,(い),(う)に対してそれぞれ(イ),(ウ)が成り立つ.$■$
(ステップ2)
$Y$に整列定理の証明のときと同じ順序を入れておく.
すると$Y$は(P1)をみたす.
あとは$Y$が(P2)をみたすことを示せばよい.
任意の$y\in Y$を考えると,ある$\lambda\in\Lambda$で$y\in Y_{\lambda}$となる.
このとき,整列定理のときの証明と同じで$Y<y>=Y_{\lambda}<y>$となる.
すると$P_{Y}(y)=P_{Y_{\lambda}}(y)$となり,$\varphi(P_{Y}(y))=\varphi(P_{Y_{\lambda}}(y))=y$となる.
よって$Y$は性質Pをみたす.$■$
(ステップ3)
背理法で示す.
$Y$が$\mathbb{W}$の極大元でないと仮定する.
すると,ある$\alpha\in A$で$Y\underset{\neq}{\subset}W_{\alpha}$となる.
そこで,$a\in W_{\alpha}-Y$をとり,$Z:=Y\{a\}$とする.
$Z$には次のように順序を入れておく.
$\forall z,w\in Z,z<_{Z}w\overset{def}{\Leftrightarrow}z<_{Y}w\lor w=a$.
すると$Z$は(P1)をみたす.
また,$Y$は(P2)をみたすし$P_{Z}(a)=\{a\}$より$\varphi(P_{Z}(a))=a$なので,$Z$は(P2)もみたす.
よって$Z\in\mathbb{Y}$となるので,$Z\subseteq Y$つまり$a\in Y$となる.
ところがこれは$a$の取り方に反する.
よって$Y$は$\mathbb{W}$の極大元である.$■$
以上のステップから,選択公理⇒☆が示された.
こっちは割りとあっさりしています.
任意の非空集合族$\{X_{\alpha}|\alpha\in A\}$を考える.
$F:=\{f:B\to\underset{\alpha\in A}{\cup}:選択関数|B\subseteq A\}$とすると,$F$は帰納的な集合となる.
よって,Zornの補題から$F$は極大元$m:M\to\underset{\alpha\in A}{\cup}X_{\alpha}$をもつ.
このときじつは$M=A$である.
それを背理法で示す.
$M\neq A$と仮定すると,$\lambda\in A-M$が取れる.
この$\lambda$に対して,$a\in X_{\lambda}$が取れる.
そこで$N:=M\cup\{\lambda\}$として,$f:N\to\underset{\alpha\in A}{\cup}X_{\alpha}$を各$\alpha\in N$に対して次のように定める.
$\alpha\in M$なら$f(\alpha)=m(\alpha)$,$\alpha=\lambda$なら$f(\alpha)=a$.
するとこの$f$は選択関数になっていて,$m\underset{\neq}{\subset}f$である.
ところがこれは$m $の極大性に反する.
よって$M=A$となるので,$m $が$\{X_{\alpha}|\alpha\in A\}$の選択関数となっている.$■$
はいおしまい.
選択公理⇒☆⇒Zornの補題⇒選択公理 というふうに証明をしたので,じつは命題☆も選択公理と同値だったんですね~.
あ,そういえば明けましておめでとうございます.
参考文献
整列可能定理
ひかるさんのアドベントカレンダー企画の3日目の記事です.
このあいだの記事で整列集合のことを少し書きました.
$\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$が選択関数となっている.$■$
なんか特にオチとかもないけど,終わります.
参考文献
整列集合の定義と比較定理
今度整列可能定理の話とかを書きたいと思ってるので、その準備。
まず、順序集合の定義から。
集合$X$と$X$上の二項関係$\leq$が次の$(1),(2),(3)$を満たすとします。
$(1)\forall x\in X, x\leq x$
$(2)\forall x,y\in X,x\leq y\land y\leq x\Rightarrow x=y$
$(3)\forall x,y,z\in X,x\leq y\land y\land z\Rightarrow x\leq z$
このとき、$\leq$を$X$の順序といい、$(X,\leq)$は順序集合であるといいます。
順序が明らかなときは$(X,\leq )$を単に$X$と書いたりすることもあります。
順序集合$X$の任意の元同士が比較可能のとき、つまり次の$(4)$が成り立つとき、$X$は全順序集合であるといいます。
$(4)\forall x,y\in X,x\leq y\lor y\leq x$
全順序でない順序を特に半順序と呼んだりもします。
たとえば実数の普通の大小関係とかは全順序ですね。
てきとーに集合$X$を考えたとき、そのべき集合は集合の包含関係で半順序です。
あと、複素数の集合には順序が入らないみたいなことを言う人がたまにいるみたいですけど(まあ実数の普通の大小関係と同じように入れられないという意味だとは思うけど)複素数にもたとえば辞書式順序とかで全順序が入ります。
つまり、各$x=a+bi,y=c+di\in\mathbb{C}(a,b,c,d\in\mathbb{R})$で$x\leq y\overset{def}{\Leftrightarrow}a\leq c\lor(a=c\land b\leq d)$で$\leq$を定めると$(\mathbb{C},\leq)$は全順序集合となります。
同じ集合でも順序の入れ方はいろいろあります。
たとえば自分の同級生たちの集合に、身長順で順序を入れたり体重順で順序を入れたりできるみたいな感じです。
2つの順序集合を考えるときは、順序の構造が似てるかどうかというのをよく調べます。
順序構造が似てるかどうかというのは、元の対応で考えます。
$(X,\leq_X),(Y,\leq_Y)$が順序集合で$f\colon X\to Y$が次の条件を満たすとき$f$は順序を保つ写像であるといいます。
$\forall a,b\in X,a\leq_X b\Rightarrow f(a)\leq_Y f(b)$
順序を保つ写像$f$が全単射で逆写像も順序を保つとき特に$f$を同型写像といいます。
$X$と$Y$の間に同型写像があるとき$X$と$Y$は同型であるといって、そのことを$X\cong Y$と書きます。
順序集合どうしの同型という関係は、同値関係になっています。
同型な集合同士は同じような順序構造が入っているといえます。
たとえば$\mathbb{N}$と$\mathbb{Z}$は普通の大小関係では同型にはなりません。
($\mathbb{N}$には最小元があるけど$\mathbb{Z}$には最小元がないから。)
でも、$\mathbb{Z}$を$\{0,-1,1,-2,2,…,-n,n,…\}$と並び替えたら$\mathbb{N}\cong\mathbb{Z}$となります。
今度は、整列順序というものの話をします。
$X$が(全)順序集合で、空でない任意の部分集合$Y$が最小元を持つとき、その順序を整列順序といい、$X$を整列集合といいます。
「(全)順序集合」と書いたのは、全順序を要請するのをたまに見かけるからです。
でも、実は$X$半順序集合でも、各非空部分集合が最小元を持てば勝手に全順序になります。
(各$x,y\in X$について$\{x,y\}$が最小元を持つから。)
すぐ分かるように、整列集合はその部分集合もまた整列集合になります。
整列集合のイメージは、$\mathbb{N}$っぽい感じです。
$\mathbb{Z}$とかもさっきみたいに並べ直すと整列集合になります。
整列集合について、次の命題があります。
$W$が整列集合で単射$f\colon W\to W$が順序を保つとき、任意の$x\in W$で$x\leq f(x)$となる。
(証明)
$A\colon=\{x\in X|x\leq f(x)\},B\colon=\{x\in X|f(x)<x\}$とおく。
$W$は全順序だから$W=A\cup B$となる。
よって、$B=\emptyset$をいえばいい。
背理法で$B=\emptyset$を示す。
$B\neq\emptyset$と仮定すると、$B$は最小元$m $をもつ。
この$m $について、$m\in B$より$f(m)<m $である。
$f$は単射で順序を保つので$f(f(m))<f(m)$となり、$f(m)\in B$となる。
ところが$f(m)$は$m $つまり$B$の最小元より小さいので矛盾している。
従って$B=\emptyset$となり、$W=A$となる。$■$
次に切片というのを紹介します。
整列集合$W$と各元$a\in W$について、$a$より小さい元全体を$a$による$W$の切片と呼び、$W<a>$と書きます。
つまり$W<a>=\{x\in W|x<a\}$です。
切片は次のように特徴づけられます。
つまり、整列集合$W$と真部分集合$L\subset W$について次が成り立ちます。
$\exists a\in W,L=W<a>\Leftrightarrow\forall x\in L,W<x>\subseteq L$
(証明)
$\Rightarrow$は当たり前。
$\Leftarrow$を確認する。
$W-L$は空でないのでその最小元$m$が存在する。
この$m $について、$W<m>\subseteq L$となる。
実際、$x\in W<m>$を任意にとると$x<m $であるが、もしも$x\notin L$とすると$x\in (W-L)$となり$(W-L)$の最小元$m $より小さいことに反するので、$x\in L$となる。
逆に$L\subseteq W<m>$も成り立つ。
実際、$y\in L$を任意にとり、もし$y\notin W<m>$と仮定すると$m\leq y$より$m\in W<y>$となり条件から$m\in L$となるがこれは$m\in (W-L)$に反するので、$y\in W<m>$となる。
以上から$L=W<m>$となる。$■$
整列集合$W$から$W$自身への順序をたもつ写像についての性質から、切片について次が成り立ちます。
$(1)\forall x\in W,W\ncong W<x>$
$(2)\forall x,y\in W,x\neq y\Rightarrow W<x>\ncong W<y>$
(証明)
(1)
背理法で示す。
ある$a\in W$で$W\cong W<a>$となるとする。
すると、順序同型$f\colon W\to W<a>$が存在する。
$a\in W$について$f(a)\in W<a>$より$f(a)<a$となるが、これはさっきの命題に反する。
よって、$W\cong W<a>$となる$a\in W$は存在しない。
(2)
$x,y\in W,x\neq y$を任意にとる。
$W$は全順序なので$x<y$としてよい。
このとき$(W<y>)<x>=W<x>$なので、(1)から$W<y>\ncong W<x>$となる。$■$
また、2つの同型な整列集合$V,W$について次が成り立ちます。
$(1)\forall a\in V,\exists!b\in W,V<a>\cong W<b>$
$(2)$同型写像$V\to W$はただひとつしか存在しない。
(証明)
(1)
$f\colon V\to W$を同型写像とする。
各$a\in V$に対して、$V<a>\cong W<f(a)>$である。
また、$b,c\in W$で$W<a>\cong W<b>,W<a>\cong W<c>$のとき$W<b>\cong W<c>$となるのでさっきの命題から$b=c$となります。
(2)
任意の同型写像$f,g\colon V\to W$を考える。
任意の$x\in V$について、$W<f(x)>\cong W<g(x)>$となるのでさっきの命題から$f(x)=g(x)$となる。
よって$f=g$となる。$■$
最後に、ふたつの整列集合$V,W$についての重要な定理をひとつ紹介しておきます。
整列集合の比較定理
任意の整列集合$V,W$について、次の(あ)、(い)、(う)のうちひとつが必ず成り立ち、成り立つのはひとつだけである。
(あ)$V\cong W$
(い)$\exists a\in V,V<a>\cong W$
(う)$\exists b\in W,V\cong W<b>$
(証明)
$K\colon=\{x\in V|\exists!y\in W,V<x>\cong W<y>\}$
$L\colon=\{y\in W|\exists!x\in V,V<x>\cong W<y>\}$とする。
すると、$K$と$L$には自然に一対一の対応がつく。
その対応を$f$とすると$f$は順序同型である。
各$x\in K$について$V<x>\cong W<f(x)>$となるので、同型写像$g_x\colon V<x>\to W<f(x)>$が一意的にとれる。
$K\neq V$のときある$a\in V$で$K=V<a>$となるので、それを示す。
任意の$x\in K$を考える。
$z\in V<x>$を任意にとると$g_z$の$V<z>$での制限によって$V<z>\cong W<f(g_x(z))>$となり、$z\in K$となる。
つまり$V<x>\subseteq K$となる。
よって、さっき書いた切片の特徴から、ある$a\in V$で$ K=V<a>$となる。
同様にして、$L\neq W$のときある$b\in W$で$L=W<b>$となる。
したがって、$V,W,K,L$について、次の4つの状況が起こり得る。
(ア)$K=V,L=W$
(イ)$K=V,L=W<b>(\exists b\in W)$
(ウ)$K=V<a>(\exists a\in V),L=W$
(エ)$K=V<a>(\exists a\in V),L=W<b>(\exists b\in W)$
ただし、実際には(エ)は起こり得ない。
(もし(エ)のような状況が起きれば、$V<a>\cong W<b>$より$a\in K$つまり$a\in V<a>$となるがこれは切片の定義に反するから。)
$K\cong L$だから、(ア)、(イ)、(ウ)のときそれぞれ(あ)、(い)、(う)が成り立つ。
(あ)、(い)、(う)のいずれも両立しないのは、さっき書いた整列集合についての命題から分かる。$■$
おわり。
今度は、この整列集合の比較定理を使って、選択公理と整列可能定理の同値になる証明を書きます。そのうち。
参考文献
数学たん(@suugakutan)さんの一連のツイート。
ちりも積もれば山となる。
$\int ちりdx=山。$
ネギネギ
$Y←$ねぎ。
$\mathbb{Y}←$白ネギ
なんとなくブログ始めてみた。
なんとなく気が向いたのでブログを始めてみました。
ぱいです。
まあなんか数学の面白い話とかあったときにメモしていけたらいいかなーみたいなふうに思ってます。
過去のボクの経験から、更新はたぶん月1回とかになりそう。ゎら