离散数学序理论

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 4 分钟

序理论

序理论是利用二元关系来将「次序」这一概念严格化的数学分支 —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=\phi \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$ 上的恒等关系

关系的运算

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

    简而言之 $R$ 中有 < x , y > $S$ 中有 < y , z >，那么二者的复合为 < x , z >

  2. 逆运算：$(A\times B)^{-1} = B\times A$

  3. 幂运算：$R^n = R^{n-1}\circ R \R^0 = I_A$

关系的性质

  • 自反性 $(\forall x)(x\in A \rightarrow <x,x>\in R)=1$
  • 反自反性 $(\forall x)(x\in A \rightarrow <x,x>\notin R)=1$
  • 对称性 $(\forall x)(\forall y)((x\in A)\land (y\in A)\land (<x,y>\in R\ \rightarrow \ <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\rightarrow 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)\rightarrow(<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 中的任意元素“覆盖”
  • 上(下)确界：在上界所有元素中， 该元素满足 被任一元素“覆盖”/ “覆盖”任一元素

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