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

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.

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 for arbitrary $$a,b,c\in P$$a,b,c\in P.

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全順序関係ぜんじゅんじょかんけい.

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.

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.

5Representative examples

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

6Worked example: partial but not total

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

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反対称性はんたいしょうせい.

An incomparable pair disproves totality, not the partial-order axioms. For antisymmetry, instead look for two distinct elements related in both directions.

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.

9Exercise links

10Related links