集合与图论学习笔记02

定义

定义 2.1 闭包

非空是的二元关系，定义的自反（对称、传递）闭包满足：

• 是自反（对称的，传递的）的
• 对任意自反（对称、传递）关系，若，则（最小的）

闭包	记为
自反闭包
对称闭包
传递闭包

容易知道：

是自反的

是对称的

是传递的

且

若则

为上任意一关系

证明： 点击查看证明

1. 显然自反，且包含

   设为包含满足自反性的最小的关系

   满足自反性，则，则

   则

2. ，满足对称性，且包含

   设为包含满足对称性的最小的关系

   对称，则由知，则

   则

3. 容易验证则是传递的且包含

   设为包含满足传递性的任意的关系

   ，… 由数学归纳法知

   则

   则

若则

证明： 点击查看证明

也就是证时

考虑

则存在序列

使得

由于，必有不只出现一次

则

删去这一段，若序列元素个数大于重复这一过程，知道为止

此时有则 $(a,b)\in \bigcup^{n}{k=1}R{k}$

则

考虑对闭包的影响

• 若自反，自反
• 若对称，对称
• 若传递，传递

考虑多个闭包之间的关系

证明： 点击查看证明

3. 又对称，则对称，则得到

   ：

---

定义 2.2 等价关系

设为非空集合，为上的关系。如果是自反的、对称的和传递的，那么称为上的 等价关系

和均为等价关系

---

定义 2.3 等价类

集合非空，为上等价关系，记

称为关于的等价类，有时也简记为或

非空，为上等价关系，对，有

• 若则
• 若则

证明： 点击查看证明

1. 具有自反性，有等价类定义知
2. 设，知则矛盾，另一侧同理
3. 设，则矛盾
4. 取由等价类定义显然，显然则故

---

定义 2.4 商集

集合非空，为上等价关系，所有以产生的等价类的集合叫做的商集，记作

---

定义 2.5 划分

设为非空集合，如果的子集族满足下述条件:

1. ,
2. 若, 则,
3. ,

那么称是的一个划分，称每个为的一个划分块。当时，也称是的一个-划分。

集合上的任意一个划分可以确定上的一个等价关系

证明： 点击查看证明

证明：设集合上有一个划分 $\pi = {A_i}{i \in I}R =\bigcup{i \in I} A_i \times A_iRA$ 上的等价关系。

(1) 自反性：对任意，必存在。

(2) 对称性：若，则存在使。因此，故。

(3) 传递性：若且，则存在使且。由于划分中的不同块不相交，必有，从而，故。

综上，是上的一个等价关系。

设是集合上的两个等价关系，记。证明也是上的等价关系。

证明： 点击查看证明

(1) 自反性：对任意，有且，因此。

(2) 对称性：若，则且。由对称性，且，因此。

(3) 传递性：若且，则，由的传递性得；同理，由的传递性得。于是。

综上，是上的一个等价关系。

---

定义 2.6 划分的积

设是集合上的两个等价关系，记，由确定的划分，则称确定的划分为的积，记作

---

定义 2.7 划分的加细

设是一个集合，$ \pi = \{A_i\}{i \in I}\sigma = \{B_j\}{j \in J}A $ 的两个划分。

若满足：对任意，都存在某个，使得，

则称是的一个加细，记作

设是一个集合，是上的两个划分，对应的等价关系分别为

如果是的一个加细，即

证明： 点击查看证明

设是集合，是的两个划分，对应的等价关系分别为。

(1) 若，则。

假设，则存在使。

由于，必存在某个，使得。

因此，从而

故。

(2) 若，则。

任取，并任取，有。

由，得。

这说明中所有元素在下互相等价，因此，其中是的等价类。

故。

综上，

设为划分，则

• 细分
• 设为划分，若细分则细分

都可由关系与划分的对应关系直接可得

---

定义 2.8 划分的和

设是集合上的两个等价关系，记。
是上的自反对称关系，但未必是等价关系，我们取其生成的最小传递关系，记作或

由确定的划分分别为，则称确定的划分为的和，记作

容易知道细分

设为划分，若细分则细分

简单来说，是同时比更粗的最细划分，即它是所有的下确界，其中。

---

定义 2.9 偏序关系

设为非空集合，为上的关系。如果是自反的、反对称的和传递的，那么称为上的 偏序关系，称为偏序集

是偏序集但不是偏序集

一般将偏序关系记为，若则，也有的记法，表示且

偏序关系中的偏意味着部分可比较但未必全部都能比较

---

定义2.10 偏序的覆盖

设为偏序集，若且不存在使得则称覆盖

---

定义2.11 哈斯图

对于给定偏序集按照如下方法画 哈斯图

以中所有元素为顶点，适当排列顶点顺序，满足

• 若则把画在下方
• 若覆盖，则用一条线段连接和

---

定义 2.12 偏序集的特殊元素

设为偏序集，，

• 若都有，则称是的最大元
• 若都有，则称是的最小元
• 若都有当时必有，则称是的极大元
• 若都有当时必有，则称是的极小元
• 若都有，则称为的上界
• 若都有，则称为的下界
• 若为的上界，且对的任意上界都有则称为的最小上界或者上确界
• 若为的下界，且对的任意下界都有则称为的最大下界或者下确界

从定义可知

最大元和极大元可能是不同的，最大元要求中的所有元素都可比，而极大元只要求能够和极大元比较的元素里不存在比极大元大的元素

的最大元一定是的上界，同时也是的最小上界，但的上界不一定是的最大元，因为它可能不是的元素，最小元同理。

如果的最大下界和最小上界存在，那么一定唯一

每个非空有限偏序集至少有一个极小元

证明： 点击查看证明

反证法，假设没有极小元，任意使得无限重复这一过程可得无限序列这说明有无限多个元素，这与是个有限集矛盾，故中存在极小元

---

定义 2.13 全序关系

设为偏序集，都是可比的，则称为上的全序关系（或简称全序、线性序）

---

定义 2.14 拓扑排序

设为 非空集合上的偏序关系，为上的全序关系，，只要成立，必有，则称全序与偏序是相容的，由一个偏序构造相容的全序的过程叫做拓扑排序

设是非空有限偏序集，则上存在与相容的全序

证明： 点击查看证明

中一定有极小元，考虑 $A\{x_{1}\}(A\{x_{1}\},\preceq)Ax_{1},x_{2},…,x_{n}\preceq’$ 由下面的序给出

，当作为极小元被选中时，已经被选中了，否则不可能是极小元，因此有，即当时一定有，这就证明了全序和偏序是相容的

拓扑排序算法

输入：元偏序集

输出：与相容的全序

1. ;
2. ;
4. ;
5. ;
6. ;
7. ;

---

拓展

拓展2.1 格

设是偏序集，如果，都有最大下界和最小上界，那么称为偏序的格

用表示和的最小上界

用表示和的最大下界

一般地，设，是的正因子的集合，为整除关系，偏序集构成格，事实上，，的最小上界是，最大下界是

---

拓展2.2 离散与覆盖

是格，若，且不存在使得，则称覆盖

若有，使得覆盖，且，则称为连接和的链。

如果的任何两个元素，总有连接它们的链，则称是离散的

有限的离散全序集的哈斯图由一条链组成

---

拓展2.3 完全格

为格，当任有最大下界、最小上界时，显然是格，称为完全格

自身的最小上界是整个格的最大元，记为

自身的最大上界是整个格的最小元，记为

若为格，则

若为格，

• 幂等律：
• 交换律：
• 结合律：
• 吸收律：

证明： 点击查看证明

幂等律、交换律由定义直接可得

结合律由上一性质立即可得

吸收律：由，得；又，故

至此，可将视为代数系统

在中，满足上面的四个律，定义关系如下：

，当且仅当，则为偏序集

证明： 点击查看证明

自反性：由，得。

反对称性：若且，则，，故

传递性：若且，则，，

于是故

因此是偏序关系。

下面证明是格

证明： 点击查看证明

只需证明，

由结合律和幂等律故

同理，所以是的上界

设满足且，即，则故因此

由吸收律：，同理，故是的下界

设且，则，，于是故，因此

所以为格。

是一代数系统，和为定义在上的二元运算。当其满足以上四个律时，称为格。并称为积（或交），为和（或并）

格，任意，当时有及。

证明： 点击查看证明

因此

同理可证

---

拓展2.4 子格

为格，，，若关于和封闭（即对任意，有且），则称为的子格

当为的子格时，一定是格。但当，且关于中的偏序关系构成格时，不一定是的子格

例如：

当时，是3次对称群

是格，且为完全格

取

其中

这4个都是的子群，是其两个平凡子群，则也是格，但不是的子格。

推广

一个群的子群全体关于包含关系所构成的格，不是该群的所有子集组成的集合（即的幂集）关于包含关系所构成的格的子格，因为子群的并（或交）并不一定是子群