全順序

半順序では、$\{1\}$ と $\{2\}$ のように一方が他方を包含しない集合同士のように、比較できないペアが存在することがある。でも、数の大小関係にはそういうギャップがない。どんな2つの整数を取っても、必ずどちらが小さいか言える。この強い条件が全順序（ぜんじゅんじょ、total order）だ。

完全性公理

半順序 $(S, \leq)$ は、$\leq$ が反射的・反対称的・推移的であることを要求する。全順序（線形順序とも呼ばれる）は、さらにもう一つの条件を加える：

$$\forall a, b \in S,\quad a \leq b \;\text{ または }\; b \leq a \tag{完全性}$$

すべての要素のペアが比較可能でなければならない――比較できないペアは一つも存在しない。

注意. 完全性は反射性を含意する。$a = b$ とおけば $a \leq a$ が得られる。そのため、全順序を反対称性・推移性・完全性だけを満たす関係として定義する流儀もある。反射性の公理は自動的に従う。

定義

$\leq$ が（完全性）を満たす半順序であるとき、ペア $(S, \leq)$ を全順序集合（または線形順序集合）と呼ぶ。

三分律

完全性を（反対称性と推移性のもとで）同値に言い換えたものが三分律（さんぶんりつ、law of trichotomy）だ。任意の2つの要素 $a$ と $b$ に対して、3つの場合のうちちょうど1つが成り立つ：

$$a < b, \qquad a = b, \qquad \text{または} \qquad b < a \tag{三分律}$$

実際に全順序について論じるとき、三分律は最も自然な方法であることが多い。この3つの排反なケースに場合分けして、それぞれを個別に処理する。

例

$\leq$ による実数

$(\mathbb{R}, \leq)$ は典型的な全順序だ。任意の $a, b \in \mathbb{R}$ に対して、$a < b$、$a = b$、$b < a$ のうちちょうど1つが成り立つ。同じ全性は $(\mathbb{Q}, \leq)$、$(\mathbb{Z}, \leq)$、$(\mathbb{N}, \leq)$ にも適用される。

文字列上の辞書式順序

文字に標準的なアルファベット順を入れたように、全順序が入ったアルファベットを固定しよう。そのアルファベット上の文字列に対する辞書式順序（じしょしきじゅんじょ、lexicographic order）は、2つの文字列を先頭から1文字ずつ比較する。最初に異なる位置を見つけ、そこでアルファベットの順序を使う。一方の文字列が先に終わった場合は、それが前に来る。例えば：

$$\text{"apple"} < \text{"apply"} < \text{"apt"}$$

これにより、同じアルファベット上の任意の文字列集合に全順序が定まる。辞書が使っているのもこの順序だ。

半順序の線形拡張

任意の有限な半順序集合（ポセット）は、それと整合的な全順序に常に拡張できる。元の半順序で $a \leq b$ ならば、全順序でも $a \leq b$ が成り立つようにできる。このような拡張を線形拡張（せんけいかくちょう、linear extension）と呼ぶ。実用的にも便利で、タスクに依存関係（半順序）がある場合、すべての依存関係を守る1本の線形なスケジュールを常に作れる。

反例

$\mathbb{N}$ 上の整除関係

半順序で見たように、整除関係は全順序ではない。$2 \nmid 3$ かつ $3 \nmid 2$ なので、$2$ と $3$ は比較不能だ。

冪集合上の包含関係

$(\mathcal{P}(A), \subseteq)$ は $|A| \geq 2$ の任意の集合 $A$ に対して全順序ではない。$a \neq b$ となる2つの異なる一元集合 $\{a\}$ と $\{b\}$ は比較不能だ。

全順序に固有の性質

完全性公理によって、半順序では保証されない構造的な性質が生まれる。

極小元と最小元の一致

一般のポセットでは、複数の極小元が存在してもその中に最小元がない場合がある――半順序における $\{2, 3, 6\}$ 上の整除関係の例がそれを示している。全順序では、これらの概念が一致する。$m$ が極小元（自分より真に小さいものが存在しない）とすると、任意の $a \in S$ に対して完全性より $m \leq a$ または $a \leq m$ が成り立つ。後者なら $a < m$ となり極小性に矛盾する。よって $m \leq a$ がすべての $a \in S$ に成り立ち、$m$ は最小元となる。

系. 全順序では、極小元は高々1つしか存在せず、存在すれば唯一の最小元となる。同じ議論が極大元と最大元にも適用される。

空でない有限全順序集合には唯一の最小元と最大元が存在する

任意の要素から始めて、集合を走査しながら小さい要素が見つかるたびに置き換えていけば最小元を見つけられる。完全性があるからすべての比較が決定的で、有限性があるから走査が終了する。最後の候補が最小元だ。対称性により最大元も存在する。

全順序のハッセ図は鎖になる

全順序集合のハッセ図（ハッセず）では、各要素に一意な前者と一意な後者が（存在する場合）存在するため、すべての要素が枝分かれなく1本の縦の鎖に並ぶ。この線形な形から、全順序は線形順序とも呼ばれる。

まとめ

• 全順序は、すべての要素のペアが比較可能という完全性公理を加えた半順序だ。
• 同値な言い方として、三分律が成り立つ：任意の $a$ と $b$ に対して、$a < b$、$a = b$、$b < a$ のうちちょうど1つが真である。
• 主な例：$(\mathbb{R}, \leq)$、$(\mathbb{Z}, \leq)$、$(\mathbb{Q}, \leq)$、$(\mathbb{N}, \leq)$、および文字列上の辞書式順序。
• $\mathbb{N}$ 上の整除関係と冪集合上の包含関係は全順序ではない。
• 全順序では、極小元と最小元は一致し、空でない有限全順序集合には唯一の最小元と最大元が存在する。