順序集合 Ordered Set


|| そういえば順序ってそもそもなに?

『順序』が定義された「集合」(そのまま)

中身(要素)のどれかに『順序』が決まってる集合のことです。

スポンサーリンク





目次


半順序集合「半順序の関係を持ってる集合」

全順序集合「全順序の関係を持ってる集合」



順序「前と後ろの区別がつくってこと」

   反対称律「対称の時には、必ず同じになる関係」

   完全律「確実に関係が成立するっていう保証」


   前順序「最低限の関係しか満たしてない順序っぽい順序」

   半順序「比較不能のケースはあっても直観的な順序」

   全順序「全てのケースで比較が可能な順序」








注意点としては、

全て比較できる(比較可能)」ことは、この条件ではありません。



ただどれか 2 つの「要素」があって、

これに『順序関係』が定まっていれば、それでOKです。



つまりそれ以外のものが「比較できない」としても、

それでも『順序関係』が少なくとも 1 つあればそれで良いんです。




数学の大きな目的として「比較できるか」があるので、

その辺りをちょっとでも満たしてれば、

それはもう数学の範囲ですから。







半順序集合 Partially Ordered Set


|| 半ってか、部分?

↑のような、ちょっと範囲の広い『順序集合』のこと。

要は一般性のある『順序集合』のことを『半順序集合』と言います。




これは名前の通り『半順序』という「関係」が定義された、

『順序』を持った「集合」のことです。



この『半順序集合』上では「比較不能」な場合があり得ます。




ここでの重要な部分は『順序』は「関係」だという点ですね。

考えてみれば、まあ当然なんですけど。



例えば「 21 の後です」って感じですし。

数学的には『 >,≧,∈,⊆ 』みたいなのが「順序」を表します。

というか使うのってこれくらいじゃ?






全順序集合 Totally Ordered Set


|| 名前通りにぜんぶ比較できる

名前から滲み出てるかのような感じの意味で合ってます。

はい、『比較不能』な場合が無い「順序集合」のことです。



別の言い方をするなら「比較が確実にできる集合」でしょうか。




実例としては「自然数に 」とか。

これはいわゆる『大小比較』とかいうやつですね。



形式的には、順序集合を「 (N,≤) 」みたいに書きます。




これでまあ、感覚的には「順序」の意味を掴めました。

しかしはて、厳密には「順序」っていったいなんなんでしょ?



「関係」というのは分かるんですが、

はて、どんな「関係」なんでしょうか?




というわけで、さっそく「順序」について見ていきます。







順序 Order


|| 前と後ろの区別がつく感じ

集合論では「集合の上で定義された『二項関係』」のことを言います。

これじゃちょっと一般性が強過ぎてよー分からんですね。




具体例を見てみましょう。(↑のと一緒です)

集合があります。そうですね、「実数 R 」とかで。

この「実数 R 」の上では「二項関係 」が定義できます。



これはいわゆる「大小比較」です。

なら、これを使って「順序」を定義することはできますよね。



「大きい方が後」みたいにすれば、

10099 の後」って言えるんで。




この「二項関係 」が、実数上では『順序関係』となります。

具体例で見ると、まあ当然じゃんって感じしませんか?




では、その「順序関係」が満たす性質を見ていきましょう。

押さえておくべき「関係 R 」は 4 つになります。

説明には「量化記号」を使います。



・反射律「 ∀e∈S\,[\,eRe\,]

・推移律「 ∀e_1,e_2,e_3∈S\,[\,(e_1Re_2∧e_2Re_3)⇒(e_1Re_3)\,]

・反対称律「 ∀e_1,e_2∈S\,[\,(e_1Re_2∧e_2Re_1)⇒(e_1=e_2)\,]

・完全律「 ∀e_1,e_2∈S\,[\,e_1Re_2∨e_2Re_1\,]




「反射律」と「推移律」の詳細は『関係』の記事をご覧ください。

2 つは↓で解説します。






反対称関係 Antisymmetric Relation


|| 対称のアンチさん

要は「対称」にはさせん! みたいな「関係」のことです。

ただしこれ「対称律」と同居できます。(え?)



意味わかんないかもしれませんが、

対称律と同居できるのは、こいつ「 = 」のことです。




こいつは、確かに「対称律」を作らないみたいな意味ではあります。

実際、これを適用すると「入れ替え」が成立しません。( = 以外)



この感じは、例えば↑の言い換えとかだとわかりやすいかもです。



∀e_1,e_2∈S\,[\,(e_{1}Re_{2}\,∧\,(e_{1}\,{≠}\,e_{2}))⇒¬(e_2Re_1)\,]



e_{1}\,{≠}\,e_{2} 』なら「入れ替えできません」よって言ってます。

つまりは「対称関係」の不成立です。( = 以外)




こう見ると、確かに「反対称」という感じがしませんか?

ちなみに「対称じゃない」という意味の「非対称」とは異なります。

つまるところ、これは『対称関係の否定』ではありません。






完全関係 Total Relation


|| 完全な関係ってなんじゃい

これは「関係」は「全部の場合」で成り立つよ、と言ってます。



∀e_1,e_2∈S\,[\,e_1Re_2∨e_2Re_1\,] 』です。

つまり『 e_1Re_2 』か『 e_2Re_1 』が成立します。




見た感じ、なんか「完全」な感じしませんか?

なにせこの時、「関係」は『全ての場合で必ず成立する』わけです。

「関係が不成立」になるものなんか出てきません。




そう、必ず「二つの関係」は、どっちかで成立します。

例えば「 e_1≧e_2 」も「 e_2≧e_1 」もダメ、とはなりません。

どっちかは、絶対に正しくなります。






ただこれ「 e_1=e_2 」の場合だけは注意です。(また =

この時、『反射関係』が全てのパターンで成立します。

なので、こいつは「反射律」を自動的に持っちゃいます。要注意です。



なんで注意しなきゃならんのかというと、

>,< 」この辺がダメになるからですね。

といってもまあ、これも『順序』と言う場合があります。

(これは「反射律」と「対称律」を満たさない)






さて、では一通り終わったので「順序」を見ていきましょう。

先に言っとくと、「順序関係」は↑のを満たします。

主な違いは、単に満たす数が違うだけです。







前順序 Preorder


|| 前と全で発音するときややこしい

これあんま見ないんで適当に紹介。



ちなみに自分は「まえじゅんじょ」って呼んでます。

正しくは「ぜんじゅんじょ」なんですけど…




反射律」と「推移律」だけ満たす「順序関係」です。

ほぼ「推移律」だけで成り立ってるようなやつですね。

要はこれが『順序関係』って言える「最低限の要件」になります。



縛りが弱すぎてあまり実用的じゃないです。

ただ、上から抑えたいときとかには使えます。

それでもあんま使いませんが(扱うとしたら圏論とか)




ちなみにこれに「対称律」を追加すると『同値関係』になります。






半順序 Partial Order


|| 部分的に順序があるよーって感じです

直観的には「完全律」を満たすわけではない「順序関係」

みたいに考えた方が方が分かりやすいかも。




厳密には「反射律」「推移律」+「反対称律」を満たす「順序関係」

こう見るとほんとなんじゃらほいですね。

いやまじで意味わからん。なんだこれ。




この辺だと割と実用の範囲に入ります。

「比較不能」は主に「集合同士の比較」で起きるんで。

こいつが使われるのはそういう集合を扱うときです。




割と身近です。というのも、どんな集合かというと、

例えば「 S_a=\{1,2,3\} 」と「 S_b=\{1,2,8\} 」みたいなのです。

これは『順序関係 』じゃ順序が定まりません。




『冪集合』上とかでは↑みたいなのを割とよく見かけます。

なのでこいつはそれなりに使われますね。




寧ろ人間の直観に近いのはこっちの方かもしれません。

現実では順序付けできるものってそう多くないですし。






全順序 Total Order


|| よく見かけるやつ

ぜんぶ比較できるやつです。「実数上の大小比較」とか。

「順序」っていったらだいたいこいつのことです。




「数」で無理なのは「複素数上の 」とかですね。

いわゆる『線型』ではなく上下左右なので、「前後」が分かりません。




ちなみにこの『線型』じゃないと分かんない性質から、

『線型順序 Linear Order』みたいに呼ばれたり。




このくらいになると日常的に見るレベルの実用段階に入ってます。

てかほとんどの「順序」はこいつのことですね。

『全順序』こそが「順序」の主役と言っても問題ないでしょう。






はい、というわけで『全順序』が定義できました。

というわけで話は『整列集合』に移ります。(別記事)

目指すは「順序数」です。(別記事)