偏序

偏序是集合上的一种二元关系，用于描述一种不要求任意两个元素都可比较的次序。它具有自反性、反对称性和传递性。配备这种关系的集合称为偏序集，英文简称为 poset。与数值排名不同，偏序可以表示具有分支的层级结构，以及不规定某些元素之间次序的约束。(lara.epfl.ch)

定义与相关关系

设 $P$ 为一个集合，$\leq$ 为 $P$ 上的关系。如果对所有 $x,y,z\in P$，该关系都满足以下三条公理，则称其为偏序：

• 自反性： $x\leq x$。
• 反对称性： 若 $x\leq y$ 且 $y\leq x$，则 $x=y$。
• 传递性： 若 $x\leq y$ 且 $y\leq z$，则 $x\leq z$。

记号 $(P,\leq)$ 同时指明了底层集合及其上的序关系。当两个元素相等时，反对称性并不禁止两个方向的比较关系同时成立。(lara.epfl.ch)

如果 $x\leq y$ 或 $y\leq x$，则称这两个元素可比较；否则称其不可比较。全序也称线性序，是任意两个元素都可比较的偏序。因此，“偏”意味着允许存在不可比较的元素，而不是要求一定存在这样的元素。实数上的通常序关系就是全序。(math.mit.edu)

与偏序对应的严格序定义为

它具有非自反性和传递性。反过来，将相等关系加入一个具有非自反性和传递性的关系，就得到一个偏序。(lara.epfl.ch)

例子与构造

在集合论中，包含关系为幂集 $\mathcal P(S)$ 赋予偏序：$A\leq B$ 表示 $A\subseteq B$。当 $S=\{a,b\}$ 时，子集 $\{a\}$ 与 $\{b\}$ 不可比较，但它们都位于空集之上、$S$ 之下。(lara.epfl.ch)

整除关系为正整数赋予偏序：$a\leq b$ 表示 $a\mid b$。例如，$2$ 与 $3$ 不可比较，但二者都排在 $6$ 之前。将这一关系限制在 $12$ 的正因数上，就得到一个由 $1,2,3,4,6,12$ 构成的有限偏序集。(math.mit.edu)

两个偏序集的笛卡尔积上可以定义积序：

因此，对于数值坐标，$(1,3)$ 与 $(2,2)$ 不可比较。这种序不同于字典序，后者通过第一个不同的坐标来进行比较。(math.mit.edu)

将所有比较关系的方向反转，就得到对偶序，其定义为：$x\leq_{\mathrm{op}}y$ 当且仅当 $y\leq x$。对偶性使有关上界与下界、最大元与最小元的命题相互对应。(math.hawaii.edu)

哈斯图、链与反链

有限偏序集通常用哈斯图表示。如果 $x<y$，且不存在满足 $x<z<y$ 的元素 $z$，则称元素 $y$ 覆盖 $x$。图中将 $y$ 放在 $x$ 上方，并在这一覆盖条件成立时将二者连线。自反的比较关系以及可由传递性推得的比较关系均省略不画。(math.mit.edu)

在有限偏序集中，$x<y$ 当且仅当存在一条从 $x$ 向上通往 $y$ 的路径。将这一描述用于无限序时需要谨慎：实数上的通常序关系没有任何覆盖对，因为任意两个不同的实数之间都存在另一个实数。(math.mit.edu)

链是元素两两可比较的子集。反链是任意两个不同元素都不可比较的子集。对于有限偏序集，其高度通常定义为链所能包含的最大元素数，其宽度则定义为反链所能包含的最大元素数。有些作者改用步数来衡量链的长度。狄尔沃斯定理指出，宽度等于将该偏序集划分为若干条链所需的最少链数。(math.mit.edu)

极值元素与界

如果不存在严格小于 $m$ 的元素，则称 $m$ 为极小元；如果对每个 $x\in P$ 都有 $m\leq x$，则称 $m$ 为最小元。对偶地，如果不存在严格大于某个元素的元素，则称它为极大元；如果它大于或等于所有元素，则称它为最大元。极小元或极大元可能有多个，但最小元或最大元一旦存在，就必定唯一。(lara.epfl.ch)

对于子集 $A\subseteq P$，上界是大于或等于 $A$ 中每个元素的元素。在上确界与下确界中，上确界是最小上界，下确界是最大下界。界不一定属于 $A$，而且即使一个子集有界，也不一定存在上确界或下确界。(scss.tcd.ie)

格是一种偏序集，其中任意两个元素都有上确界和下确界，分别称为这两个元素的并与交。完全格的每个子集都有上确界和下确界，包括空子集。按包含关系排序的幂集是完全格：并运算是集合的并集，交运算是集合的交集。再配以补集运算，它们也是布尔代数的标准例子。(math.hawaii.edu)

线性扩张与计算

线性扩张是保留原偏序集中所有比较关系的全序。每个有限偏序集都有线性扩张，不过不可比较的元素往往可以按任一先后次序排列，从而产生多个扩张。(math.mit.edu)

在图论中，有向无环图通过可达关系加上相等关系定义一个偏序。它的传递闭包记录间接依赖关系。拓扑排序算法将每个顶点排在其后继之前，从而构造出一个线性扩张。这使得任务可以按照前置条件约束进行调度，而不必事先规定独立任务之间的次序。对于顶点集为 $V$、边集为 $E$ 的图，标准实现的运行时间为 $O(|V|+|E|)$。(cs.cornell.edu)