离散数学序理论

序理论

序理论是利用二元关系来将「次序」这一概念严格化的数学分支 —oi wiki

二元关系

有序偶对(序偶) ：两元素按一定的次序组成的二元组，记为 < x , y >

对于两集合 $A$ 和 $B$ ，称集合 $A \times B$ 为二者的笛卡尔积。

笛卡尔积满足： $A \times B = {< x, y > | x \in A \land y \in B}$

若存在一个集合 $S$ , 设 $| S | = n$ ，那么 $S$ 上不同的二元关系的个数为：

集合 $S$ 上的二元关系是 $S \times S$ 的一个子集

集合 $S$ 上的二元关系数量即是 $S \times S$ 的子集数量（ $2^{n^{2}}$ ）

那么对于一个 $A \times B$ 上的关系 $R$

$R = ϕ \Leftrightarrow R$ 为 $A \times B$ 上的空关系
$R = A \times B \Leftrightarrow R$ 为 $A \times B$ 上的全关系
$R = I_{A} = {< x, y > | x \in A} \Leftrightarrow R$ 为 $A$ 上的恒等关系

关系的运算

复合运算： $R \circ S = {< x, y > | x \in A \land z \in C \land (\exists y) (y \in B \land x R y \land y S z)}$

简而言之 $R$ 中有 < x , y > $S$ 中有 < y , z >，那么二者的复合为 < x , z >
逆运算： $(A \times B)^{- 1} = B \times A$
幂运算： $R^{n} = R^{n - 1} \circ R R^{0} = I_{A}$

关系的性质

自反性 $(\forall x) (x \in A \to< x, x >\in R) = 1$
反自反性 $(\forall x) (x \in A \to< x, x >\notin R) = 1$
对称性 $(\forall x) (\forall y) ((x \in A) \land (y \in A) \land (< x, y >\in R \to < y, x >\in R)) = 1$
反对称性 $(\forall x) (\forall y) ((x \in A) \land (y \in A) \land (< x, y >\in R) \land (< y, x >\in R \to x = y)) = 1$
传递性 $(\forall x) (\forall y) (\forall z) ((x \in A) \land (y \in A) \land (z \in A) \land ((< x, y >\in R) \land (< y, z >\in R) \to (< x, z >\in R))) = 1$

从关系图的角度理解会更简单：

自反性：全是自环

反自反性：没自环

对称性：两点间只要存在边，就必须是双边（x=y 时即自环也满足

反对称性：两点间只要存在边，除了自环都不能有双边

传递性：参考向量的合成，需要注意自环

关系的闭包

闭包运算，简单来说就是将一个关系增加最少的元素，使得该关系具有某一性质

自反、对称、传递闭包分别用 $r (R) s (R) t (R)$ 表示

更具体的计算：

$r (R) = R \cup I_{A}$

$s (R) = R \cup R^{- 1}$

$t (R) = \cup_{i = 1}^{| A |} R^{i}$

特殊关系

二元关系	自反性	反自反性	对称性	反对称性	传递性
等价关系（equivalence relation）	√		√		√
拟序关系 (quasi-order set)		√		√	√
偏序（partial order）	√			√	√

等价

集合的划分：

一个集合的划分，就是将该集合视为几个交集为空的非空真子集的并集。

再简单些，可以将它理解为把一个集合切成几个非空的小集合。

等价类：

设 R 是非空集合 A 上的等价关系

那么对于 $\forall x \in A$ ，称集合 $[x]_{R} = {y | y \in A \land < x, y >\in R}$ 为 x 关于 R 的等价类。

所以，R 上所有的等价类构成的集合就是一个依据等价关系进行的 A 的划分

于是就引出了商集的概念

商集：

设 R 是非空集合 A 上的等价关系，那么由 R 确定的等价类的集合就称为(A上关于R的)商集，记为 A/R

不妨举个例子：

有一集合 A={1,2,3,5,7,9}，R为其上的以 4 为模的同余关系

那么等价类有：

$[1]_{R} = [5]_{R} = [9]_{R} = {1, 5, 9}$

$[3]_{R} = [7]_{R} = {3, 7}$

$[2]_{R} = {2}$

商集为：

$A / R = {[1]_{R}, [2]_{R}, [3]_{R}} = {{1, 5, 9}, {2}, {3, 7}}$

偏序

为更好研究偏序关系，我们常会使用哈斯图来描述

确定元素之间的覆盖关系, 如果 a 覆盖 b, 那么 b 就在 a 上方并链接;

有集合 S = {2, 3, 6,12}对于在 S 上的整除关系:

6 能覆盖 2 和 3

12 能覆盖 2,3,6

因此哈斯图表示为
1
2
3
4
graph LR
A((12))-->B((6))
B((6))-->C((2))
B((6))-->D((3))

特殊元素

设 A 是一个偏序集, B 是其上的某一个子集，那么有:

最大(小)元：在 B 中，该元素满足 “覆盖"任意元素/被任意元素"覆盖”
极大(小)元：在 B 中，该元素满足不被任一元素”覆盖“/不“覆盖”任一元素
上(下)界：在 A 中，该元素满足 “覆盖” B 中的任意元素/被 B 中的任意元素“覆盖”
上(下)确界：在上界所有元素中，该元素满足被任一元素“覆盖”/ “覆盖”任一元素

注意：本文借以哈斯图描述中的“覆盖”一词来描述 两元素之间满足的某一关系，以避免直接带入符号理解定义而导致误解的可能。