全序

在偏序中，某些元素對可以是不可比較的——想像子集 $\{1\}$ 和 $\{2\}$ 並排而立，彼此之間沒有包含關係。但我們熟悉的數字排序沒有這樣的間隙：給定任意兩個整數，你總能說出哪個更小。這個更強的條件就是全序（total order）。

完全性公理

偏序 $(S, \leq)$ 要求 $\leq$ 是自反的、反對稱的且可傳遞的。全序（也稱為線性序（linear order））再添加一個要求：

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

每對元素都必須是可比較的——完全沒有不可比較的對。

注意。 完全性蘊含自反性：令 $a = b$ 得 $a \leq a$。所以在某些表述中，你會看到全序被定義為只滿足反對稱性、可傳遞性和完全性的關係；自反性公理由此免費得到。

定義

數對 $(S, \leq)$ 是全序集（totally ordered set）（或線性序集），當 $\leq$ 是也滿足（完全性）的偏序。

三分律

完全性的一個等價表述（給定反對稱性和可傳遞性）是三分律（law of trichotomy）：對任意兩個元素 $a$ 和 $b$，恰好有三種情形之一成立：

$$a < b, \qquad a = b, \qquad \text{or} \qquad b < a \tag{三分律}$$

三分律通常是在實踐中推理全序的最自然方式：你將論證分支為這三個互斥情形，分別處理每一個。

範例

實數的 $\leq$ 關係

$(\mathbb{R}, \leq)$ 是標準的全序。對任意 $a, b \in \mathbb{R}$，$a < b$、$a = b$、$b < a$ 中恰好有一個成立。同樣的完全性適用於 $(\mathbb{Q}, \leq)$、$(\mathbb{Z}, \leq)$ 和 $(\mathbb{N}, \leq)$。

字串的字典序

固定一個全序字母表——比如說字母的標準字典序。字母表上字串的**字典序（lexicographic order）**逐字元比較兩個字串：找到它們不同的第一個位置，並使用那裡的字母序；若一個字串先耗盡字元，它排在另一個之前。例如：

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

這對同一字母表上的任意字串集合給出全序，這與字典使用的順序相同。

偏序的線性擴展

給定任意有限偏序集，你總能將其擴展為一個與之一致的全序：只要在原偏序中 $a \leq b$，在全序中也有 $a \leq b$。這樣的擴展稱為線性擴展（linear extension）。這在實踐中很有用：若任務有依賴順序（偏序），你總能將它們安排在一個尊重所有依賴關係的單一線性序列中。

反例

$\mathbb{N}$ 上的整除性

如偏序中所見，整除性不是全序：$2 \nmid 3$ 且 $3 \nmid 2$，所以 $2$ 和 $3$ 是不可比較的。

冪集上的子集包含

對任意集合 $A$，若 $|A| \geq 2$，$(\mathcal{P}(A), \subseteq)$ 不是全序：任意兩個不同的單元素集 $\{a\}$ 和 $\{b\}$（其中 $a \neq b$）都是不可比較的。

全序特有的性質

完全性公理開啟了偏序所不保證的結構性質。

極小元素與最小元素重合

在一般偏序集中，偏序集可以有多個極小元素而其中沒有最小元素——偏序中 $\{2, 3, 6\}$ 上的整除例子說明了這一點。在全序中，這兩個概念合而為一：若 $m$ 是極小的（其下方沒有嚴格更小的元素），則對每個 $a \in S$，完全性給出要麼 $m \leq a$ 要麼 $a \leq m$；後者將使 $a < m$，與極小性矛盾。因此對所有 $a \in S$，$m \leq a$，意味著 $m$ 是最小元素。

推論。 在全序中，最多有一個極小元素，若它存在，則是唯一的最小元素。同樣的推論適用於極大元素和最大元素。

每個非空有限全序集都有唯一的最小值和最大值

你可以從任意元素開始，在掃描集合時不斷用更小的元素替換它來找到最小值。完全性確保每次比較都是決定性的；有限性確保掃描會終止。最終的候選者就是最小值。對稱地，最大值也存在。

全序的哈斯圖是鏈

在全序集的哈斯圖中，每個元素都有唯一的前驅和唯一的後繼（若它們存在），所以所有元素排列在一條沒有分支的單一垂直鏈上。這種線性形狀就是全序也被稱為線性序的原因。

摘要

• 全序是具有額外完全性公理的偏序：每對元素都是可比較的。
• 等價地，三分律成立：對任意 $a$ 和 $b$，$a < b$、$a = b$、$b < a$ 中恰好有一個為真。
• 關鍵範例：$(\mathbb{R}, \leq)$、$(\mathbb{Z}, \leq)$、$(\mathbb{Q}, \leq)$、$(\mathbb{N}, \leq)$ 和字串的字典序。
• $\mathbb{N}$ 上的整除性和冪集上的子集包含不是全序。
• 在全序中，極小元素與最小元素重合；每個非空有限全序集都有唯一的最小值和最大值。