|| そういえば順序ってそもそもなに?
『順序』が定義された「集合」(そのまま)
中身(要素)のどれかに『順序』が決まってる集合のことです。
スポンサーリンク
目次
・半順序集合「半順序の関係を持ってる集合」
・全順序集合「全順序の関係を持ってる集合」
・順序「前と後ろの区別がつくってこと」
反対称律「対称の時には、必ず同じになる関係」
完全律「確実に関係が成立するっていう保証」
前順序「最低限の関係しか満たしてない順序っぽい順序」
半順序「比較不能のケースはあっても直観的な順序」
全順序「全てのケースで比較が可能な順序」
注意点としては、
「全て比較できる(比較可能)」ことは、この条件ではありません。
ただどれか 2 つの「要素」があって、
これに『順序関係』が定まっていれば、それでOKです。
つまりそれ以外のものが「比較できない」としても、
それでも『順序関係』が少なくとも 1 つあればそれで良いんです。
数学の大きな目的として「比較できるか」があるので、
その辺りをちょっとでも満たしてれば、
それはもう数学の範囲ですから。
半順序集合 Partially Ordered Set
|| 半ってか、部分?
↑のような、ちょっと範囲の広い『順序集合』のこと。
要は一般性のある『順序集合』のことを『半順序集合』と言います。
これは名前の通り『半順序』という「関係」が定義された、
『順序』を持った「集合」のことです。
この『半順序集合』上では「比較不能」な場合があり得ます。
ここでの重要な部分は『順序』は「関係」だという点ですね。
考えてみれば、まあ当然なんですけど。
例えば「 2 は 1 の後です」って感じですし。
数学的には『 >,≧,∈,⊆ 』みたいなのが「順序」を表します。
というか使うのってこれくらいじゃ?
全順序集合 Totally Ordered Set
|| 名前通りにぜんぶ比較できる
名前から滲み出てるかのような感じの意味で合ってます。
はい、『比較不能』な場合が無い「順序集合」のことです。
別の言い方をするなら「比較が確実にできる集合」でしょうか。
実例としては「自然数に ≤ 」とか。
これはいわゆる『大小比較』とかいうやつですね。
形式的には、順序集合を「 (N,≤) 」みたいに書きます。
これでまあ、感覚的には「順序」の意味を掴めました。
しかしはて、厳密には「順序」っていったいなんなんでしょ?
「関係」というのは分かるんですが、
はて、どんな「関係」なんでしょうか?
というわけで、さっそく「順序」について見ていきます。
順序 Order
|| 前と後ろの区別がつく感じ
集合論では「集合の上で定義された『二項関係』」のことを言います。
これじゃちょっと一般性が強過ぎてよー分からんですね。
具体例を見てみましょう。(↑のと一緒です)
集合があります。そうですね、「実数 R 」とかで。
この「実数 R 」の上では「二項関係 ≧ 」が定義できます。
これはいわゆる「大小比較」です。
なら、これを使って「順序」を定義することはできますよね。
「大きい方が後」みたいにすれば、
「 100 は 99 の後」って言えるんで。
この「二項関係 ≧ 」が、実数上では『順序関係』となります。
具体例で見ると、まあ当然じゃんって感じしませんか?
では、その「順序関係」が満たす性質を見ていきましょう。
押さえておくべき「関係 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』みたいに呼ばれたり。
このくらいになると日常的に見るレベルの実用段階に入ってます。
てかほとんどの「順序」はこいつのことですね。
『全順序』こそが「順序」の主役と言っても問題ないでしょう。
はい、というわけで『全順序』が定義できました。
というわけで話は『整列集合』に移ります。(別記事)
目指すは「順序数」です。(別記事)