Total Order

定义 Definition

全序（全序关系）：一种“排序”关系，在某个集合上满足：

自反性：任意 \(a\) 都有 \(a \le a\)；
反对称性：若 \(a \le b\) 且 \(b \le a\)，则 \(a=b\)；
传递性：若 \(a \le b\) 且 \(b \le c\)，则 \(a \le c\)；
可比性（完全性）：任意 \(a,b\)，必有 \(a \le b\) 或 \(b \le a\)。
常见例子：实数上的“≤”、字典序（在一定规则下）。（在计算机科学中也常说 total order 用来强调“任意两元素都能比较”。）

例句 Examples

Integers with the usual “≤” form a total order.
整数在通常的“≤”关系下构成一个全序。

To guarantee deterministic results, the algorithm imposes a total order on events by sorting them by timestamp and then by ID.
为保证结果确定性，该算法通过先按时间戳、再按编号排序，对事件施加一个全序。

发音 Pronunciation (IPA)

/ˈtoʊtəl ˈɔːrdər/

词源 Etymology

total 来自拉丁语 totus（“全部的、整体的”），表示“覆盖所有情况”；order 来自拉丁语 ordo（“排列、秩序”）。合起来的 total order 字面意思是“完全的排序/秩序”，对应数学里“任意两元素都可比较”的排序关系。

文献作品 Literary Works

Naive Set Theory（Paul R. Halmos）
Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）
The Art of Computer Programming（Donald E. Knuth）
Introduction to Lattices and Order（B. A. Davey & H. A. Priestley）