|| 整ってる列
「整列順序」持ちの「集合」のこと。
スポンサーリンク
基本的には『自然数』の性質の話で、
『ソートアルゴリズム』とかで見る考え方になります。
これをきちんと理解するには
まあ、知らなくてもなんとなく分かるとは思いますが。
整列順序関係 Well-Order
|| 整ってて順序がある感じ
「よく見る数字」が持ってる『関係』のこと。
厳密には『整礎』かつ『全順序』な「関係」のことです。
\begin{array}{llllll} \displaystyle 0&≤&1&≤&2&\cdots \end{array}
「全部比較できる」し
「一番ちっちゃいのある」し
それが「集合の一部分でも成り立つ」
\begin{array}{llllll} \displaystyle \{10,20,30,...\}&⊂&N \end{array}
\begin{array}{llllll} \displaystyle 10&≤&20&≤&30&≤&\cdots \end{array}
そういう「集合」の上で
『整礎』かつ『全順序』な関係
\begin{array}{llllll} \displaystyle ≤,&≦,&⊆\end{array}
つまり「自然数」やら「実数」やらで定義できる
こういう記号を「整列順序関係」と言います。
長くなるので『整礎関係』の詳細は別記事で。
整列集合の具体例
「自然数」はかなり直感的に定義できるんですけど
「整数」とか「有理数」は微妙なので解説しておきます。
自然数の場合
これは「空集合」の存在を考慮すると
「 0 を含める」ことにすれば扱いやすくなるので、
\begin{array}{llllll} \displaystyle 0&:=&∅ \\ \\ 1&:=&\{∅,\{∅\}\} \\ \\ &\vdots&\\ \\ \displaystyle n+1&:=&\{n,\{n\}\} &\mathrm{or}&\mathrm{Power \,\, Set}(n) \end{array}
以下、記事内での『自然数』は「 0 を含む」とします。
\begin{array}{llllll} \displaystyle N&=&\mathbb{N} \\ \\ &=&\{0,1,2,3,4,5,...\} \end{array}
この時「自然数」上では、
『整列関係 ≤ 』を考えると
『最小元 0 がある』ことはすぐに分かります。
\begin{array}{llllll} \displaystyle N&⊃&\{5,9,143\} \\ \\ N&⊃&\{634,957,9567,...\} \end{array}
また、どのように「部分集合」をとっても
ちゃんと「最小元」が存在することも分かります。
出鱈目に並び替えたとしても同様
\begin{array}{llllll} \displaystyle N&⊃&\{6134,131,7613,735,2,8,836\} \end{array}
『整列関係 ≤ 』を使って全て比較していけば、
最終的に『 2 が最小元』だと確実に分かります。
最後、無限の場合はどうなん？って話ですが
『集合の定義』より、集合の中身は確実に分かるので
\begin{array}{llllll} \displaystyle 0&≤&1&≤&\cdots&<&ω \end{array}
どこか「適当な数字を１個選んで」
「他の全てと比較」すれば
『全ての要素』が『比較可能』である以上
必ず最終的に最小元は見つかります。
整数の場合
『最小元』を考える時
「自然数」は直感的に 0 だと分かります。
\begin{array}{llllll} \displaystyle \cdots&-2&-1&0&1&2&\cdots \end{array}
しかし「整数」の範囲における『最小』は
「大小関係 ≤ 」上では -\infty
\begin{array}{ccclll} \displaystyle -\infty&:=&∅ \\ \\ &\vdots \\ \\ 0&:=&? \end{array}
しかしこれを「空集合」だとする場合
0 をうまく定義することはできません。
基準と定義
整数を集合で定義する時
「最小元」をどうすればいいのか。
これを単純に決めるのは難しいですが、
中心にある『 0 』が良さそう
というのはなんとなく直感的に分かります。
他の候補も見当たりませんし
「無限」ではいろいろ不都合が多いですし。
とまあそういうわけで
「最小元」を「 0 にしてみる」
これを指針にして集合での定義を考えてみます。
\begin{array}{llllll} \displaystyle \{1,2,3,4,5,...\} \\ \\ \{-1,-2,-3,-4,...\} \end{array}
まず確認しておくと
整数は 2 ブロックに割れている
この事実はすぐに確認することができます。
その上で『 0 を基準に』
これを「整列させる」とすると
\begin{array}{rrrrrrrrrrrrrrrrr} \displaystyle 1&2&3&4&5&\cdots&-1&-2&\cdots \\ \\ -1&1&-2&2&-3&\cdots \end{array}
これを反転させた形を含めて
パッと 4 通り思いつくわけですが、
\begin{array}{rrrrrrrrrrrrrrrr} \displaystyle 1&≤&2&≤&3&≤&4&≤&5&\cdots&-1&≥&-2&≥&\cdots \\ \\ -1&≤&1&≥&-2&≤&2&≥&-3&\cdots \end{array}
いずれにしても
単純に「大小関係」でこれを表現することはできません。
整数での整列関係
↑ の話から分かる通り
整数に対して、単純な整列関係は構築できません。
\begin{array}{llllllllllllllllllllllllll} \displaystyle -\infty&<&\cdots&≤&-1&≤&0&≤&1&≤&\cdots&<&\infty \end{array}
直感的に、こういう事実は理解できますが、
集合での表現はそう単純でもなく。
\begin{array}{ccclll} \displaystyle -\infty&:=&∅ \\ \\ 0&:=&∅ \end{array}
いずれかのパターンで考える必要があって、
「関係」は、その上で考える必要があります。
整列関係とマイナス
考えられる並びの内
「途中」で無限を挟みたくない
\begin{array}{llllll} \displaystyle -1,1,-2,2,-3,\cdots \end{array}
そう考えると、並びの候補はこれに絞られます。
この上で「整列関係」を考えていくわけですが
\begin{array}{llllll} \displaystyle ≤ \end{array}
少なくとも
単純な整列関係ではうまくいかないので
ここでとりあえず
これを満たす整列関係を R_{\mathrm{ord}^{\mathrm{well}}} としておきます。
\begin{array}{llllll} \displaystyle e^{+}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{+}_{n+2} \end{array}
その上で考えていくと
まず「正の数同士」であればこうなるのは明らか。
ここは特に問題なくクリアです。
\begin{array}{llllll} \displaystyle e^{-}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{-}_{n+2} \end{array}
ただこのままだと「 -1 R_{\mathrm{ord}^{\mathrm{well}}} -2 」
みたいな感じになるので、これは間違い。
\begin{array}{llllll} \displaystyle e_n&R_{\mathrm{ord}^{\mathrm{well}}}&e_{n+2}\end{array}
なんか分からんでもない関係ですが
このままこう定義することはできそうにありません。
マイナスの処理
↓ の並びでは
\begin{array}{llllll} \displaystyle n+1&:=&\mathrm{Power \,\, Set}(n) \end{array}
\begin{array}{llllll} \displaystyle -1,1,-2,2,-3,\cdots \end{array}
集合では必ず「 n∈n+1 」となりますから
この記号 ∈ で「整列関係」を定義する場合
\begin{array}{llllll} \displaystyle -1∈-4 \end{array}
このような形にした方が都合が良いです。
\begin{array}{llllll} \displaystyle e^{-}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{-}_{n+2} \end{array}
なので「負の数同士の関係」では
基本的にこの形で書いてしまいたい。
となると、これを実現するためには
『マイナス記号を無視する』必要があって
\begin{array}{llllll} \displaystyle |e^{-}_n|&R_{\mathrm{ord}^{\mathrm{well}}}&|e^{-}_{n+2}| \end{array}
都合の良いことに
この「絶対値 |-1|<|-3| 」を利用すれば
これは簡単に実現できてしまいます。
整数上での整列関係の定義
以上のことをまとめると
『最小元 0 』として
『 e_n∈e_{n+1} 』の並びを変えない「整列関係 R_{\mathrm{ord}^{\mathrm{well}}} 」は
正の数同士では e^{+}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k}
正の方が後ろ e^{-}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k}
負の数が右に来るなら e_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,|e^{-}_{n+k}|
↑ を満たすとする
こうすることで実現できます。
総括すると
『整数上の整列関係 R_{\mathrm{ord}^{\mathrm{well}}} 』
「整列集合 (Z,R_{\mathrm{ord}^{\mathrm{well}}}) 」の中身は ↓
\begin{array}{llllll} \displaystyle 0,-1,1,-2,2,-3,3,\cdots \end{array}
k を自然数として
関係の決まりは ↓ になります。
\begin{array}{llllll} \displaystyle e^{+}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k} \\ \\ e^{-}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k} \\ \\ e_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,|e^{-}_{n+k}| \end{array}
ちょっと複雑ですが、言ってることは普通ですね。
この『整列集合』の考え方は
「順序数」を定義する上で必須になります。
「順序数」を詳しく理解したいのなら覚えておきましょう。