全順序

概要

集合 $X$ とその上の二項関係 $\le$ の組 $(X, \le)$ が全順序集合（Total Ordered Set）であるとは、それが半順序集合であり、かつ全ての要素が比較可能であること、すなわち以下の4公理を満たすことをいう。

全順序の公理

任意の $a, b, c \in X$ に対して：

この第4の条件により、「比較できないペア」が存在しないことが保証される。また、狭義の不等号 $<$ を用いれば、全順序性は以下の三分律（Trichotomy law）と同値になる。

三分律

任意の $a, b \in X$ に対し、以下のいずれか一つのみが成り立つ。
$$a < b, \quad a = b, \quad a > b$$

全順序と半順序の決定的違いは、構造の「形状」にある。

半順序: 要素関係が分岐したり合流したりする（ハッセ図が平面的な広がりを持つ）。比較不能な元（$a \not\le b$ かつ $b \not\le a$）が存在しうる。
全順序: 要素が分岐せず、一本の鎖（Chain）のように並ぶ。これを強調して線型順序（Linear order）とも呼ぶ。
位相空間論やグラフ理論の文脈では、全順序集合はしばしば単に「鎖（Chain）」と呼ばれる。

全順序は日常的な「数の大小」や「並び順」のモデルである一方、数学的な構造の多くは全順序ではない（半順序にとどまる）ことが多い。

全順序の例

数体系:
自然数 $\mathbb{N}$、整数 $\mathbb{Z}$、有理数 $\mathbb{Q}$、実数 $\mathbb{R}$ は、通常の大小関係 $\le$ に関して全順序集合である。
辞書式順序:
アルファベット順のように、複数の全順序集合の直積上に定義される順序。
例えば $(1, 3) < (2, 1)$ （1文字目で比較）など。

一方で、以下のような構造は半順序ではあるが、全順序ではない。

反例（半順序だが全順序ではない）

集合の包含関係:
集合 $S=\{a, b\}$ の冪集合 $\mathcal{P}(S)$ において、$\{a\}$ と $\{b\}$ はどちらも他方を含まない。
$$\{a\} \not\subseteq \{b\} \quad \text{かつ} \quad \{b\} \not\subseteq \{a\}$$
したがって比較不能であり、全順序ではない。
整除関係:
自然数における「割り切る」関係 $x \mid y$。
$2$ と $3$ は互いに割り切れないため、比較不能である。

半順序と全順序の関係において、極めて重要な定理が存在する。それは「比較できない部分があるなら、適当に順序を追加して無理やり一直線に並べ替えることができる」というものである。

順序拡大原理 (Szpilrajnの拡張定理)

任意の半順序集合 $(P, \le)$ に対して、その順序構造を保存するような全順序 $\le^*$ が存在する。
すなわち、任意の $x, y \in P$ に対し、$x \le y \implies x \le^* y$ となる全順序 $\le^*$ （$P$ 上の線型拡張）が存在する。

この定理の証明には選択公理（あるいはZornの補題）が必要となる。これは、タスクの依存関係（半順序）があるとき、矛盾なくタスクを一列にスケジューリング（全順序化/トポロジカルソート）できることを一般の場合で保証するものである。

順序構造の制約の強さは以下の順になる。

順序の階層

$$\text{前順序} \supset \text{半順序} \supset \textbf{全順序} \supset \text{[[整列順序]]}$$

全順序 $\to$ 整列順序:
全順序集合において、さらに「任意の空でない部分集合が最小元を持つ」という条件を加えると、整列順序（Well-order）となる。
- 例: 自然数 $\mathbb{N}$ は整列順序だが、整数 $\mathbb{Z}$ や実数 $\mathbb{R}$ は（通常の大小関係では）最小元を持たない部分集合があるため、全順序ではあるが整列順序ではない。