整列集合 Well-Ordered


|| 整な列

読んだまま、「整列順序」持ちの「集合」のことです。

「整列順序」は定義より「直感」で理解した方が良いかと。

スポンサーリンク



といってもまあ、定義を押さえていくわけですが。

基本的には『自然数』の性質だと思っておけば良いと思います。

使用例は『ソートアルゴリズム』とかですね。




↓の説明を見る前に、

順序集合』と『整礎関係』を知っておきましょう。

まあ、知らなくてもなんとなく分かるとは思いますが。






整列順序関係 Well-Order


|| 整な列な順序です。整な列っていうと、整った列とか?

直観的に分かると思うので、定義からさっさと行きます。



まず『全順序関係 R_{ord^{\,T}} 』が『集合 S_{ord} 』上で定義されてます。

R_{ord^{\,T}} 』の具体例は「 ≤,≦ (←どっちも同じ)」とか。



この上で『全順序関係 R_{ord^{\,T}} 』に関して「最小元」があります。



もいっちょ「最小元」に関してですが、これは↓を満たします。

『集合 S_{ord} 』の部分集合(空集合以外)もまた「最小元」を持つ

(全順序関係 R_{ord^{\,T}} についての)




あー、定義になるとしちゃかちゃしますね。

まあ、要するに↓ってことです。



「全部比較できて、しかも一番ちっちゃいのあるよ」

これが「集合の一部分でも成り立つよ」と。



もっと具体的に言うと、要は数値の性質です。(複素数とか以外の)

「実数」なり「自然数」なりが持ってる当たり前の性質になります。




ちなみにこれを、

『整礎な全順序関係』とか言ったりします。

うわー『整礎』っすよ。なんかまたきました。




といってもまあ、これかなーり大事なんで紹介します。

でも長くなるので『整礎関係』は別記事で。




とりあえず具体例を見ましょうか。

それが一番、直感的に理解するのに良いでしょう。







整列集合の具体例



自然数の場合


まずは代表的な「自然数」を使ってみます。



これは「 0 を含める」と扱いやすいので、(集合論的観点から)

以下、記事内では『自然数』は「 0 を含む」とします。




この上で、「自然数 N=\{0,1,2,3,4,5,...\} 」の上では、

『整列関係(整礎な全順序関係) 』を考えると、

『最小元 0 がある』ことが言えます。




またどのように「部分集合 N_{pt} 」をとっても、

例えば「 N_{pt}=\{5,9,143\} 」だとか。

N_{pt}=\{634,957,9567,...\} 」だとか。



ちゃんと「最小元」がそれぞれ 5634 と、ありますね。




これを出鱈目に並び替えたとしても、例えば↓みたいに。



N_{pt}=\{6134,131,7613,735,2,8,836\}



『整列関係 』を使って全て比較していけば、

最終的に『 2 が最小元』だと分かります。




↑のは有限ですが、これは当然、無限でも成立します。

なぜなら『集合の定義』より、集合の中身は確実に分かるからです。

ですから必ず最終的に最小元は見つかります。






整数の場合


ここからは少し操作を加えないといけません。

というのも、これは「整列関係 」を考えたとき、

直観的に「最小元」も「最大限」も存在しないことが分かるので。




正の数はどこまでも大きくなりますし、

負の数もまたどこまでも小さくなります。




はい、そんなわけですから普通にやると「整列関係」は得られません。

つまり別の『整列関係 R_{ord^{well}} 』を考える必要があります。




ともあれ、『整列関係』で必要なのは「最小元」です。

それでいて「部分集合」でもそれが必ず現れなければなりません。




つまり「最小元 e_{min} 」とすると、


e_{min}\,R_{ord^{well}}\,e_1\,R_{ord^{well}}\,e_2\,R_{ord^{well}}\,e_3\,R_{ord^{well}}\,…


見慣れた形だと「 e_{min}<e_1<e_2<e_3<...

↑みたいな形でないとダメってことですね。




整数は「 Z=\{...,-3,-2,-1,0,1,2,3,...\} 」ですから、

これをどうにかして↑の形にしなくちゃいけません。

なので、そんな「整列関係 R_{ord^{well}} 」を考える必要があります。






というわけで「関係 R_{ord^{well}} 」を場合分けしてみましょう。



最小元は中心にある『 0 』が良さそうです。

残念ながら他の候補は見当たりませんね。

前も後ろも限りがありませんし。




では「最小元 0 (候補)」を元に関係を定めてみましょう。

すると、まず 2 ブロックに割れてることが分かります。

\{1,2,3,4,5,...\} 』と『 \{-1,-2,-3,-4,...\} 』に。




というわけで、これを使って「整列」させてみましょう。

しかしはて、どうしましょうか。



パッと思いつくことなら 4 通りくらいですね。

1,2,3,...,-1,-2,... 」「←の反転」の形で作るか、

-1,1,-2,2,-3,... 」「←の反転」で作るかのどれかでしょう。




こうなると、まず「正負の関係」について定めないといけません。

直観はこうなので『正の方が大きい(後ろ)』としましょうか。



形式的にはこんな『 e^{-}\,R_{ord^{well}}\,e^{+} 』です。




4 つは多いので「 -1,1,-2,2,-3,… 」に絞って考えましょう。

すると「正の数同士」であれば、この「整列関係」は直観的です。



形式であれば『 e^{+}_1\,R_{ord^{well}}\,e^{+}_2




しかし「 -1 R_{ord^{well}} -2 」となってることが分かります。

これは直観に反する並びですが、なんか分からんでもないです。



これはどうも「 - 」を取り除けばいけそうな気がします。

なので「負の数同士の関係」は、

例えばこう「 |-1|<|-3| 」しましょう。



形式的には「 |e^{-}_1|\,R_{ord^{well}}\,|e^{-}_2| 」で。






まとめると、

『最小元 0 』があって、

『正の方が後ろ e^{-}\,R_{ord^{well}}\,e^{+} 』で、

『正の数同士では e^{+}_1\,R_{ord^{well}}\,e^{+}_2 』となって、

『負の数同士では |e^{-}_1|\,R_{ord^{well}}\,|e^{-}_2| 』記号を外す。




↑を満たす「関係」なら、『整数上の整列関係』と言えます。

その「整列集合 (Z,R_{ord^{well}}) 」の中身は、

0,-1,1,-2,2,-3,3,... 』です。




ちょっとややこしいですね。











この『整列集合』は「順序数」を定義する上で必須になります。 

順序数」を詳しく理解したいのなら押さえておきましょう。