形式陈述

偏序 $(P,\preceq)$$(P,⪯)$ 是全序，当且仅当还满足

$$ \forall x,y\in P\;(x\preceq y\lor y\preceq x). $$$$\mathrm{\forall }x,y\in P(x⪯y\vee y⪯x).$$

严格关系可定义为 $x\prec y\iff x\preceq y\land x\ne y$$x\prec y⟺x⪯y\wedge x\ne y$。

直觉

全序把所有元素排成一条线；偏序则可保留分支和不可比性。可比性是额外结构，不由偏序三公理推出。

例子与边界

整数的通常大小关系是全序。集合族上的包含关系通常不是全序，例如 $\{1\}$$\{1\}$ 与 $\{2\}$$\{2\}$ 不可比。字典序可给字符串全序，但结果依赖字母表顺序和前缀规则。

推论与应用

二分查找和比较排序需要可比较的键。拓扑排序只为偏序选择一个线性扩张，并不消除原有依赖结构。

参考资料

• Paul R. Halmos, Naive Set Theory, 1960; Dover reprint 2017, §14。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Relations chapter。