在之前的一篇博文 Sperner Theorem 中，笔者写过幂集上的 Sperner 定理，然而组合数学中对于偏序集性质的研究远不止如此；所以，本文的讨论对象将不再局限于 $\subseteq$ 关系下的幂集，而是一般的偏序集，进而讨论链与反链的两个微妙的对偶定理.

链与反链

设 $(X,\leq)$ 是有限偏序集，我们可以定义链与反链如下：

1. 链：$X$ 的一个子集 $C$ ，且其任意两个元素间都存在序关系（可比较）；
2. 反链：$X$ 的一个子集 $A$，且其任意两个元素都不存在序关系（不可比较）；

显然，我们可以得知：

1. 链 $C$ 是 $X$ 的一个全序子集，即 $C$ 的全部元素可以被全序化（以序关系 $\leq$ 线性排列）；
2. 链的子集仍是链；
3. 反链的子集仍是反链；
4. 若 $A$ 和 $C$ 分别是 $X$ 的反链和链，则 $\lvert A \cap C \rvert \leq 1$；

极小元与极大元

设 $(X,\leq)$ 是有限偏序集，称某个元素 $a \in X$ 为极小元，当且仅当：不存在 $x \in X$，使得 $x < a$ ；同理，称某个元素 $b \in X$ 为极大元，当且仅当：不存在 $x \in X$，使得 $b < x$ ；

我们很容易得知：

偏序集的所有极大元（极小元）构成一个反链；

最大链，最大反链，偏序集的宽和高

链 $C$ 包含元素个数不少于任意其他链 $C'$ ，则 $C$ 是最大链；

反链 $A$ 包含元素个数不少于任意其他链 $A'$ ，则 $A$ 是最大反链；

偏序集 $X$ 的最大链的大小称为偏序集 $X$ 的高；

偏序集 $X$ 的最大反链的大小称为偏序集 $X$ 的宽；

Dual of Dilworth's theorem (Mirsky's theorem)

Statement:

设 $(X,\leq)$ 是有限偏序集，将 $X$ 分划成反链集族，则分划得到的反链的最小数目等于 $X$ 的高.

Proof

设 $X$ 的高为 $h$，即 $X$ 的最大链 $C$ 包含的元素数目为 $h$ . 设分划的反链最小数目为 $r$ .

首先，容易证明 $r \geq h$：可先假设命题不成立，则由抽屉原理已知必定存在两个属于 $C$ 的元素将分配到同一个反链中，与定义矛盾；

再构造性地证明 $r \leq h$ 如下.

1. 令 $X_1=X$，$i=1$；
2. 令 $A_i=\{x \in X_i | \ x \,\text{是}\, A_i \text{的极小元}\}$；
3. 令 $X_{i+1}=X_i - A_i$；
4. 若 $X_{i+1}=\varnothing$ ，终止；
   否则，令 $i++$，回到步骤2；

经过有限步之后，我们就这样把 $X$ 分划成一列集合：

注意到，在每一步 $A_i$ 的构造中，$A_i$ 都是 $X_i$ 的全体极小元组成的，所以上面的集合 $\{A\}$ 每一个都是反链——于是我们通过这样的分划，已经将原偏序集分划为 $n$ 个反链，从而 $n \geq r$.

另外，我们可以得知：

如若不然，则 $x$ 在 $X_j$ 中已经是极小元，根本不会被分划到 $A_{j+1}$ 中去；

所以，根据上式以及 $A_n$ 非空的事实，我们可以得到一条链：

其中，$a_i$ 对应地属于 $A_i$，而 $X$ 的高为 $h$，从而 $h \geq n$.

由 $h \geq n$ 且 $n\geq r$ 可得出 $h \geq r$.

综合可知，$r=h$.

Q.E.D.

Dilworth's theorem

Statement

设 $(X,\leq)$ 是有限偏序集，将 $X$ 分划成链集族，则分划得到的链的最小数目等于 $X$ 的宽.

Proof

设 $X$ 的宽为 $w$，即 $X$ 的最大反链 $A$ 包含的元素数目为 $w$ . 设分划的链最小数目为 $s$ .

首先，容易证明 $s \geq w$：可先假设命题不成立，则由抽屉原理已知必定存在两个属于 $A$ 的元素将分配到同一个链中，与定义矛盾；

接下来我们需要证明，$X$ 的确可以被分划成 $w$ 个链，我们将使用强归纳法来证明此事.

当 $|X|=1$ 时，命题自然地成立；

若 $|X|>1$ ，归纳地假设：对于一切基数小于 $|X|$ 的偏序集，命题已经成立，现在需要考虑两种情形：

1. 若 $A$ 既不是 $X$ 所有极大元的集合，也不是其所有极小元的集合.
   基于此，我们设

   $$A^+=\{x \in X\ |\ \exists a \in A,x \geq a\}$$
   以及
   $$A^-=\{x \in X\ |\ \exists a \in A,x \leq a\}$$
   直观而言， $A^+$ 就是在 $X$ 中位于 $A$ 的元素上方的那些元素的集合；而 $A^-$ 就是在 $X$ 中位于 $A$ 的元素下方的那些元素的集合；另一方面，$A$ 的元素恰好是 $A^-$ 的极大元，以及 $A^+​$ 的极小元.

   我们可以得知以下若干条性质：

   1. 因为 $A$ 不是 $X$ 的所有极小元的集合，所以，在 $X$ 中存在一些不属于 $A$ 的极小元，从而 $A^+ \subsetneqq X$
   2. 同理， $A$ 不是 $X$ 的所有极大元的集合，因此 $A^- \subsetneqq X$
   3. 显然有 $A \subseteq (A^+ \cap A^-)$ 且 $(A^+ \cup A^-) \subseteq X$
   4. $A = (A^+ \cap A^-)$
   5. $(A^+ \cup A^-) = X$

   第 4，5 条性质并非显然，但稍加思考也不难看出，证明略；

   第 1，2 条性质告诉我们，$A^-$ 和 $A^+$ 的基数小于 $X$，于是此时由归纳假设可知，$A^-$ 可以被分划成 $w$ 条链

   $$\mathcal{L}_1,\ \mathcal{L}_2,\ \cdots,\ \mathcal{L}_w$$
   类似地，$A^+$ 可以被分划成 $w$ 条链
   $$\mathcal{L}'_1,\ \mathcal{L}'_2,\ \cdots,\ \mathcal{L}'_w$$
   而链 $\mathcal{L}_i$ 的极大元和 $\mathcal{L}'_i$ 的极小元都同时对应于 $A$ 中的某个元素. 构造链 $\mathcal{K}_i=\mathcal{L}_i \cup \mathcal{L}'_i$，将它们 “粘合” 在一起得到的新的 $w$ 条链，就是偏序集 $X$ 的链分划.

2. 若 $A$ 是 $X$ 的所有极小元的集合，或者 $X$ 的所有极大元的集合

   设 $x$ 是 $X$ 的极小元而 $y$ 是 $X$ 的极大元且 $x \leq y$（ $x$ 和 $y$ 可能相等），则 $X-\{x,y\}$ 的最大反链大小至多为 $w-1$ ，根据归纳假设， $X-\{x,y\}$ 最少能划分成 $w-1$ 条链，这些链和链 $\{x,y\}$ 一起构成了 $X$ 的一个大小为 $w$ 的链分划.

综合可知，定理得证.

Q.E.D.

注解与阐释

偏序集 $(X,\leq)$ 可以用 Hasse 图来表示；在某种程度上，本文的内容亦可以借助 Hasse 图直观地解释或描述.

如上图所示，在 Hasse 图中，可比的元素总体上沿纵向排列，而互相不可比的元素倾向于排布在同一水平位置上；链的大小决定了 Hasse 图在（至少是局部范围内）纵向的长短，而反链的大小决定了其在（至少局部范围内）横向的长短——因此，我们在上文中，把最大链的大小定义为 “高”，把最大反链的大小定义为 “宽”，正蕴含了其中的直观意味.

于是，本文所述的两个定理所具有的对偶性，就类似于一个面积固定的矩形的长和宽所具有的对偶性（希望这不是个糟糕透顶的比喻）.

不妨继续从 Hasse 图的角度解释 Mirsky 定理. 既然我们已经知道，互不可比的元素总体上沿横向排布，所以，对偏序集的反链分划其实就类似于沿横向 “切蛋糕”——但是分划过程中切的数目就必须由纵向的最大长度（也就是 $X$ 的高）来界定：

• 一方面，我们沿着最大链来切蛋糕的话，分划数目可以刚好等于 $X$ 的高；
• 另一方面，不能小于最大链的元素数目（否则强大的抽屉原理会马上导出矛盾）

Dilworth 定理的情形是高度对称的，对偏序集的链分划就要求我们沿纵向 “切蛋糕” ：

• 一方面，只需要从最大反链的集合元素出发，就可以延伸出刚好 $w$ 条链；
• 但不能小于 $w$ 条链（原理同上，不赘述）

无聊的总结

本文叙述了偏序集上关于链和反链的两个对偶定理，和几乎所有非纯数专业的人能接触到的定理一样，它们不光具有形式上的 “美”，还可以实实在在地用于解决一些问题，以后或许笔者会沿此继续深入.