偏序

偏序表达的是“某些对象之间有先后或包含关系”，而不是“每两个对象都必须排出高低”。对软件构建，依赖项必须先完成，但两个互不依赖的模块可以任选顺序；对集合，$\{a\}\subseteq \{a,b\}$，而 $\{a\}$ 与 $\{b\}$ 谁也不包含谁。

这些不可比并不是我们尚未查明一个隐藏的大小关系，而是模型本身没有要求两者排序。把偏序扩展成执行用的线性顺序可以方便调度，但扩展后额外决定的先后不应被反过来当作原始依赖。

有限偏序常用 Hasse 图表示：当 $x<y$，且没有 $z$ 严格夹在两者之间时，画一条从较低的 $x$ 连到较高的 $y$ 的边，称 $y$ 覆盖 $x$。图中省去自反关系和可由传递性恢复的边，因此每条边只表示一步不可再分的上升。

同一“排在前面”可以来自不同含义 ​

幂集 $\mathcal{P}(S)$ 上的包含关系是偏序：每个集合包含自己，互相包含则相等，包含还具有传递性。正整数上的整除关系 $a\mid b$ 也是偏序：例如 $2\mid 6$，但 $2,3$ 不可比。它表达因子关系，不等同于通常的数值大小。

若把整除关系放到所有整数上，反对称就失效了：$2\mid -2$ 且 $-2\mid 2$，但 $2\ne -2$。去除这一歧义的一种方式是回到正整数，另一种是把互相整除的整数识别为同一等价类。能否称为偏序，要连同论域一起检查。

不可比也不具有传递性。取 $A=\{1\}$、$B=\{2\}$、$C=\{1,3\}$，则 $A$ 与 $B$ 不可比，$B$ 与 $C$ 不可比，但 $A⊊C$。因此不可比不能直接拿来当作把对象分组的等价关系。

最大元与极大元的量词不同 ​

对 $S\subseteq P$，最大元 $m\in S$ 要满足每个 $s\in S$ 都有 $s\le m$；极大元 $m\in S$ 只要求不存在 $s\in S$ 使 $m<s$。前者位于所有元素之上，后者只保证无法在 $S$ 内继续向上走。

在整除偏序的子集 $S=\{2,3,6,10\}$ 中，$6$ 和 $10$ 都是极大元，但没有最大元：两者互不整除。每个最大元都是极大元，并且最大元若存在只能有一个；非空有限偏序一定有极大元，却未必有最大元。

从任一元素出发，只要还不是极大元，就选一个严格更大的元素；传递性保证途中不重复，有限性保证必须停下。无限偏序不能沿用这个停止理由，自然数的通常次序就可以一直上升。极小元与最小元是完全对偶的概念。

上界则不要求属于 $S$。在正整数整除偏序中，$S=\{6,10\}$ 的上界是共同倍数，最小上界为 $30$，但 $30\notin S$。因此“最小上界”也不能直接替换成“最大元”。

预序、可达性与压缩 ​

若关系只满足自反与传递，就称为预序。令 $x\sim y$ 当且仅当 $x\le y$ 且 $y\le x$，可以证明 $\sim$ 是等价关系；将等价元素组成商集理路商集Quotient set · Set of equivalence classes等价关系的所有等价类组成的集合。后，定义 $[x]⪯[y]⟺x\le y$，便得到良定义的偏序。商掉的正是违反反对称性的双向可达部分。

有向图理路有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。中的可达关系（允许长度 $0$ 的路径）就是预序。存在有向环时，不同顶点可以互相到达；把每个强连通分量缩成一个点，分量之间的可达关系便成为偏序。对于 DAG，原顶点上的可达关系已经满足反对称性，无须这一步压缩。

覆盖关系的 Hasse 图主要适用于有限偏序，不能无条件推广成所有偏序的完整表示。在 $\mathbb{Q}$ 的通常序中，任意 $x<y$ 之间都有 $(x+y)/2$，所以没有覆盖边；显然不能从一张无边图恢复全部大小关系。

链与反链描述两种不同的组织方式 ​

链是任意两元素都可比的子集，反链是任意两不同元素都不可比的子集。对任务依赖而言，链反映必须依次经过的步骤，反链反映没有相互先后约束的一组任务；实际能否并行还取决于机器数量等资源，并非只由不可比性决定。

有限偏序可以通过不断取一个极小元、输出并删除它，得到与原偏序相容的线性排列，即线性扩张。对应到 DAG，就是拓扑排序。一次具体执行顺序增加了可比关系，却没有改变原模型中哪些步骤真正依赖哪些步骤。

结构保持、极值存在与格 ​

映射 $f:P\to Q$ 若满足 $x\le y\Rightarrow f(x)\le f(y)$，称为保序映射。它保留已有比较，但未必反映比较：常值映射保序，却把很多不同元素压成一个值。

如果任意两个元素都有最小上界和最大下界，就得到格；在幂集偏序中，它们分别是并集与交集。无限偏序的极大元存在问题则需要额外条件，Zorn 引理给出“每条链有上界”时存在极大元的原则，不能把有限情形中不断向上走终会停止的理由直接搬到无限情形。

在并发系统中，happens-before 通常以严格偏序表达因果先后。日志中的一个全序时间线可能只是其中一个线性化排列；它额外排定的不可比事件，不应自动解释成因果关系。

良拟序理路良拟序Well quasi order · WQO用每条无限序列中的顺向可比对定义良拟序，证明向上闭集有限基和增长链终止，并辨别良基与良拟序。不要求反对称，但要求每条无限序列中出现顺向可比对。它既排除无限严格下降链，也排除无限反链，因此比单纯良基性更强；其向上闭集有限基性质，是把无限状态集合压缩成有限阈值清单的关键。

标号偏序分拆理路标号偏序分拆与主指标生成函数Labeled P-partition · (P, omega)-partition · P-partition fundamental theorem · Major-index shuffle theorem以相等值的标签顺序唯一分解偏序分拆，推导线性扩张的主指标分子，并对任意互异标签的两条词证明洗牌公式。把反序整数赋值按唯一线性扩张分组，并用扩张的下降位置之和给出生成函数分子。若每个值只允许取 $1,\dots ,m$，序多项式理路序多项式与严格计数互反Order polynomial · Order polynomial reciprocity · Strict order polynomial · Stanley order reciprocity以线性扩张的下降展开计算有限偏序保序映射，证明次数及首系数，再用互补标号和负二项式得到弱严格互反。分别计数弱保序与严格保序映射，证明 ${\mathrm{\Omega }}_P^{\circ }(m)=(-1{)}^{|P|}{\mathrm{\Omega }}_P(-m)$；不可比元素在严格版本中仍能同值，不能把它误读成全部值互异。