偏序集的讲解
偏序集的讲解
偏序集是数学中一个重要的概念，广泛应用于计算机科学、组合数学等领域。本文将从偏序关系的定义出发，逐步介绍偏序集的性质、哈斯图的构造方法以及著名的Dilworth定理，帮助读者建立对这一抽象概念的直观理解。
偏序集
偏序集是由集合 SS 与 SS 上的偏序关系 RR 构成的，记为 (S,R)(S,R)。
下面介绍什么是偏序关系。
偏序关系
对于二元关系 R⊆S×SR⊆S×S，如果 RR 是自反的，反对称的，传递的，那么 RR 称为偏序关系。
自反性
a≤aa≤a，∀a∈S∀a∈S
反对称性
∀a∀a，b∈Sb∈S，若 a≤ba≤b 且 b≤ab≤a，则 a=ba=b
传递性
∀a∀a，bb，c∈Pc∈P，若 a≤ba≤b 且 b≤cb≤c，则 a≤ca≤c
注意： ≤≤ 符号是偏序关系的符号，并不是“小于等于”的意思，但“小于等于”也是一个偏序关系，一个典型偏序集的例子便是 (Z,≤)(Z,≤)，ZZ 表示整数集。
对于 SS 中的元素 aa，bb。如果 a≤ba≤b 或 b≤ab≤a，则称 aa ，bb 可比，反之则不可比。 请记住元素可比的概念，这在后面讨论链会再次出现。
以上是偏序集的数学定义，过于抽象，为了更好理解偏序关系，我们引入哈斯图。
哈斯图（ Hasse 图）
定义
对于元素 xx，如果 x<yx<y 且不存在 zz 使得 x<z<yx<z<y，那么 yy 就是 xx 的覆盖元素，在哈斯图中连出一条 x−>yx−>y 的有向边。通过覆盖关系生成的图就是哈斯图。
例如，集合 {1,2,3,4,6,8,12}{1,2,3,4,6,8,12} 上的关系 { (a,b)(a,b) | aa 整除 bb } 画出的哈斯图就是
看起来哈斯图并不是有向图，这是否与上面所说的违背？
其实不然，在哈斯图中，把较大元放在较小元的上方，以此来隐式地表示有向。
性质
由于偏序关系满足反对称性，所以哈斯图中一定不能出现回路。
不难发现，哈斯图是一个有向无环图( DAG )！
一个经典的应用就是拓扑排序：从偏序构造一个相容的全序。相关内容在此不再赘述。
接下来给出一个定理。
Dilworth 定理
对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真。
补充一下对链和反链的定义：
设 CC 是偏序集的一个子集，如果 CC 中元素互相可比，那么称 CC 是链；如果 CC 中元素互相不可比，则称 CC 是反链。
这个定义非常形象，链对应到哈斯图上就是一条从下至上的 “链”（有向路径）。
以上面的哈斯图为例，红圈就是一条链，蓝圈就是一条反链。
在这个图中，反链元素个数最多是 2 ，而且，整个图至少需要 2 条链 ( {1,2,4,8}{1,2,4,8} 和 {3,6,12}{3,6,12} ) 来覆盖。
通过观察哈斯图，我们可以直观地发现 Dilworth 定理成立。
严格的数学证明如下：
设有限偏序集 (S,≤)(S,≤) , 有 ∣S∣=n∣S∣=n，对 nn 进行归纳。
当 nn=1 时，显然，链划分=宽度=1。
假设该命题对于 n≤kn≤k 时均成立，下面证明 n=k+1n=k+1 时也成立：
设 AA 是一条最长反链，记为 A={a1,a2,...,aw}A={a1,a2,...,aw}，定义
D(A)={x∣∃a∈A(x<a)}D(A)={x∣∃a∈A(x<a)}
U(A)={x∣∃a∈A(a<x)}U(A)={x∣∃a∈A(a<x)}
则 S=A∪D(A)∪U(A)S=A∪D(A)∪U(A)
存在最长反链 AA 使得 D(A)D(A) 和 U(A)U(A) 均不为空。因为 AA 是 SS 的最长反链，所以 AA 也是 A∪D(A)A∪D(A) 的最长反链，由归纳假设： A∪D(A)A∪D(A) 可以划分为 c1,c2,...,cwc1 ,c2 ,...,cw 共 ww 条链，其中 cici 的极大元是 aiai 。同理， A∪U(A)A∪U(A) 也可以划分为 d1,d2,...,dwd1 ,d2 ,...,dw 共 ww 条链，其中 didi 的极小元是 aiai 。于是 SS 可以划分为 c1∪d1c1 ∪d1 ,c2∪d2c2 ∪d2 ,...,cw∪dwcw ∪dw 共 ww 条链。
对于每一个最长反链 AA 都有 D(A)D(A) 或 U(A)U(A) 为空。那么每条反链 AA 要么构成全上界，要么构成全下界。在 SS 中选择一个极大元 yy ，再选择一个满足 x≤yx≤y 的极小元 xx ， {x{x , y}y} 必构成一条链 CC ，且 xx 一定包含在全下界， yy 一定包含在全上界，因此 S−CS−C 中每个最长反链的元素个数都较 SS 减去 1 ， S−CS−C 的宽度是 w−1w−1。应用归纳假设， S−CS−C 可划分为 w−1w−1 条链，再加上 CC 得到 ww 条链。
归纳证明完毕。