7. 偏序关系

有序集合 ordered set

一个有序的 pair $(P,\le)$ 且有一个集合 P 和一个偏序关系 $\le$

偏序集 poset

我们称 $(P,\le)$ 为偏序集
注意到 poset 这一步只是强调反对称性，并没有强调 任意两个 这个要求

线性有序 linear order

我们称对于 $\forall x,y\in P$ , 我们有 $x\le y$ 或者 $y \le x$ 那么这就是 total order 或 linear order
这个强调集合内的所有元素都参与偏序关系，在约束上比一般的partial order限制的参与者（所有元素）

线性扩展 linear extension

我们称 $P=(X,\le_P)$ 是一个非空有限集合，如果 total order $L=(X , \le_L)$ 满足 $\le_P \subset\le_L$ 那么我们称 L 是 P 的线性扩展

矩阵表示

对于线性有序的集合，我们可以用矩阵表示 (回想我们在关系relation的时候曾经用 01 存在矩阵判断关系元素是否存在, 这里就是将关系变成了偏序关系, 由于反对称性所以有上三角现象)，而且我们会发现这个矩阵是上三角矩阵

偏序的元素相关定义

极小元素 minimal element: $a\in P, \not \exists x\in P, s.t. x < a$ 那么 $a$ 是一个极小元素
最小元素 minimum element: $a\le x \forall x\in P$
区别：极小元素是不存在比它小的元素，最小元素是要求存在关系保证所有元素都大于之
极大元素 maximal element: $z\in P\not \exists x\in P, s.t. z < x$
最大元素 maximum element: $z\ge x \forall x\in P$
可比较的 comparable: $x,y\in P$ 如果 $x\le y$ 或者 $y\le x$ 那么我们称 x,y 是可比较的

子偏序集 subposet

对于一个偏序集合 $(P,\le_P)$ 如果 $Q\subset P$ 且 $Q$ 也是一个偏序集合, 且有偏序关系 $\le_Q =\le_P|_{Q\times Q}$ ，那么我们称 $(Q,\le_Q)$ 是 $(P,\le_P)$ 的子偏序集

覆盖 Cover

对于偏序集合 P 我们有 $y\in P$ 是对于 $x\in P$ 的一个覆盖，如果 $x < y$ 且对于所有 $z\in P$ , $x\le z\le y$ 可以推到出 $z\in \{x,y\}$
这种情况下我们也可以说 x is covered by y, 或者 y covers x
我们也称 x 与 y 是 adjacent

注

cover 关系描述的对象是元素
一般表示偏序关系下 相邻的大

例子

$\{1,3,5\}$ 对于偏序关系 $\subset$ 来说， $\{1,3,5,7\}$ 是它的覆盖集合
在集合 $\mathbb R, \mathbb Q$ 中不存在 cover 集合

偏序关系的可视化 —— Hasse Diagram

Hasse 图是用来表示偏序关系的简化图形工具，它只显示直接的关系，不显示传递关系。

绘制方法

自底向上法

边界是 cover pair 的关系
如果有偏序关系 (x,y)，那么 x 画在y的下面
单调关系画成竖直的

自顶向下法

将集合中所有的偏序关系化成向上的箭头
消除所有的loop
消除所有的redundant,遵循 transitivity关系
消除所有箭头

链 Chain

对于偏序集合 $(P,\le)$ ，链是子集 $C\subset P$ 使得任意两个元素是 comparable 的
antichain：任意两个元素不可比较
二者的讨论对象都是元素子集，并不是关系集合
链和等价类的性质比较类似哦

用 hasse 图像来解释

chain

就是从下到上的一个完成的连线，不能平级连接，一条主干，没有分支

antichain

不相干的元素组成的集合，也就是hasse图中没有直接相连的或者通过递增关系间接相连的集合

正反链引理

对于链子 C 和反链子 A 我们有 $|A \cap C| \le 1$

最大链 Maximum Chain

对于chain C, $\forall C' s.t. |C| \not <|C'|$

极大链 Maximal Chain

对于chain C, $\not\exists C' s.t. C\subsetneq C'$ 那么 C 是极大链

链子高度 height

maximum size of chain in P，写作 $h(P)$

最大反链 Maximum Antichain

对于antichain A, $\forall A' s.t. |A| \not <|A'|$

极大反链 Maximal Antichain

对于antichain A, $\not\exists A' s.t. A\subsetneq A'$ 那么 A 是极大反链

链子宽度 width

maximum size of antichain in P，写作 $w(P)$
其实可以理解成，我们将所有递增关系的图画成向上的几条平行线，那么横向找一条没有递增关系的折线组成的就是anti chain且长度就是整张图的宽度

极大性质

我们不能通过给极大链子/反链添加新元素来增长链子/反链

尺寸性质

如果 P可以被分割成 t 个反链，那么P的高度最多有 t
如果 P可以被分割成 t 个链，那么P的宽度最多有 t
由极大元素组成的集合是一个antichain

Mirsky Theorem

一个高度为 h 的偏序集合可以被分割成 h 个反链

证明方法

递归的删去极大元素就行

Dilworth Theorem

一个宽度为 w 的偏序集合可以被分割成 w 个链

注

Dilworth 定理对于无限集合也是成立的，但是，w需要是有限的

团 Clique / 完整图 Complete Graph

对于图 G，如果 G 的每一个顶点都与其他所有的顶点相连，那么我们称 G 是一个完整图
用符号定义，就是对于图 $G = (V,E)$ 我们有 $E = \begin{pmatrix}V\\2\end{pmatrix}$
相反，我们用 $G = (V,\begin{pmatrix}V\\2\end{pmatrix})$ 定义，那么 $\bar G = (V,\varnothing)$ 就是一个独立图 independent graph,即只有点没有edge