偏序

當你將一列數字從小到大排序時，你依賴的是一種順序關係。但排序的概念遠比這更廣：你可以按包含關係排序子集、按依賴關係排序任務、按整除性排序整數。所有這些背後的抽象結構就是偏序（partial order）——一個精確的數學概念，表示「先於或等於」，甚至允許某些元素對之間不可比較。

二元關係

在定義順序之前，你需要一種討論集合元素之間關係的方式。關鍵要素是笛卡兒積（Cartesian product）。

給定集合 $A$ 和 $B$，它們的笛卡兒積 $A \times B$ 是所有有序對 $(a, b)$（其中 $a \in A$ 且 $b \in B$）所構成的集合：

$$A \times B \;\coloneqq\; \{(a, b) \mid a \in A,\; b \in B\}$$

例如，$\{1, 2\} \times \{x, y\} = \{(1,x),\,(1,y),\,(2,x),\,(2,y)\}$。

集合 $S$ 上的**二元關係（binary relation）**是任意子集 $R \subseteq S \times S$。當 $(a, b) \in R$ 時，稱「$a$ 與 $b$ 有關係」，記作 $a \mathbin{R} b$。關係描述哪些有序對被 $R$ 所編碼的規則「聯繫」起來。

熟悉的範例：

• $\mathbb{Z}$ 上通常的 $\leq$：有序對 $(2, 5)$ 屬於該關係，因為 $2 \leq 5$。
• $\mathbb{N}$ 上的整除性：$a \mid b$ 表示 $\exists\, k \in \mathbb{N}$ 使得 $b = k \cdot a$。
• 冪集上的集合包含：有序對 $(\{1\}, \{1, 2\})$ 屬於該關係，因為 $\{1\} \subseteq \{1, 2\}$。

三個關鍵性質

並非所有二元關係都是順序。一個順序關係必須滿足三個結構條件。

自反性（Reflexivity）。 每個元素與自身有關係：

$$\forall a \in S,\quad a \leq a$$

反對稱性（Antisymmetry）。 若 $a \leq b$ 且 $b \leq a$，則 $a$ 與 $b$ 必須相等：

$$\forall a, b \in S,\quad a \leq b \;\text{ and }\; b \leq a \;\Longrightarrow\; a = b$$

這排除了循環：兩個不同的元素不能同時各自「低於」對方。

可傳遞性（Transitivity）。 若 $a \leq b$ 且 $b \leq c$，則 $a \leq c$：

$$\forall a, b, c \in S,\quad a \leq b \;\text{ and }\; b \leq c \;\Longrightarrow\; a \leq c$$

這捕捉了順序關係沿比較鏈「傳播」的概念。

偏序的定義

$S$ 上的偏序（partial order）是 $S$ 上一個自反、反對稱且可傳遞的二元關係 $\leq$。數對 $(S, \leq)$ 稱為偏序集（partially ordered set），簡稱 poset。

符號 $\leq$ 是慣例，但任何滿足這三個公理的二元關係都是偏序，無論使用何種記號。

嚴格偏序

從任意偏序 $\leq$，可以得到一個伴隨的嚴格偏序（strict partial order） $<$，定義為：

$$a < b \;\coloneqq\; a \leq b \;\text{ and }\; a \neq b$$

嚴格版本是非自反的（對所有 $a$，$a \not< a$）和非對稱的（$a < b \Rightarrow b \not< a$）。兩個版本互相決定，所以你可以透過給出 $\leq$ 或 $<$ 中的任一個來指定偏序。

範例

整數的 $\leq$ 關係

$(\mathbb{Z}, \leq)$ 是最熟悉的偏序。自反性（$n \leq n$）、反對稱性（若 $m \leq n$ 且 $n \leq m$ 則 $m = n$）和可傳遞性（若 $m \leq n$ 且 $n \leq p$ 則 $m \leq p$）都成立。在這個例子中，每對整數都是可比較的：給定任意 $m, n \in \mathbb{Z}$，要麼 $m \leq n$ 要麼 $n \leq m$。

包含關係下的冪集

設 $A$ 為任意集合，$\mathcal{P}(A)$ 表示其冪集——$A$ 的所有子集的集合。則 $(\mathcal{P}(A), \subseteq)$ 是一個偏序。

取 $A = \{1, 2, 3\}$，考慮子集 $\{1, 2\}$ 和 $\{2, 3\}$：兩者都不包含另一個，所以它們在 $\subseteq$ 下是不可比較的。這在 $(\mathbb{Z}, \leq)$ 中不會發生。

正整數的整除性

定義 $a \mid b$（「$a$ 整除 $b$」），若存在 $k \in \mathbb{N}$ 使得 $b = k \cdot a$。則 $(\mathbb{Z}_{>0},\; \mid)$ 是偏序：

• 自反性： $a \mid a$，因為 $a = 1 \cdot a$。✓
• 反對稱性： 對正整數，若 $a \mid b$ 且 $b \mid a$，則 $a = b$。✓
• 可傳遞性： 若 $a \mid b$ 且 $b \mid c$，寫 $b = j \cdot a$ 和 $c = k \cdot b$；則 $c = (kj) \cdot a$，所以 $a \mid c$。✓

然而 $2$ 和 $3$ 不可比較：$2 \nmid 3$ 且 $3 \nmid 2$。

哈斯圖

對有限偏序集，**哈斯圖（Hasse diagram）**提供了簡明的視覺摘要：

• 將每個元素畫為一個帶標籤的點。
• 每當 $a < b$ 時，將 $b$ 置於 $a$ 上方。
• 從 $a$ 向上到 $b$ 畫一條線段，當且僅當 $a < b$ 且沒有 $c$ 使得 $a < c < b$（這些稱為覆蓋關係）。
• 省略已由可傳遞性暗示的線條。

對 $\{1, 2, 3, 6\}$ 上的整除序，圖中 $1$ 在底部，$2$ 和 $3$ 在中間（各自透過一條線與 $1$ 相連），$6$ 在頂部（與 $2$ 和 $3$ 相連）。從 $1$ 到 $6$ 的線省略了，因為它由 $1 < 2 < 6$ 的可傳遞性推出。

可比較與不可比較的元素

$S$ 中兩個元素 $a, b$ 是可比較的（comparable），若 $a \leq b$ 或 $b \leq a$。若兩者都不成立，則它們是不可比較的（incomparable），有時記作 $a \parallel b$。

在 $(\mathbb{Z}, \leq)$ 中，每對元素都是可比較的。在 $(\mathcal{P}(\{1,2\}), \subseteq)$ 中，單元素集 $\{1\}$ 和 $\{2\}$ 是不可比較的。「偏序」中的「偏」字正是指此：不是每對元素都需要可比較。當每對元素都可比較時，結果就是一個更強的概念——全序，你將在下一個檢查點中遇到它。

極小、極大、最小與最大元素

這四個術語容易混淆；以下是它們的精確含義。

元素 $m \in S$ 是極小的（minimal），若 $S$ 中沒有嚴格低於它的元素：

$$\nexists\, a \in S \text{ with } a < m$$

元素 $M \in S$ 是極大的（maximal），若 $S$ 中沒有嚴格高於它的元素：

$$\nexists\, a \in S \text{ with } M < a$$

$S$ 的最小元素（least element）（或最小值）是低於每個其他元素的元素 $m_0$：

$$\forall a \in S,\quad m_0 \leq a$$

$S$ 的最大元素（greatest element）（或最大值）是高於每個其他元素的元素 $M_0$：

$$\forall a \in S,\quad a \leq M_0$$

關鍵區別。 最小元素自動是極小的，但極小元素不一定是最小元素。一個偏序集可以有多個極小元素，而其中沒有最小元素。

範例。 考慮 $S = \{2, 3, 6\}$ 上的整除序。元素 $2$ 和 $3$ 都是極小的（$S$ 中沒有元素嚴格整除它們中的任一個），但沒有最小元素——$2$ 和 $3$ 不可比較，所以兩者都不是 $\leq$ 另一個。元素 $6$ 既是極大的又是唯一的最大元素，因為 $2 \mid 6$ 且 $3 \mid 6$。

最小元素若存在，由反對稱性唯一確定；最大元素也同樣。

摘要

• 笛卡兒積 $A \times B = \{(a, b) \mid a \in A, b \in B\}$ 封裝有序對。集合 $S$ 上的二元關係是 $S \times S$ 的任意子集。
• $S$ 上的偏序 $\leq$ 是自反的、反對稱的且可傳遞的；數對 $(S, \leq)$ 是偏序集。
• 伴隨的嚴格偏序 $<$ 定義為 $a < b \coloneqq a \leq b$ 且 $a \neq b$。
• 關鍵範例：$(\mathbb{Z}, \leq)$、$(\mathcal{P}(A), \subseteq)$ 和正整數上的整除性。
• 元素可以是可比較的（一個 $\leq$ 另一個）或不可比較的（兩者都不成立）。
• 最小（最大）元素是 $\leq$（$\geq$） $S$ 中每個元素的元素，且是唯一的；極小（極大）元素僅是其下方（上方）沒有嚴格更小（更大）的元素，且不必唯一。