見出し画像

順序

通常よくあるように、会社の組織体制としてピラミッド構造している状況を考えよう。そこにはいわゆる上司・部下の関係(上下関係)がある。よってこの組織には順序の構造ある。この順序では同じ会社員だが、部署が違えば上下の比較ができないものもある。一方で社長さんと比べればどの社員よりも上に位置している。この会社の社員全員と、その間の上下関係を併せて考えるということは、そこにある順序の構造を意識している。

もう少し単純な順序の例では、「実数の世界」には大小の関係があるのもそうだ。2つの大小関係を記号<(小なり)、>(大なり)を使って表現された:
1は2より小さい ⇔ 1<2
5はー1より大きい ⇔ 5>-1

念のため「小なり」を定義すると次のようになる:
a<b ⇔ ある正の実数cが存在して、b=a+cと表される

「大なり」についても同様で、次のようになる:
a>b ⇔ b<a
    ⇔ ある正の実数cが存在して、a=b+cと表される

また、「以下」、「以上」を記号≦(小なりイコール)、≧(大なりイコール)を使って表す。

0は0以下である ⇔ 0≦0
円周率πは3.14以上である ⇔ π≧3.14

これらは、実数a,bについて
a≦b ⇔ a<b または a=b
a≧b ⇔ b≦a
    ⇔ b<a または b=a
として定義される。

この関係「≦」については、次の3条件を満足することが上の定義から証明される:
(1)反射律:
 任意の実数xについて、x≦xである。
(2)反対称律:
 任意の実数x,yについて、”x≦yかつy≦x⇒x=y”である。
(3)推移律:
 任意の実数x,y,zについて、”x≦yかつy≦z⇒x≦z”である。

こららの条件を満たすとき、関係≦は順序関係といわれ、実数全体とその上の2項関係≦を併せて考えたものは順序集合と呼ばれる。(「関係」の項を参照)

このように、実数の大小関係は一般的な「順序集合」の枠組みの中に納まる。

では、冒頭の会社員全員の集合における上下関係についてはどうだろうか。この上下関係の定義を、反射律を認めるようにすれば(すなわち自分自身も上下関係をもつという広い意味で定義すれば)、
(1)反射律は満たす
  理由:自分自身は上司以上だ
(2)反対称律は満たすとは限らない
  理由:自分の上司以上でもあり部下以下でもあるような社員は、自分との同僚である
(3)推移律は満たす
  理由:上司の上司は上司だ
従って(2)反対称律が必ずしも満たされないので、上の定義による順序集合には当てはまらない。しかし感覚的には順序の仲間に入れたい気持ちがある。そこで、(1)反射律と(3)推移律を満たしている場合は前順序集合と呼ぶ。これを一般の集合の上で定義しておこう。

【定義】
与えられた集合X上の2項関係Rが反射律、推移律を満たすとき、(X,R)を前順序集合(ぜんじゅんじょしゅうごう)と呼ばれる。

英語で”preoder set”と言われるので”前”という接頭語がある。さらに反対称律を満たすときはその”前”が取れて、順序集合、あるいは半順序集合(はんじゅんじょしゅうごう)と呼ばれる。なお”半”と言っているのは、比較ができない元a,bがあってもよいことを言っている。さらに次の「比較可能性」の条件を入れよう。

比較可能性
Xの任意の2元a,bについて、aRbまたはbRaを満たす。

こうして反射律、反対称律、推移律、比較可能性の4条件を備えたときは、全順序集合(ぜんじゅんじょしゅうごう)と言われ、英語でいう"total order set"となる。

例えば、実数全体の集合の大小関係は全順序集合である。

一方、集合Aが2つ以上の元を含むとし、Aの部分集合すべての集合をP、Pにおける2項関係を集合の包含関係(⊂)と考えたときは、(P,⊂)は半順序集合となるが、全順序集合とはならない。例えばA={1,2}のとき、
{1}⊄{2},{2}⊄{1}
であるから、Pの2元{1}と{2}については比較可能ではない。また、X⊂YかつY⊂XならばX=Yであるから反対称律を満たす。反射律、推移律も明らかだろう。

また、自然数の集合Nにおける整除関係|(注意1)は、全順序にならず、半順序の例である。しかし整数の集合Zにおける整除関係|は、半順序にもならず、前順序である。実際、
1|(-1) かつ (-1)|1 であるが、1 ≠ -1
よって、反対称律を満たさない。

(注意1:a,bを整数とする。bがaの倍数である、または同じことだがaはbの約数であるとき、a|bと書き、この関係を整除関係(せいじょかんけい)と呼ぶ。
例えば、6は2の倍数だから、2|6である。しかし6は4の倍数ではないから、4|6ではない。)

これらの概念の包含関係をまとめると、
「前順序集合」 ⊃ 「(半)順序集合」 ⊃ 「全順序集合」
となる。

冒頭の会社の上下関係の例のように、前順序であるが半順序でない場合、それは反対称律を満たさない訳であるが、反対称律の仮定になるような2元はイコールとみなせば、半順序に昇格される。同僚の関係は同じ一つの対象として見直そうという訳だ。それは一般に次のような手続きを取ればよい:

(X,<)を前順序集合とする。Xの上の関係~を
a~b ⇔ a<bかつb<a
によって定義すると、関係~はXの上の同値関係となる。この同値関係~によるXの商集合X’と置く。

次にX’に次の関係<を定義する。
[a]<[b] ⇔ a<b
ただし、[a]はXの元aの~による同値類(aと関係~を持つものすべての集合)を表す:

これはXの代表元の取り方によらず定義される(注意1)。このX’の上の関係<は、反射律、反対称律、推移律を満足する(注意2)。よって(X’,<)は半順序集合となる。

(注意1)「a~a’,b~b’のとき、a<b⇒a’<b’」であることを言っている。実際、仮定を満たすとき、~の定義からa’<a<b<b’であるから、<の推移性によってa’<b’である。

(注意2)反射律:[a]<[a]
反対称律:[a]<[b]かつ[b]<[a]ならば、[a]=[b]
推移律:[a]<[b]かつ[b]<[c]ならば、[a]<[c]
をそれぞれ示せばよいが、すべてXの上の関係<のそれぞれの対応する性質から従う。


良ければサポート頂けますととても助かります。数学に関してより本質への追究と普及のための活動費として使わさせて頂きます。