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

Partial orders半順序関係はんじゅんじょかんけい and total orders全順序関係ぜんじゅんじょかんけい

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 元げんが比較ひかくできることを要求ようきゅうする。

1Introduction

For an order relation順序関係じゅんじょかんけい, the first point is to separate what it means for two objects to be comparable. In ordinary numerical order, any two numbers can usually be compared. In inclusion包含ほうがん of sets or divisibility整除せいじょ of integers, two objects need not be comparable.

This distinction leads to partial orders半順序関係はんじゅんじょかんけい and total orders全順序関係ぜんじゅんじょかんけい. A partial order compares the pairs that the structure allows us to compare. A total order requires every pair of elements to be comparable.

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

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

$$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という。

2Terms and definitions

A binary relation二項関係にこうかんけい $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le on a set集合しゅうごう $$P$$P is a partial order半順序関係はんじゅんじょかんけい if it satisfies the following three conditions.

If $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b or $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a holds, then $$a$$a and $$b$$b are comparable比較可能ひかくかのう. If every two elements of a partially ordered set半順序集合はんじゅんじょしゅうごう are comparable, the order is a total order全順序関係ぜんじゅんじょかんけい.

3方針ほうしん

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

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

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

3Method

To prove that a relation is a partial order半順序関係はんじゅんじょかんけい, check reflexivity, antisymmetry, and transitivity separately. These three checks are the partial-order part.

After that, check whether every pair of elements is comparable. If yes, the order is total. If not, it remains a partial order but is not total.

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ではない。

4Intuitive explanation

A total order全順序関係ぜんじゅんじょかんけい is an order that can be placed in one line. The usual order $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le on real numbers is total because, for any $$a,b$$a,b, either $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b or $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a.

A partial order半順序関係はんじゅんじょかんけい allows branching. The sets $$\{1,2\}$$\{1,2\} and $$\{1,3\}$$\{1,3\} are not comparable by inclusion, because neither contains the other. However, $$\left\{1\right\}\subseteq \{1,2\}$$\{1\}\subseteq\{1,2\} is comparable. Thus inclusion is a partial order, but not usually a total order.

5代表例だいひょうれい

5Representative examples

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.11. Inclusion order on a power set

On $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A), define $$B\text{[PARSE ERROR: Undefined("Command("le")")]}C$$B\le C by $$B\subseteq C$$B\subseteq C. This is a partial order半順序関係はんじゅんじょかんけい. Reflexivity is $$B\subseteq B$$B\subseteq B; antisymmetry is the fact that $$B\subseteq C$$B\subseteq C and $$C\subseteq B$$C\subseteq B imply $$B=C$$B=C; transitivity is the fact that $$B\subseteq C$$B\subseteq C and $$C\subseteq D$$C\subseteq D imply $$B\subseteq D$$B\subseteq D.

It is not usually total. If $$A=\{1,2,3\}$$A=\{1,2,3\}, the sets $$\{1,2\}$$\{1,2\} and $$\{1,3\}$$\{1,3\} are not 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.22. Divisibility order on positive integers

On the positive integers, define $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b to mean that $$a$$a divides $$b$$b. This is a partial order半順序関係はんじゅんじょかんけい. But $$2$$2 and $$3$$3 do not divide each other, so they are not comparable. Therefore divisibility is not a 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 が成なり立たつからである。

5.33. Usual numerical order

The usual order $$\text{[PARSE ERROR: Undefined("Command("le")")]}$$\le on $$\mathbb{R}$$\mathbb R is a total order全順序関係ぜんじゅんじょかんけい because for all $$a,b\in \mathbb{R}$$a,b\in\mathbb R, either $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b or $$b\text{[PARSE ERROR: Undefined("Command("le")")]}a$$b\le a.

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

6Worked example: partial but not total

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.1Problem

Let $$A=\{1,2,3\}$$A=\{1,2,3\}, and define an order on $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) by

Show that this is a partial order半順序関係はんじゅんじょかんけい but not a 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ではない。

6.2Explanation

Reflexivity holds because $$B\subseteq B$$B\subseteq B for every $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A).

Antisymmetry holds because $$B\subseteq C$$B\subseteq C and $$C\subseteq B$$C\subseteq B imply $$B=C$$B=C by extensionality外延性がいえんせい of sets.

Transitivity holds because $$B\subseteq C$$B\subseteq C and $$C\subseteq D$$C\subseteq D imply $$B\subseteq D$$B\subseteq D. Thus inclusion on $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) is a partial order.

However, $$\{1,2\}$$\{1,2\} and $$\{1,3\}$$\{1,3\} are not comparable because neither contains the other. Hence the order is not total.

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 元げんがないかを確認かくにんする。

7Recognition criteria

• If the comparison relation satisfies reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, and transitivity推移性すいいせい, suspect a partial order半順序関係はんじゅんじょかんけい.
• If every two elements元げん are comparable, the order is a total order全順序関係ぜんじゅんじょかんけい.
• A single incomparable pair is enough to show that an order is not a total order全順序関係ぜんじゅんじょかんけい.
• Do not confuse an equivalence relation同値関係どうちかんけい with an order relation. Equivalence relations use symmetry対称性たいしょうせい, while order relations use antisymmetry反対称性はんたいしょうせい.

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 が成なり立たつからである。

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

8Proof supplement: restricting an order to a subset preserves the order

Let $$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) be a partially ordered set半順序集合はんじゅんじょしゅうごう, and let $$Y\subseteq X$$Y\subseteq X. Define a relation on $$Y$$Y by

Then $$(Y,{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y)$$(Y,\le_Y) is also a partially ordered set半順序集合はんじゅんじょしゅうごう.

Reflexivity反射性はんしゃせい follows because every $$y\in Y$$y\in Y is also an element of $$X$$X, so $$y\text{[PARSE ERROR: Undefined("Command("le")")]}y$$y\le y holds in $$X$$X. Antisymmetry反対称性はんたいしょうせい follows because $$y_1{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y{y}_2$$y_1\le_Y y_2 and $$y_2{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y{y}_1$$y_2\le_Y y_1 mean $$y_1\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_2$$y_1\le y_2 and $$y_2\text{[PARSE ERROR: Undefined("Command("le")")]}{y}_1$$y_2\le y_1 in $$X$$X, hence $$y_1=y_2$$y_1=y_2. Transitivity推移性すいいせい is inherited in the same way from $$X$$X.

Furthermore, if $$(X,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(X,\le) is a totally ordered set全順序集合ぜんじゅんじょしゅうごう, then $$(Y,{\text{[PARSE ERROR: Undefined("Command("le")")]}}_Y)$$(Y,\le_Y) is also totally ordered, because any two elements of $$Y$$Y are also elements of $$X$$X and are therefore comparable.

This proof shows that restricting an order to a smaller set集合しゅうごう does not break the order axioms.

9演習えんしゅうリンク

9Exercise links

10関連かんれんリンク

10Related links