半順序関係はんじゅんじょかんけいpartial orderと全順序関係ぜんじゅんじょかんけいtotal order

1導入どうにゅう

順序関係じゅんじょかんけいorder relationで重要じゅうようなのは、「比較ひかくできる」とは何なにを意味いみするかを分解ぶんかいすることである。日常にちじょうの大小だいしょうでは、任意にんいの 2 つを比くらべられることが多おおい。しかし集合しゅうごうsetの包含ほうがんinclusionや整数せいすうintegerの整除せいじょdivisibilityでは、2 つの対象たいしょうobjectが常つねに比較ひかくできるとは限かぎらない。

この違ちがいを扱あつかうために、半順序関係はんじゅんじょかんけいpartial orderと全順序関係ぜんじゅんじょかんけいtotal orderを分わける。半順序関係はんじゅんじょかんけいpartial orderは「比較ひかくできる組くみだけを比較ひかくする」構造こうぞうであり、全順序関係ぜんじゅんじょかんけいtotal orderは「任意にんいの 2 つを必かならず比較ひかくする」構造こうぞうである。

半順序関係はんじゅんじょかんけいpartial orderでは比較不能ひかくふのうな 2 元げんが存在そんざいしてもよい。全順序関係ぜんじゅんじょかんけいtotal orderは、これに加くわえて任意にんいの 2 元げんが比較ひかくできることを要求ようきゅうする。

2用語ようごと定義ていぎ

集合しゅうごうset $$P$$P 上うえの二項関係にこうかんけいbinary relation $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le が半順序関係はんじゅんじょかんけいpartial orderであるとは、次つぎの 3 条件じょうけんを満みたすことである。表ひょうの $$a,b,c$$a,b,c は $$P$$P の任意にんいの元げんelementとする。

$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b または $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a が成立せいりつするとき、$$a$$a と $$b$$b は比較可能ひかくかのうcomparableであるという。半順序集合はんじゅんじょしゅうごうpartially ordered setで任意にんいの 2 元げんが比較可能ひかくかのうcomparableなら、その順序じゅんじょorderを全順序関係ぜんじゅんじょかんけいtotal orderという。

3方針ほうしん

順序関係じゅんじょかんけいorder relationを判定はんていするときは、まず反射性はんしゃせいreflexivity、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityを確認かくにんする。ここまでは半順序関係はんじゅんじょかんけいpartial orderの確認かくにんである。

その後あとで、任意にんいの 2 元げんが比較可能ひかくかのうcomparableかを確認かくにんする。これが成立せいりつすれば全順序関係ぜんじゅんじょかんけいtotal orderであり、成立せいりつしなければ半順序関係はんじゅんじょかんけいpartial orderだが全順序関係ぜんじゅんじょかんけいtotal orderではない。

判定はんていでは、反射性はんしゃせいreflexivity・反対称性はんたいしょうせいantisymmetry・推移性すいいせいtransitivityを順じゅんに確認かくにんする。全順序関係ぜんじゅんじょかんけいtotal orderを示しめすには、さらに任意にんいの 2 元げんが比較可能ひかくかのうであることを加くわえる。

4直感的ちょっかんてきな説明せつめい

全順序関係ぜんじゅんじょかんけいtotal orderは、一列いちれつに並ならべられる順序じゅんじょである。通常つうじょうの $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le による実数じっすうreal numberの大小だいしょうは全順序関係ぜんじゅんじょかんけいtotal orderである。任意にんいの $$a,b$$a,b について、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b または $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a が成立せいりつするからである。

一方いっぽう、半順序関係はんじゅんじょかんけいpartial orderは、枝分えだわかれを許ゆるす順序じゅんじょである。$$\{1,2\}$$\{1,2\} と $$\{1,3\}$$\{1,3\} は、包含ほうがんinclusionでは比較ひかくできない。どちらも相手あいてを含ふくまないからである。しかし $$\left\{1\right\}\subseteq \{1,2\}$$\{1\}\subseteq\{1,2\} は成立せいりつする。したがって包含ほうがんinclusionは半順序関係はんじゅんじょかんけいpartial orderであるが、一般いっぱんには全順序関係ぜんじゅんじょかんけいtotal orderではない。

5代表例だいひょうれい

5.11. べき集合しゅうごうpower setの包含順序ほうがんじゅんじょinclusion order

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) 上うえで $$B\text{[PARSE ERROR: Undefined("Command("le")")]}C$$B\le C を $$B\subseteq C$$B\subseteq C と定義ていぎする。これは半順序関係はんじゅんじょかんけいpartial orderである。反射性はんしゃせいreflexivityは $$B\subseteq B$$B\subseteq B、反対称性はんたいしょうせいantisymmetryは $$B\subseteq C$$B\subseteq C かつ $$C\subseteq B$$C\subseteq B なら $$B=C$$B=C、推移性すいいせいtransitivityは $$B\subseteq C$$B\subseteq C かつ $$C\subseteq D$$C\subseteq D なら $$B\subseteq D$$B\subseteq D であることから従したがう。

ただし、一般いっぱんには全順序関係ぜんじゅんじょかんけいtotal orderではない。$$A=\{1,2,3\}$$A=\{1,2,3\} のとき、$$\{1,2\}$$\{1,2\} と $$\{1,3\}$$\{1,3\} は比較可能ひかくかのうcomparableではない。

5.22. 正せいの整数せいすうintegerの整除順序せいじょじゅんじょdivisibility order

正せいの整数せいすうintegerの集合しゅうごうで、$$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b を「$$a$$a が $$b$$b を割わり切きる」と定義ていぎする。これは半順序関係はんじゅんじょかんけいpartial orderである。しかし $$2$$2 と $$3$$3 は互たがいに割わり切きらないため、比較可能ひかくかのうcomparableではない。したがって全順序関係ぜんじゅんじょかんけいtotal orderではない。

5.33. 数かずの通常つうじょうの大小だいしょう

$$\mathbb{R}$$\mathbb R 上うえの通常つうじょうの $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le は全順序関係ぜんじゅんじょかんけいtotal orderである。任意にんいの $$a,b\in \mathbb{R}$$a,b\in\mathbb R について $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b または $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a が成立せいりつするからである。

6例題れいだい：半順序はんじゅんじょpartial orderだが全順序ぜんじゅんじょtotal orderではないことを示しめす

6.1問題もんだい

$$A=\{1,2,3\}$$A=\{1,2,3\} とし、$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) 上うえに $$B\text{[PARSE ERROR: Undefined("Command("le")")]}C⟺B\subseteq C$$B\le C\Longleftrightarrow B\subseteq C と定義ていぎする。この順序じゅんじょorderが半順序関係はんじゅんじょかんけいpartial orderであり、全順序関係ぜんじゅんじょかんけいtotal orderではないことを示しめせ。

6.2解説かいせつ

反射性はんしゃせいreflexivityは、任意にんいの $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) について $$B\subseteq B$$B\subseteq B であることから成立せいりつする。

反対称性はんたいしょうせいantisymmetryは、$$B\subseteq C$$B\subseteq C かつ $$C\subseteq B$$C\subseteq B なら外延性がいえんせいextensionalityより $$B=C$$B=C であることから成立せいりつする。

推移性すいいせいtransitivityは、$$B\subseteq C$$B\subseteq C かつ $$C\subseteq D$$C\subseteq D なら $$B\subseteq D$$B\subseteq D であることから成立せいりつする。よってこれは半順序関係はんじゅんじょかんけいpartial orderである。

しかし $$\{1,2\}$$\{1,2\} と $$\{1,3\}$$\{1,3\} は、どちらも相手あいてを含ふくまない。したがって比較可能ひかくかのうcomparableではない。任意にんいの 2 元げんが比較可能ひかくかのうcomparableではないので、これは全順序関係ぜんじゅんじょかんけいtotal orderではない。

7見分みわけ方かた

• 比較ひかくの関係かんけいが反射性はんしゃせいreflexivity、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityを満みたすなら、半順序関係はんじゅんじょかんけいpartial orderを疑うたがう。
• 任意にんいの 2 元げんが比較ひかくできるなら、全順序関係ぜんじゅんじょかんけいtotal orderである。
• 比較ひかくできない 2 元げんが 1 組くみでも存在そんざいすれば、全順序関係ぜんじゅんじょかんけいtotal orderではない。
• 同値関係どうちかんけいequivalence relation は対称性たいしょうせいsymmetryを持もつが、順序関係じゅんじょかんけいorder relationは反対称性はんたいしょうせいantisymmetryを持もつ。この違ちがいを混同こんどうしない。

比較不能ひかくふのうincomparableな組くみがあることは、全順序関係ぜんじゅんじょかんけいtotal orderの失敗しっぱいを示しめすが、半順序関係はんじゅんじょかんけいpartial orderの失敗しっぱいではない。反対称性はんたいしょうせいantisymmetryでは、両向りょうむきに関係かんけいする別べつの 2 元げんがないかを確認かくにんする。

8証明しょうめい補足ほそく：部分集合ぶぶんしゅうごうへの制限せいげんで順序じゅんじょが保存ほぞんされる

$$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) を半順序集合はんじゅんじょしゅうごうpartially ordered set とし、$$Y\subseteq X$$Y\subseteq X とする。$$Y$$Y 上うえの関係かんけいを

で定義ていぎする。このとき $$(Y,{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y)$$(Y,\le_Y) も半順序集合はんじゅんじょしゅうごうである。

反射性はんしゃせいは、任意にんいの $$y\in Y$$y\in Y について $$y\text{[PARSE ERROR: Undefined("Command("le")")]}y$$y\le y が $$X$$X で成立せいりつすることから従したがう。反対称性はんたいしょうせいは、$$y_1{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y{y}_2$$y_1\le_Y y_2 かつ $$y_2{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y{y}_1$$y_2\le_Y y_1 なら、$$X$$X で $$y_1\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_2$$y_1\le y_2 かつ $$y_2\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_1$$y_2\le y_1 なので $$y_1=y_2$$y_1=y_2 であることから従したがう。推移性すいいせいも同おなじく、$$X$$X での推移性すいいせいをそのまま使つかう。

さらに $$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) が全順序集合ぜんじゅんじょしゅうごうtotally ordered set なら、$$(Y,{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y)$$(Y,\le_Y) も全順序集合ぜんじゅんじょしゅうごうである。任意にんいの $$y_1,y_2\in Y$$y_1,y_2\in Y は $$X$$X の要素ようそでもあるので、$$y_1\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_2$$y_1\le y_2 または $$y_2\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_1$$y_2\le y_1 が成立せいりつするからである。

この証明しょうめいは、順序じゅんじょを小ちいさな集合しゅうごうへ制限せいげんしても、順序じゅんじょの公理こうりが壊こわれないことを示しめしている。

9演習えんしゅうリンク

10関連かんれんリンク