ぱいおつ日記

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

自然数の個数と実数の個数の話

数学を専門にしていない人(高校で習う集合の簡単な予備知識ぐらいは仮定するかも)向けにおもしろい話をしたいので,僕が数学科で勉強して最初に感動した話を書きます.

いろんな集合の要素の個数を比べるっていう話.

(この記事では$1$以上の整数を自然数と呼ぶことにします.)

 

まずは,簡単なもので,アルファベットの個数とひらがな五十音の個数を,どっちが多いか比べてみましょう.

まあ当然平仮名の方が個数は多いですよね.

アルファベットは$26$個しかないけど平仮名はもっと沢山ありますから.

(ところで,ひらがなって$50$文字あるのかと思ってたんですけど数えてみたら$46$個しかないんですね.なんで五十音って言うんだろう.)

 

いま僕たちはアルファベットの個数も五十音の個数も知っていたから簡単に個数を比べられましたよね.

でも,じゃあ,もしアルファベットや五十音の文字数を知らない人がいたら、その人はどうやって個数を比べたらいいんでしょうか.

 

その答は単純で,運動会の玉入れの結果発表みたいに,ひとつずつ対応をさせていけば個数が比べられます.

 

$1$文字目「A」「あ」,$2$文字目「B」「い」,...,という風に比べてみると,アルファベットは$26$文字目の「Z」で終わりますが平仮名の$26$文字目は「は」でまだまだ文字が余ってます.

それで,対応が途中で途切れてしまうので平仮名の方がたくさんあるというのが分かります.

 

数学で集合の要素の個数を比べるときは,この対応づけるやり方を使います.

そうすると,集合の要素が無数にあるような集合同士でも簡単に要素の個数を比べることができます.

 

 

たとえば正の奇数と偶数の個数を比べてみましょう.

なんとなく直感的に,どちらも同じだけ存在していそうな感じがしますよね.

実際,$1$番目の奇数「$1$」と偶数「$2$」,$2$番目の奇数「$3$」と偶数「$4$」,...,$n$番目の奇数「$2n-1$」と偶数「$2n$」,...というふうにしていくと,どちらかが先に尽きるということなく一対一に対応がつきます.

また,今の比べ方から分かるように,正の奇数全体の個数と自然数全体$\mathbb{N}$の個数も同じであることが分かります.

 

正の奇数全体を$A$と書くことにします.

$A\underset{\neq}{\subset}\mathbb{N}$だし,直感的にはなんとなく奇数は自然数の半分ぐらいしかなさそうな気がしますよね.

ところが実際に要素の個数を比べてみると同じになるって,すこし不思議な感じがします.

無限という数はめちゃくちゃ大きいので,半分にしたぐらいでは小さくならないんですね~.

 

自然数全体$\mathbb{N}$と整数全体$\mathbb{Z}$も要素の個数も同じように考えられます.

直感的に自然数は整数の半分ぐらいしか無さそうだし,無限は半分にしたぐらいでは小さくならないので,個数は同じと言えます.

厳密には,整数を$\{0,-1,1,-2,2,...,-n,n,...\}$と並べ直して各自然数$2n-1,2n$にそれぞれ整数$n-1,-n$を対応させるとこの対応はどちらかが先に尽きるということなく一対一の対応になっています.

 

 

今度は,自然数全体$\mathbb{N}$と有理数全体$\mathbb{Q}$の要素の個数を比べてみましょう.

同じように無限の大きさは半分にしたぐらいでは変わらないので,有理数は正のものだけを考えて大丈夫です.

正の有理数全体を$\mathbb{Q}_{+}$と書くことにして、$\mathbb{N}$と$\mathbb{Q}_{+}$の要素の個数を考えてみましょう.

 

$\mathbb{Q}_{+}$の各要素は$m,n\in\mathbb{N}$を用いて$n/m $と書けますね.

また,各自然数は少し素因数分解をすると$m,n\in\mathbb{N}$を用いて$2^{n}(2m-1)$と書くことができます.

そこで各$2^{n}(2m-1)$と$n/m $を対応させると,この対応はどちらかが先に尽きてしまうということなく一対一に対応できています.

よって,自然数の個数と有理数の個数は同じであるといえます.

 

これもなんだか気持ちわるい事実ですよね~.

数直線とか見てみると,自然数って$1$ずつの間隔でポツポツとしか存在してないのに有理数はわりとギッシリ存在してるし,直感的には有理数のほうがはるかに沢山ありそうな感じがするのに!

 

 

ここまでをまとめると,偶数や奇数,整数,それに有理数も,みんな個数は自然数と同じということでした.

 

じゃあ今度は,実数全部の個数と自然数の個数を比べてみましょう.

この流れだと実数も自然数と同じだけあるのかなーと思ってしまうかもしれないですが,じつは実数のほうが自然数より真にたくさんあるんです.

無限にもいろいろ大きさがあって,実数全体の無限のレベルは自然数や整数とかの無限のレベルよりもめちゃめちゃ大きいんです.

 

 

ではそれを証明していきましょう.

 

じつは区間$[0,1]$内にある実数の個数だけでも自然数全部よりはるかに多いので,それを示してゆきます.

 

背理法で示します.(カントール対角線論法)

自然数と$[0,1]$内の実数の要素の個数が同じであると仮定します.

つまり,自然数と$[0,1]$内の実数に一対一の対応がつけられると仮定します.

 

自然数「$1$」に対応するなにか実数があるのでそれを「$a(1)$」として,自然数「$2$」に対応する実数を「$a(2)$」として,...,自然数「$n$」に対応する実数を「$a(n)$」として,...というふうに$[0,1]$内の各実数に番号がつけられます.

それで,各$a(n)$たちを十進展開して次のように表示しておきます.

(各$a(n)_{m}$は$0$から$9$までの整数のどれか.)

$a(1)=0.a(1)_{1}a(1)_{2}a(1)_{3}...a(1)_{n}...$

$a(2)=0.a(2)_{1}a(2)_{2}a(2)_{3}...a(3)_{n}...$

$a(3)=0.a(3)_{1}a(3)_{2}a(3)_{3}...a(3)_{n}...$

...

$a(n)=0.a(n)_{1}a(n)_{2}a(n)_{3}...a(n)_{n}...$

...

 

この$a(n)$たちに対して,次のように作った数$x\in[0,1]$を考えてみます.

$x$を十進展開して次のように表示します.

$x=0.x_{1}x_{2}x_{3}...x_{n}...$

各$x_{n}$たちは$0$から$9$までの整数で,次のように決めていきます.

まず,$x_{1}$は$a(1)_{1}$とは違う整数をにします.

つまり,たとえば$a(1)_{1}=2$なら$x_{1}$は$2$でない整数($3$とか$4$とか)という感じ.

次に,$x_{2}$は$a(2)_{2}$と違う整数にして,$x_{3}$は$a(3)_{3}$と違う整数にします.

そういうふうに,各$x_{n}$を$a(n)_{n}$と違う整数にして作った$x$という数を考えます.

 

こうして作った$x$は$[0,1]$内の数なので,仮定から,ある何番目かの自然数$m $に対応しているはずです.

つまり,ある自然数$m $で$x=a(m)$となるはずです.

ところが,$x$の作り方から分かるように,$x$の小数$m $位と$a(m)$の小数$m $位は異なる整数になっています.

これは矛盾しているので,仮定が誤りだったということになります.

 

つまり,自然数の個数と実数の個数が同じという仮定が誤りで,実数のほうが自然数よりもはるかに多いということが分かりました.

わーい!

 

 

無限って直感に反するような気持ち悪いことが色々起こって不思議.

おしまい.

 

 

ツォルンの補題

こんにちは,ぱいです.

 

寒いですね.寒いのに雪が降らない.

雪が降れば寒くてもちょっとワクワクするのにね.こんなこと言ったら雪国の人たちに殴られそうだけど.

にゃーんって感じです.

 

そういえばなんかツイッターのアカウントが消えてますけどまあ寂しくなったら多分また復活します.

にゃーん.

 

 

ところで,

年末ぐらいに,選択公理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}$(選択関数)が存在する.

 

Zorn補題

任意の帰納的順序集合は極大元をもつ.

 

帰納的とか極大とかの定義をたぶん前までの記事で書いてないので書いときます.

順序とかの定義はたぶんどこかで書きました.わからなかったら過去記事を漁ってください.

 

順序集合$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)$.

 

最大と極大ってなんかややこしいですよね.

僕は最初のころどう違うのかよく分かんなかったです()

最大元はどの元と比べても一番大きいやつで,極大元は比べられる元たちの中では一番大きいものという感じです.

 

 

さて、次の定理を考えてゆきましょー.

定理.

選択公理Zorn補題

 

 

この定理を示していく前に,ひとつ命題を紹介しておきます.

 

任意の半順序集合は(包含関係で)極大な整列部分集合を含む.

(この命題を☆と呼ぶことにします.)

 

この命題☆について,次が成り立ちます.

補題

☆⇒Zorn補題

 

この補題を使うと定理の証明が少し楽になる(気がする)ので,まずはこれから考えてゆきましょー.

細かい記号とかは前の記事とかを参照してください.$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$の極大元である.$■$ 

 

 

はいじゃあ今度は定理のほうを証明していきましょー.

いま示した補題を使ったら,このあいだの記事で選択公理から整列定理を示したのとほとんど同じやり方で証明ができます.

 

 

(定理の証明.選択公理Zorn補題 のほう)

さっきの補題があるので,選択公理⇒☆を証明すればいい.

 

任意の半順序集合$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}$の極大元である.$■$

 

(選択公理Zorn補題 の証明)

以上のステップから,選択公理⇒☆が示された.

よって,補題から,選択公理Zorn補題もいえる.$■$

 

 

今度は逆に,Zorn補題から選択公理を示しましょう.

こっちは割りとあっさりしています.

 

 

(Zorn補題選択公理 の証明)

任意の非空集合族$\{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日目の記事です.

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$が選択関数となっている.$■$ 

 

 

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

 

 

参考文献

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

 

 

整列集合の定義と比較定理

今度整列可能定理の話とかを書きたいと思ってるので、その準備。

 

 

まず、順序集合の定義から。

 

集合$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=山。$

可算選択公理の実数バージョン(?)

このあいだ書いた記事。

paiotunoowari.hatenadiary.jp

この記事で、こんな命題が出てきました。

 

$f\colon\mathbb{R}\to\mathbb{R}$と$\alpha\in\mathbb{R}$ について、$\alpha$に収束する任意の数列$\{x_{n}\}\subseteq\mathbb{R}$で$f(x_{n})$が$f(\alpha)$に収束するとする。このとき、$f$は$\alpha$で連続となる。

 

実はこの命題は可算選択公理の実数バージョン(?)と同値になるっていうのを前にネットで見て面白かったので紹介します。

 

つまりどういうことかと言うと、次の命題が必要十分条件であるということです。

 

任意の集合族$\{X_{n}\subseteq\mathbb{R}|n\in\mathbb{N},各X_{n}\neq\emptyset\}$に対して、ある$f\colon\mathbb{N}\to\underset{n\in\mathbb{N}}{\cup}X_{n}$で$\forall n\in\mathbb{N},f(n)\in X_{n}$となる。

 

 

(証明) ($0$は自然数に含めることにします。)

十分性は前の記事で書いたので、必要性を示す。

 

任意の集合族$\{X_{n}\subseteq\mathbb{R}|各X_{n}\neq\emptyset\}$を考える。

各$n\in\mathbb{N}$で$\varphi_{n}\colon\mathbb{R}^{n+1}\to(0,1)$を全単射とする。

また、各$n\in\mathbb{N}$で$Z_{n}\colon=\{\varphi_{n}(y)+n | y\in Y_{n}\}$として、$Z\colon\underset{n\in\mathbb{N}}{\cup}Z_{n}$とする。

すると、各$n\in\mathbb{N}$で$\emptyset\underset{\neq}{\subset}Z_{n}\subset(n,n+1)$なので、$Z$は上に非有界となる。

 

この$Z$が非有界な数列$\{z_{n}\}$を持つことを示す。

 

アイバーソンの記法*1で、$\iota\colon\mathbb{R}\to\{0,1\}$を$\iota(x)=[x\in$Arctan(Z)$]$で定める。

すると、$\iota$は$\pi/2$で不連続となる。

よって、条件より、$\pi/2$に収束する数列$\{a_{n}\}$で$\{\iota(a_n)\}$が$\iota(\pi/2)=0$に収束しないものが取れる。

このとき$\{\iota(a_{n})\}$は$1$に収束するので、$\{a_{n}\}$のある部分列$\{b_{n}\}$で各$\iota(b_{n})=1,b_{n}\to1$となるものがとれる。

この$\{b_{n}\}$に対して、数列$\{z_{n}\}$を各$z_{n}\colon=\tan(b_{n})$で定める。

すると、この$\{z_{n}\}$は上に非有界な数列である。

実際、任意の$c\in\mathbb{R}$に対して$b_{n}\to\pi/2$より$Aractan(c)<b_{n}<\pi/2$なる$b_{n}$が取れて、$c<z_{n}$となる。

 

この$\{z_{n}\}$に対して、$\cal{M}\colon=\{m\in\mathbb{N}|\exists n\in\mathbb{N},z_{n}\in Z_{m}\}$とする。

各$n\in\mathbb{N}$に対して、$n\leq\cal{m}$となるような$m\in\cal{M}$のうち最小のものを$\alpha(n)$と書くことにする。

また、$z_{m}\in Z_{\alpha(n)}$となるような$\cal{m}$のうち最小のものを$\beta(n)$と書くことにする。

 すると、各$z_{\beta(n)}\in Z_{\alpha(n)}$なので、ある$y_{\alpha(n)}\colon=(x_{0}^{\alpha(n)},x_{1}^{\alpha(n)},...,x_{\alpha(n)}^{\alpha(n)})$を用いて$z_{\beta(n)}=\varphi(y_{\alpha(n)})+\alpha(n)$と表すことが出来る。

 

この数列$\{y_{\alpha(n)}\}$に対して$f\colon\mathbb{N}\to\underset{n\in\mathbb{N}}{\cup}X_{n}$を各$f(n)\colon=x_{n}^{\alpha(n)}$で定める。

すると、この$f$で各$f(n)\in X_{n}$となる。$■$

 

 

参考文献:alg_dさんの壱大整域 実数関数の連続性 : 選択公理 | 壱大整域

 

*1:アイバーソンの記法

命題Pに対してPが真なら[P]=1、Pが偽なら[P]=0というのをアイバーソンの記法といって、便利です。

選択公理ってなんなんだろう。

突然だけど$X,Y\neq\emptyset$に対して$X\times Y$っていうものが空かどうか考えてみましょう。

まあ$X$も$Y$も空でないってしてあるので当然$x\in X$と$y\in Y$が取れますね。

なので$(x,y)\in X\times Y$となるから$X\times Y$は空でないと分かりますね。

 

$2$個の集合じゃなくて$n$個の集合で考えても一緒ですね。

つまり、$X_{1},...,X_{n}\neq\emptyset$に対して$x_{1}\in X_{1},...,x_{n}\in X_{n}$が取れるので$(x_{1},...,x_{n})\in X_{1}\times ... \times X_{n}$となり、$X_{1}\times...\times X_{n}\neq\emptyset$と分かります。

 

じゃあ今度は、次の命題を考えてみましょう。

 

命題

$f\colon\mathbb{R}\to\mathbb{R}$と$\alpha\in\mathbb{R}$ について、$\alpha$に収束する任意の数列$\{x_{n}\}\subseteq\mathbb{R}$で$f(x_{n})$が$f(\alpha)$に収束するとする。このとき、$f$は$\alpha$で連続となる。

 

さて、この命題を背理法で証明していってみましょう。

 (証明)

$f$が$\alpha$で連続でないと仮定して矛盾を導く。

この仮定より、まず、$\forall\delta>0,\exists x\in\mathbb{R},|x-\alpha|<\delta\land|f(x)-f(\alpha)|\geq\epsilon$となるような$\epsilon\in\mathbb{R}$が存在する。

この$\epsilon$に対して、各$\delta_{n}\colon=\frac{1}{n}$で数列$\{\delta_{n}\}$を考える。

各$n\in\mathbb{N}$で$X_{n}\colon=\{x\in\mathbb{R}\mid|x-\alpha|<\delta_{n}\land$$|f(x)-f(\alpha)|\geq\epsilon\}$とすると、各$X_{n}\neq\emptyset$である。

そこで、$a_{1}\in X_{1},a_{2}\in X_{2},...,a_{n}\in X_{n},...$というふうに点を取って数列$\{a_{n}\}$をつくる。

すると、各$n$で$|a_{n}-\alpha|<\delta_{n}=\frac{1}{n}$なので$a_{n}$は$\alpha$に収束する。

よって、命題の仮定から$f(a_{n})$は$f(\alpha)$に収束するはずである。

ところが、各$a_{n}\in X_{n}$より$|f(a_{n})-f(\alpha)|\geq\epsilon$なので$f(a_{n})$は$f(\alpha)$に収束しない。

これは矛盾しているので、仮定は誤りである。

つまり、$f$は$\alpha$で連続となる。$■$

 

はい。

まあパッと見た感じ、これで良さそうですよね。

 

でも、ちょっとよく考えてみてください。

上の証明で数列$\{a_{n}\}$というのを考えましたが、その作り方は、$X_{1},X_{2},...$から順番に元を取ってくるというものでした。

いちばん最初に挙げた例では考える集合の数が有限個だったからそういう操作が簡単だったけど、今回はどうでしょう。

$X_{1}$から$a_{1}$を取って、$X_{2}$から$a_{2}$を取って、$...$という操作は、永遠に終わりが見えてきません。

 

そこで役に立つのが、可算選択公理というものです。

それはいったいどういうものかというと、$\varphi\colon\mathbb{N}\to\underset{n\in\mathbb{N}}\cup,各\varphi(n)\in X_{n}$という、選択関数と呼ばれるものの存在を認めてしまおうというものです。

この公理を仮定しておけば、$\{a_{n}\},各a_{n}=\varphi(n)$という列で上の証明がちゃんと証明になるんですね。

便利な公理です。

 

さてさて、この可算選択公理をもっと便利にしたやつが選択公理です。

つまりどういうことかというと、次の主張を選択公理といいます;

任意の非空集合族$\{X_{\alpha}\}_{\alpha\in A}$について、ある$\varphi\colon A\to\underset{\alpha\in A}\cup X_{\alpha}$で$\forall\alpha\in A,\varphi(\alpha)\in X_{\alpha}$となる。

つまり、各$X_{\alpha}$から元をひとつずつ取って来れるということを保証してくれている公理なんですね。

添え字集合$A$の元の個数は$\mathbb{N}$より多くてもオッケーです。(たとえば$\mathbb{R}$とかもっと大きいものとか)

 

この選択公理があると、かのツォルンの補題とか整列可能定理とかが使えるようになって、とても便利なんですね~。

そのうちその証明とかも書こうかなーって思ってたり思っていなかったり。