投稿日: 投稿者: takan

整列集合 Well-Ordered


|| 整ってる列

「整列順序」持ちの「集合」のこと。

スポンサーリンク

　

　

基本的には『自然数』の性質の話で、

『ソートアルゴリズム』とかで見る考え方になります。

　

　

これをきちんと理解するには

『順序集合』『整礎関係』が予備知識として必要です。

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

　

　

　

　

　

整列順序関係 Well-Order

　

|| 整ってて順序がある感じ

「よく見る数字」が持ってる『関係』のこと。

厳密には『整礎』かつ『全順序』な「関係」のことです。

　

0≤1≤2⋯\begin{array}{llllll} \displaystyle 0&≤&1&≤&2&\cdots \end{array}

　

「全部比較できる」し

「一番ちっちゃいのある」し

それが「集合の一部分でも成り立つ」

　

{10,20,30,...}⊂N\begin{array}{llllll} \displaystyle \{10,20,30,...\}&⊂&N \end{array}

　

10≤20≤30≤⋯\begin{array}{llllll} \displaystyle 10&≤&20&≤&30&≤&\cdots \end{array}

　

そういう「集合」の上で

『整礎』かつ『全順序』な関係

　

≤,≦,⊆\begin{array}{llllll} \displaystyle ≤,&≦,&⊆\end{array}

　

つまり「自然数」やら「実数」やらで定義できる

こういう記号を「整列順序関係」と言います。

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

　

　

　

　

　

整列集合の具体例

　

「自然数」はかなり直感的に定義できるんですけど

「整数」とか「有理数」は微妙なので解説しておきます。

　

　

　

　

　

自然数の場合

　

これは「空集合」の存在を考慮すると

「 00 を含める」ことにすれば扱いやすくなるので、

　

0:=∅1:={∅,{∅}}⋮n+1:={n,{n}}orPower  Set(n)\begin{array}{llllll} \displaystyle 0&:=&∅ \\ \\ 1&:=&\{∅,\{∅\}\} \\ \\ &\vdots&\\ \\ \displaystyle n+1&:=&\{n,\{n\}\} &\mathrm{or}&\mathrm{Power \,\, Set}(n) \end{array}

　

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

　

N=N={0,1,2,3,4,5,...}\begin{array}{llllll} \displaystyle N&=&\mathbb{N} \\ \\ &=&\{0,1,2,3,4,5,...\} \end{array}

　

この時「自然数」上では、

『整列関係 ≤≤ 』を考えると

『最小元 00 がある』ことはすぐに分かります。

　

N⊃{5,9,143}N⊃{634,957,9567,...}\begin{array}{llllll} \displaystyle N&⊃&\{5,9,143\} \\ \\ N&⊃&\{634,957,9567,...\} \end{array}

　

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

ちゃんと「最小元」が存在することも分かります。

　

　

出鱈目に並び替えたとしても同様

　

N⊃{6134,131,7613,735,2,8,836}\begin{array}{llllll} \displaystyle N&⊃&\{6134,131,7613,735,2,8,836\} \end{array}

　

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

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

　

　

　

最後、無限の場合はどうなん？って話ですが

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

　

0≤1≤⋯<ω\begin{array}{llllll} \displaystyle 0&≤&1&≤&\cdots&<&ω \end{array}

　

どこか「適当な数字を１個選んで」

「他の全てと比較」すれば

　

　

『全ての要素』が『比較可能』である以上

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

　

　

　

　

　

整数の場合

　

『最小元』を考える時

「自然数」は直感的に 00 だと分かります。

　

⋯−2−1012⋯\begin{array}{llllll} \displaystyle \cdots&-2&-1&0&1&2&\cdots \end{array}

　

しかし「整数」の範囲における『最小』は

「大小関係 ≤≤ 」上では −∞-\infty

　

−∞:=∅⋮0:=?\begin{array}{ccclll} \displaystyle -\infty&:=&∅ \\ \\ &\vdots \\ \\ 0&:=&? \end{array}

　

しかしこれを「空集合」だとする場合

00 をうまく定義することはできません。

　

　

　

　

　

基準と定義

　

整数を集合で定義する時

「最小元」をどうすればいいのか。

　

　

これを単純に決めるのは難しいですが、

中心にある『 00 』が良さそう

というのはなんとなく直感的に分かります。

　

　

他の候補も見当たりませんし

「無限」ではいろいろ不都合が多いですし。

　

　

とまあそういうわけで

「最小元」を「 00 にしてみる」

これを指針にして集合での定義を考えてみます。

　

{1,2,3,4,5,...}{−1,−2,−3,−4,...}\begin{array}{llllll} \displaystyle \{1,2,3,4,5,...\} \\ \\ \{-1,-2,-3,-4,...\} \end{array}

　

まず確認しておくと

整数は 22 ブロックに割れている

この事実はすぐに確認することができます。

　

　

その上で『 00 を基準に』

これを「整列させる」とすると

　

12345⋯−1−2⋯−11−22−3⋯\begin{array}{rrrrrrrrrrrrrrrrr} \displaystyle 1&2&3&4&5&\cdots&-1&-2&\cdots \\ \\ -1&1&-2&2&-3&\cdots \end{array}

　

これを反転させた形を含めて

パッと 44 通り思いつくわけですが、

　

1≤2≤3≤4≤5⋯−1≥−2≥⋯−1≤1≥−2≤2≥−3⋯\begin{array}{rrrrrrrrrrrrrrrr} \displaystyle 1&≤&2&≤&3&≤&4&≤&5&\cdots&-1&≥&-2&≥&\cdots \\ \\ -1&≤&1&≥&-2&≤&2&≥&-3&\cdots \end{array}

　

いずれにしても

単純に「大小関係」でこれを表現することはできません。

　

　

　

　

　

整数での整列関係

　

↑ の話から分かる通り

整数に対して、単純な整列関係は構築できません。

　

−∞<⋯≤−1≤0≤1≤⋯<∞\begin{array}{llllllllllllllllllllllllll} \displaystyle -\infty&<&\cdots&≤&-1&≤&0&≤&1&≤&\cdots&<&\infty \end{array}

　

直感的に、こういう事実は理解できますが、

集合での表現はそう単純でもなく。

　

−∞:=∅0:=∅\begin{array}{ccclll} \displaystyle -\infty&:=&∅ \\ \\ 0&:=&∅ \end{array}

　

いずれかのパターンで考える必要があって、

「関係」は、その上で考える必要があります。

　

　

　

　

　

整列関係とマイナス

　

考えられる並びの内

「途中」で無限を挟みたくない

　

−1,1,−2,2,−3,⋯\begin{array}{llllll} \displaystyle -1,1,-2,2,-3,\cdots \end{array}

　

そう考えると、並びの候補はこれに絞られます。

この上で「整列関係」を考えていくわけですが

　

≤\begin{array}{llllll} \displaystyle ≤ \end{array}

　

少なくとも

単純な整列関係ではうまくいかないので

　

　

ここでとりあえず

これを満たす整列関係を RordwellR_{\mathrm{ord}^{\mathrm{well}}} としておきます。

　

en+Rordwellen+2+\begin{array}{llllll} \displaystyle e^{+}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{+}_{n+2} \end{array}

　

その上で考えていくと

まず「正の数同士」であればこうなるのは明らか。

ここは特に問題なくクリアです。

　

en−Rordwellen+2−\begin{array}{llllll} \displaystyle e^{-}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{-}_{n+2} \end{array}

　

ただこのままだと「 −1Rordwell−2-1 R_{\mathrm{ord}^{\mathrm{well}}} -2 」

みたいな感じになるので、これは間違い。

　

enRordwellen+2\begin{array}{llllll} \displaystyle e_n&R_{\mathrm{ord}^{\mathrm{well}}}&e_{n+2}\end{array}

　

なんか分からんでもない関係ですが

このままこう定義することはできそうにありません。

　

　

　

　

　

マイナスの処理

　

↓ の並びでは

　

n+1:=Power  Set(n)\begin{array}{llllll} \displaystyle n+1&:=&\mathrm{Power \,\, Set}(n) \end{array}

　

−1,1,−2,2,−3,⋯\begin{array}{llllll} \displaystyle -1,1,-2,2,-3,\cdots \end{array}

　

集合では必ず「 n∈n+1n∈n+1 」となりますから

この記号 ∈∈ で「整列関係」を定義する場合

　

−1∈−4\begin{array}{llllll} \displaystyle -1∈-4 \end{array}

　

このような形にした方が都合が良いです。

　

en−Rordwellen+2−\begin{array}{llllll} \displaystyle e^{-}_n&R_{\mathrm{ord}^{\mathrm{well}}}&e^{-}_{n+2} \end{array}

　

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

基本的にこの形で書いてしまいたい。

　

　

となると、これを実現するためには

『マイナス記号を無視する』必要があって

　

∣en−∣Rordwell∣en+2−∣\begin{array}{llllll} \displaystyle |e^{-}_n|&R_{\mathrm{ord}^{\mathrm{well}}}&|e^{-}_{n+2}| \end{array}

　

都合の良いことに

この「絶対値 ∣−1∣<∣−3∣|-1|<|-3| 」を利用すれば

これは簡単に実現できてしまいます。

　

　

　

　

　

整数上での整列関係の定義

　

以上のことをまとめると

『最小元 00 』として

『 en∈en+1e_n∈e_{n+1} 』の並びを変えない「整列関係 RordwellR_{\mathrm{ord}^{\mathrm{well}}} 」は

　

　

正の数同士では　　　　 en+ Rordwell en+k+e^{+}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k}

正の方が後ろ　　　　　 en− Rordwell en+k+e^{-}_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,e^{+}_{n+k}

負の数が右に来るなら　 en Rordwell ∣en+k−∣e_n\,R_{\mathrm{ord}^{\mathrm{well}}}\,|e^{-}_{n+k}|

　

　

↑ を満たすとする

こうすることで実現できます。

　

　

　

総括すると

『整数上の整列関係 RordwellR_{\mathrm{ord}^{\mathrm{well}}} 』

「整列集合 (Z,Rordwell)(Z,R_{\mathrm{ord}^{\mathrm{well}}}) 」の中身は ↓

　

0,−1,1,−2,2,−3,3,⋯\begin{array}{llllll} \displaystyle 0,-1,1,-2,2,-3,3,\cdots \end{array}

　

kk を自然数として

関係の決まりは ↓ になります。

　

en+ Rordwell en+k+en− Rordwell en+k+en Rordwell ∣en+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}

　

ちょっと複雑ですが、言ってることは普通ですね。

　

　

　

　

　

この『整列集合』の考え方は

「順序数」を定義する上で必須になります。　

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