順序集合 Ordered Set


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

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

中身(要素)のどれかに『順序』が定義できます。

スポンサーリンク

 

 

 


目次

 

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

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

 

 

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

 

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

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

 

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

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

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

 

 

 

 

 


 

数学にとって最も重要なことは

『比較できるかどうか』です。

 

 

その中でも「数字」は『大小の比較が可能』で

『違う』以外の比較基準が存在しています。

 

\begin{array}{llllll} \displaystyle 0&≠&3 \\ \\ 0&<&3 \end{array}

 

で、これに関わってくる話が「順序」で

この『順序が定義できる』っていう性質を満たすとき

 

 

『便利な比較の基準が作れる』

まあだから、普段使う集合はそんな感じにしたい。

 

 

この記事で扱う話はそんな感じで、

集合で『順序』を表現するにはどうすれば?

みたいな話がメインになります。

 

 

 


 


半順序集合 Partially Ordered Set

 

|| 半ってか、部分?

ちょっと範囲の広い『順序集合』のこと。

一般性のある『順序集合』と言ってもいいかもしれません。

 

 

まあ要は「部分的に順序が分かる集合」のことで

そういう「順序集合」を『半順序集合』と呼んでるだけです。

そんな難しい話ではありません。

 

 

実際、これは『半順序関係』が定義されてる集合

まあつまり『順序を持った集合』のことでしかないので。

 

 

 

特殊なのは

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

という点で、それ以外は普通。

 

\begin{array}{llllll} \displaystyle ¬(x≤y) &&∧&& ¬(x≥y) \end{array}

 

こういう風になる2要素の存在を認めてるだけです。

 

\begin{array}{llllll} \displaystyle a&<&b&<&d \\ \\ a&<&c&<&d \end{array}

 

\begin{array}{lcl} \displaystyle b&?&c \end{array}

 

具体的にはこんな感じのことを認めます。

 

 


 

 

全順序集合 Totally Ordered Set

 

|| ちゃんとぜんぶ比較できる

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

まあつまりよく使われる集合のことです。

 

 

「自然数」とか「実数」を表現するやつはこれ。

 

(N,≤)

 

記号だとこんな風に表されることがあります。

 

 

 


 


順序 Order

 

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

「集合の上で定義された『二項関係』」の中で

『比較ができる関係』から分かる「上下とか」のこと。

 

\begin{array}{llllll} \displaystyle <&≤&∈&⊂ \end{array}

 

まあ要はこういう「関係から分かること」のことで

「先後・前後・上下」なんかは順序によって判断されます。

 

 

 

 

 

順序関係に関わる性質

 

「順序関係」に関わる性質は 2+2 つあります。

順序を考える上で必須なのが ↓

 

 

・推移律 ∀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∈S\,[\,(e_1Re_2∧e_2Re_1)⇒(e_1=e_2)\,]

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

 

 

「反射律」「推移律」の詳細は『関係』の記事で。

 

 


 

 

反対称関係 Antisymmetric Relation

 

|| ひっくり返しても成立するなら同じ

「違うなら違う」ってことを示す「関係」のこと。

『反対称』ですが「対称律」と同居できます(え?)

 

\begin{array}{llllll} \displaystyle a=b&∧&b=a &&⇒&& a=b \\ \\ a=b&&&&⇒&&b=a \end{array}

 

等号 = が広く知られてるせいであれですが、

それでもこれ、実はちゃんと『入れ替え』を否定していて

 

\begin{array}{llllll} a≠b&&⇒&&a≤b&∨&a≥b && 〇\\ \\ &&⇒&&a≤b&∧&a≥b &&× \\ \\ \\ \displaystyle a≠b&&⇒&&a<b&∨&a>b &&〇 \\ \\ &&⇒&&a<b&∧&a>b &&× \end{array}

 

「対称律」を成立させない

みたいな用途で使うことができます( = 以外で)

 

\begin{array}{llllll} \displaystyle a<b&&⇒&&b<a &&× \\ \\ a∈b &&⇒&&b∈a &&× \\ \\ a⊂b &&⇒&&b⊂a &&× \end{array}

 

実際、反対称律を持つ関係は対称律をほぼ持ちません。

 

 

= が有名過ぎて実感し辛いかもですが、

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

 

 


 

 

完全関係 Total Relation

 

|| 全部で関係が成立する感じ

『全部の要素で成立する関係』のこと。

 

\begin{array}{llllll} \displaystyle ∀e_1,e_2∈S&\Bigl[ e_1Re_2∨e_2Re_1 \Bigr] \end{array}

 

要素が2つあって

その時『 e_1Re_2 』か『 e_2Re_1 』が必ず成立する

こういう時にその関係は完全だ、と言います。

 

 

順序だと「全順序」で使う感じですね。

もっと弱い「半順序」とかは満たしません。

 

 

 


 


前順序 Preorder

 

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

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

 

 

これは『同値関係を考える』場合の話で、

これに「対称律」が加わると『同値関係』になります。

 

\begin{array}{llllll} \displaystyle <&∈&⊂ \end{array}

 

『順序』については「推移律」だけ満たす感じですね。

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

だいたい「反対称律」を満たしちゃうので。

 

 

 

ちなみに読みですが、

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

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

 

 


 

 

半順序 Partial Order

 

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

「完全律」を満たすわけではない「順序関係」のこと。

「推移律」「反対称律」「反射律」を満たします。

 

\begin{array}{llllll} \displaystyle <&∈&⊂ \end{array}

 

まあつまり ↑ のは「半順序関係」じゃありません。

これもまあ順序関係と言えばそんな感じもしますが

 

 

「半順序」と呼ばれるものは

↓ のみたいに「反射律」も満たす場合だけです。

 

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

 

ちなみに実用レベルの集合と関係はだいたいこれ。

 

 


 

 

全順序 Total Order

 

|| 数字を扱う時に使うやつ

「半順序」の中でも『比較できないものが無い』もの。

「順序」って言ったらだいたいこれですね。

 

\begin{array}{llllll} \displaystyle n∈N \\ \\ &n_1≤n_2&∨&n_2≤n_1 \end{array}

 

これは「集合」に制約がかかります。

全ての要素が全ての要素と比較できる

 

\begin{array}{llllll} \displaystyle ∀e_1,e_2∈S &\Bigl[ e_1Re_2∨e_2Re_1 \Bigr] \end{array}

 

「完全律」はこの条件を満たす要素だけでできた

そういう特別な集合の上でしか成立しないので。

 

\begin{array}{llllll} \displaystyle 0≤1≤2≤3≤4<5≤6≤...≤n≤... \end{array}

 

ちなみにこれはこんな感じに『線型』になるので

『線型順序 Linear Order』なんて呼ばれることもあります。

 

\begin{array}{llllll} \displaystyle ∀e,e∈S &\Bigl[ eRe∨eRe \Bigr] \\ \\ \displaystyle ∀e∈S &\Bigl[ eRe \Bigr] \end{array}

 

また完全律から

e_1≠e_2 」の制限は無いのでこれが導けますから

自動的に「反射律」も満たすことになります。

 

 

 

 

 

狭義全順序

 

順序を表現可能なものは ≤,⊆ に限らず

 

\begin{array}{llllll} \displaystyle <&⊂&∈ \end{array}

 

こういったものもかなり実用的です。

なのでこういうのも含めて全順序と言いたいですよね。

 

\begin{array}{llllll} \displaystyle a<b&:=&\Bigl( a≤b ∧a≠b \Bigr) \end{array}

 

これはまあそんな感じの話で、

↑ みたいに記号の条件を定めることでこれを実現。

 

 

そうしてできた順序が「狭義全順序」で

これは全順序よりも具体的なものになります。

 

 

 

 

 

以上、『順序』に関してはこんな感じ。

整列集合」と合わせて「順序数」の話に繋がります。