偏序

偏序允许结构分叉。两个任务都依赖同一个前置任务，却彼此没有先后；两个集合各自含有对方没有的元素；两份信息沿不同方向变得更精细——这些情形都不能诚实地压成一条数轴。若既无 $x⪯y$ 也无 $y⪯x$，称 $x,y$ 不可比。不可比不是“完全没有语义关系”，只表示当前这一个次序没有选定方向。

有限偏序常用 Hasse 图压缩表示。若 $x\prec y$ 且不存在 $z$ 满足 $x\prec z\prec y$，称 $y$ 覆盖 $x$，记作 $x⋖y$。Hasse 图只画覆盖边，省略自环、箭头和由传递性强制出的长边；把向上的覆盖路径取传递闭包即可恢复原偏序。对稠密次序如 $\mathbb{Q}$ 上的通常次序，任意 $x<y$ 之间还有元素，根本没有覆盖边，因此 Hasse 图方法主要适合有限或局部有限偏序。

链是其中任意两元素都可比的子集，反链则是任意两个不同元素都不可比的子集。偏序的“高度”和“宽度”分别由链与反链刻画；链与反链定理公理库链与反链Chain and antichain偏序集中任意两元素可比的子集与任意两不同元素不可比的子集。研究二者之间的精确约束。把整个 $P$ 都要求为一条链，才得到全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。。

$\mathcal{P}(S)$ 在包含关系下构成偏序。若 $S=\{a,b,c\}$，则 $\{a\}$ 与 $\{b\}$ 不可比，二者都被 $\{a,b\}$ 覆盖；完整 Hasse 图是一个三维布尔立方体。注意最小元 $\varnothing$ 和最大元 $S$ 各自唯一，而极小元、极大元在一般子偏序中可以有多个。最大元必须大于等于所有元素；极大元只要求没有严格更大的元素，这两个概念不能混用。

正整数在整除关系下也是偏序：$2$ 与 $3$ 不可比，$2\mid 6$ 且 $3\mid 6$。若论域扩为所有非零整数，$1\mid -1$ 且 $-1\mid 1$，但二者不相等，所以这里只得到预序。可以限制到正整数，或按相差一个单位因子的伴随类取商，恢复反对称性。这正是预序商构造的具体例子。

有向图中的可达关系自反且传递，但位于同一强连通分量的不同顶点互相可达，通常不反对称。把强连通分量收缩为单点后得到有向无环图，其可达关系才是偏序。字符串前缀关系则直接反对称；实数上的 $<$ 是严格全序，而“认识”关系通常既不传递也不反对称。

不可比性本身通常不传递。集合 $A=\{1\}$ 与 $B=\{2\}$ 不可比，$B$ 与 $C=\{1\}$ 也不可比，但 $A=C$ 当然可比。因此不能把偏序集简单分割成若干“互不可比等价类”。

每个偏序都可反向得到对偶序：$x{⪯}^{\mathrm{op}}y$ 当且仅当 $y⪯x$。因此关于极小元的命题常与关于极大元的命题成对出现。Zorn 引理公理库佐恩引理Zorn's lemma若偏序集中每条链都有上界，则该偏序集存在极大元。从每条链都有上界推出极大元存在；它讨论的是极大而非最大，量词差别在这里至关重要。

保序映射公理库偏序集上的单调映射Monotone map on posets · Order-preserving map · Isotone map在偏序之间保持次序的映射，以及它作为单调算子参与不动点迭代时的基本结构。保持比较方向，格公理库格Lattice · Lattice order任意两元素都有最大下界与最小上界的偏序集。进一步要求每对元素都有并与交意义下的上确界和下确界，完备格公理库完备格Complete lattice · Complete ordered lattice任意子集都具有上确界和下确界，从而包含顶元、底元并支持任意族合流的格。再把要求扩展到任意子集。偏序只提供“可比较到什么程度”的骨架，并不自动提供这些上下确界。

依赖调度会为偏序选择一个与之相容的线性扩张，也就是把不可比任务按某种方式排成全序，同时保留所有原有先后约束。这个全序便于执行，却不应反过来被解释为原任务之间本来就有依赖；不可比元素正是潜在并行性所在。

happens-before公理库Happens-before 关系Happens-before · Causal order由程序顺序及模型规定的通信或同步边生成的事件因果严格偏序。由具体执行中的程序顺序与通信边生成因果次序，Mazurkiewicz trace公理库Mazurkiewicz traceMazurkiewicz trace · Trace monoid · Partially commutative word以独立动作的相邻交换对执行词取商，使一个 trace 表示同一因果偏序的全部交错。则先规定动作独立性，再把可交换的相邻动作序列取商。两者都产生偏序图像，但各自携带额外的并发语义，不是“任意偏序”的同义名。