形式陈述

在偏序集 $(P,\le)$$(P,\le )$ 中，子集 $C\subseteq P$$C\subseteq P$ 称为链，若其中任意两元素可比较；子集 $A\subseteq P$$A\subseteq P$ 称为反链，若其中任意两个不同元素不可比较。有限偏序集的高度 $h(P)$$h(P)$ 是最大链大小，宽度 $w(P)$$w(P)$ 是最大反链大小。链分解是把 $P$$P$ 分割为若干链，反链分解类似。极大链是不能再加入元素的链，最大链则具有最大基数；二者不可混同。

直觉

链沿偏序的一条完全可比较方向前进，反链则收集彼此无法排序的并行元素。高度测量最长依赖深度，宽度测量最大并行度。

例子与边界

布尔格 $2^{[n]}$$2^{[n]}$ 中，按包含关系，$\varnothing\subset\{1\}\subset\cdots\subset[n]$$\varnothing \subset \{1\}\subset \cdots \subset [n]$ 是链；所有大小为 $\lfloor n/2\rfloor$$\lfloor n/2\rfloor$ 的子集构成反链。整数整除偏序中，$1,2,4,8$$1,2,4,8$ 是链，而 $2,3,5$$2,3,5$ 是反链。全序中的每个子集都是链，最大反链大小为一。极小元集合是反链，但任意反链不必由极小元组成。无限偏序集的高度和宽度可能是无限基数，有限 Dilworth 定理的证明与推广需区分。

推论与应用

链与反链刻画调度依赖、并行执行、数据库偏序和格中的层级结构。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，§§10.5.3–10.6, chains, antichains, and partial orders。
• Garrett Birkhoff, Lattice Theory, 3rd ed., American Mathematical Society, 1967，Ch. I, chains, antichains, and ordered sets。