Partial Order - 偏序关系

前言

上一篇关于序理论的文章对于偏序关系的介绍不多，于是这一篇我准备重点整理偏序关系的相关知识，内容摘抄自南京大学的课件。这一篇的重点是引出join-semilattice概念，它是CRDT数据结构的核心。

知识点

偏序和全序

偏序的定义： 集合上的满足自反性、反对称性、传递性的关系，通常记作$\preceq$。

定义了偏序关系的集合成为偏序集，记作$(A,\preceq)$。

举例：

集合包含关系$(2^A,\subseteq)$（$2^A$应该表示$A$的所有子集组成的集合），其中$A$是集合。

$(Z^+,\mid)$，$Z^+$是正整数集，$\mid$是整除关系。

既是偏序又是等价的关系：

任意非空集合$A$上的恒等关系$I_A$

“字典顺序”

设$\preceq$是非空集合$A$上的偏序关系，定义$A\times A$上的关系$R$如下：(iff = 当且仅当)

$$(x_1,y_1)R(x_2,y_2)\ iff\ x_1\neq x_2\ and\ x_1\preceq x_2,\ or\ x_1=x_2\ and\ y_1\preceq y_2$$

易证$R$是$A\times A$上的偏序关系

给定有限字符集合$\Sigma$，若在$\Sigma$上有一个偏序关系，类似上述办法，可以对任意正整数$k$，定义$\Sigma^k$（有$\Sigma$中字符构成的长度为$k$的字符串的集合）上的偏序关系。加以适当的技术处理，则容易定义$\Sigma^+$（有$\Sigma$中字符构成的长度为任意正整数的字符串的集合）上的偏序关系：字典关系。

注意：在通常的字典关系中，任何两个元素均可比。

全序：一种特殊的偏序关系

如果对$a,b\in A$，$a\preceq b$和$b\preceq a$中有一个成立，则$a,b$科比。

设$R$是$A$上的偏序关系，如果$A$中的任意两个元素是可比的，则称$R$是$A$上的全序关系（或线序关系）。

举例：

实数集上的“不大于”关系$\leq$、基于拉丁字母表的字典顺序。

偏序集上的“小于”关系及覆盖

设$(A,\preceq)$是偏序集，$A$上的“小于”关系$\prec$定义如下：

$$x\prec y\ iff\ x\preceq y\ \wedge\ x\neq y$$

元素$y$覆盖$x$定义如下：

$$x\prec y, 且不存在z\in A使得x\prec z\prec y$$

哈斯图

一般的关系图可以表示偏序关系

哈斯图（Hasse）： 利用特定的性质简化图示方法

• 利用自反性省略圈
• 利用反对称性省略箭头
• 利用传递性省略部分连线（覆盖）

ρ({a,b,c})上的包含关系

{1,2,…,12}上的整除关系

{1,2,3,4,6,8,12,24}上的整除关系

偏序集的特殊元素

极大(小)元

$x$是偏序集$(A,\preceq)$中极大元，当且仅当对于任意$y\in A$，如果$x\preceq y$，则$x=y$。

$x$是偏序集$(A,\preceq)$中极小元，当且仅当对于任意$y\in A$，如果$y\preceq x$，则$x=y$。

讨论：

• 不一定存在，但是有穷集合一定有极大(小)元
• 不一定唯一
• 一个元素可能兼当极大(小)元

最大(小)元

$x$是偏序集$(A,\preceq)$中最大元，当且仅当对于任意$y\in A$，都有$y\preceq x$。

$x$是偏序集$(A,\preceq)$中最小元，当且仅当对于任意$y\in A$，都有$x\preceq y$。

讨论：

• 可能不存在
• 若存在，必唯一

上(下)确界

上界：对于偏序集$(A,\preceq)$和$A$的子集$B$，若存在$y\in A$，对于$B$中任意元素$x$，均有$x\preceq y$，则$y$是$B$的上界。

最小上界：如果$B$的上界构成的偏序集有最小元，则该最小元为$B$的最小上界（lub），也称上确界。

类似地可以定义下界、最大下界，也称下确界。

讨论：

• 不一定存在
• 最小上界若存在，则必唯一

从哈斯图来看特殊元素

拓扑排序

有向无环图

构造一种线性排序

良序

定义：给定集合$A$上的偏序$\preceq$，若$A$的任一非空子集均存在最小元素，则该偏序为良序。

良序必为全序，因为对任意$a,b\in A$，$\{a,b\}$必有最小元，则$a,b$一定可比。

实际上，“反对称性+任一非空子集存在最小元”就能保证全序性质（偏序性质+任何两个元素均可比）。

讨论：

• 全序是否一定是良序？
  当$A$是无穷结合时，全序不一定是良序。比如$(R,\leq)$，在开区间上没有最小元素。
• 良序$\rightarrow$全序$\rightarrow$偏序
• 偏序/全序/良序的逆关系是否仍为偏序/全序/良序？
  良序的逆关系不一定是良序，比如$(N,\leq)$。

链与反链

定义：设$C$是偏序集$(P,\preceq)$的一个子集，如果$C$中任何两个元素均可比，则$C$构成一个链；如果$C$中任何两个元素均不可比，则$C$构成一个反链。

Dilworth定理

链覆盖是$(P,\preceq)$中一组互不相交的链，他们一起包含了$P$中的所有元素。

Dilworth定理（1950）：在任意有限偏序集$(P,\preceq)$中，覆盖$P$的最小链数等于$P$中最长反链的长度（元素个数）。

注：覆盖$P$的链数$\geq P$中任一反链的元素个数。
等价结论：有限偏序集汇总存在一个链覆盖和一个反链，他们大小相等。

Dilworth定理的归纳证明：按照$P$中元素个数($\mid P\mid=1,2…$)进行归纳证明。设$a$是$P$中一个极大元素，$P’=P-\{a\}$。
设$(P’,\preceq)$有一个大小为$k$的反链$\{a_1,a_2,…,a_k\}$，并有一个规模为$k$的链覆盖$\{C_1,C_2,…,C_k\}$。
对任意$C_i$，$P’$中大小为$k$的任一反链均有唯一的元素属于$C_i$，这些元素有一个最大元，记为$x_i$。
$A=\{x_1,x_2,…,x_k\}$必是反链。否则，不妨假设$A$中有两个元素$x_i\preceq x_j$。根据$x_j$的定义，$P’$中必有一个大小为$k$的反链$A_j$，$x_j$是$A_j$和$C_j$的公共元素，假设$y$是$A_j$和$C_i$的公共元素，则$y\preceq x_i$。从而$y\preceq x_j$。这与$A_j$是反链矛盾。

如果$\{a,x_1,x_2,…,x_k\}$是$P$中的反链，而$P$的链覆盖$\{\{a\},C_1,C_2,…,C_k\}$就是规模为$k+1$的覆盖，得证。
如果$\{a,x_1,x_2,…,x_k\}$不是$P$中的反链，即：存在某个$x_m$使得$x_m\preceq a$。（$a$是极大元，不会出现$a\preceq x_m$）
令$K=\{a\}\cup\{z\in C_m\mid z\preceq x_m\}$。显然$K$是$P$中的一条链。$P-K$中最大的反链大小为$k-1$（根据$x_m$的定义，$P-K$中没有含$k$个元素的反链）。有归纳假设，$P-K$有大小为$k-1$的一个链覆盖，改链覆盖与$K$构成$P$的链覆盖（链数为k），已知$\{x_1,x_2,…,x_k\}$是$P$中的反链（含$k$个元素），得证。

命题：自然数$1,2,3,…,n^2+1$的任何一种排列，必然含有一个长度不小于$n+1$的严格递增链或严格递减链。

证明：给定$1,2,…,n^2+1(=m)$的一种排列$v_1v_2…v_m$，定义集合：

$$A=\{(i,v_i)\mid i=1,2,...,n^2+1\}$$

建立两个偏序关系$R_1$和$R_2$：

$(i,v_i)R_1(j,v_j)$当且仅当$i<j$并且$v_i<v_j$，或者$(i,v_i)=(j,v_j)$

$(i,v_i)R_2(j,v_j)$当且仅当$iv_j$，或者$(i,v_i)=(j,v_j)$

$R_1\cap R_2=I_A, R_1\cup R_2=A\times A$。$R_1$的链是$R_2$的反链。

问题：一定存在$A$的一个至少包含$n+1$个元素的子集，它是$R_1$的链或者$R_2$的反链。

若$R_1$链的长度均$\leq n$，即$R_2$反链的大小均$\leq n$，则存在$k\leq n$的$R_2$覆盖，有长度超过$n$的$R_2$链，否则元素个数$\leq n^2$。如此则会产生矛盾。

格(lattice)

定义：设$(S,\preceq)$是偏序集，任意$x,y\in S$存在最小上界$lub\{x,y\}$(least upper bound)，记为$x\vee y$。任意$x,y\in S$存在$\{x,y\}$的最大下界$glb\{x,y\}$，记为$x\wedge y$。则称$S$关于$\preceq$构成格。

举例：

• $(\rho(B),\subseteq)$。$x\wedge y = x\cap y$，$x\vee y=x\cup y$。
• $(\{x\in N^+\mid x|60\},\mid)$，60的正因子集合及整除关系。$x\wedge y=gcd(x,y)$，$x\vee y=lcm(x,y)$。
• $(Z,\leq)$。$x\wedge y=min\{x,y\}$，$x\vee y=max\{x,y\}$。

格的示例图

格与哈斯图

上图中右边两个哈斯图所表示的偏序集不是格

格的基本关系式
根据“最小上界”和“最大下界”的定义，有如下关系式：

$$a\preceq c, b\preceq c\Rightarrow a\vee b\preceq c$$ $$c\preceq a, c\preceq b\Rightarrow c\preceq a\wedge b$$

格的性质
若$(S,\preceq)$是格，则任意$a,b\in S$满足：$a\preceq b\Leftrightarrow a\wedge b=a\Leftrightarrow a\vee b=b$。

而且$(S,\wedge,\vee)$还符合一下规律：

• 结合律：$(a\wedge b)\wedge c=a\wedge (b\wedge c)$，$(a\vee b)\vee c=a\vee (b\vee c)$。
• 交换律：$a\wedge b=b\wedge a$，$a\vee b=b\vee a$。
• 吸收律：$a\wedge (a\vee b)=a$，$a\vee (a\wedge b)=a$。

join-semilattice

在数学上又把寻找最大下界的操作称为“meet”，把寻找最小上界的操作称为“join”。
join-semilattice的定义则是一个弱化版的lattice，它只要求任意两个元素存在最小上界，并不要求任意两个元素有最大下界。

原文链接

http://ws.nju.edu.cn/courses/dm/courseware/20150415-Partial_order.pdf