同余关系(等价关系)：#

1. 自反性：x % x == x % x;
2. 对称性：x % y == y % x;
3. 传递性：x % y % z == x % z;

mod，(x - y) | y(x - y 能整除 y)

等价类#

设R是非空集合A上的等价关系，对于任意的$x \in A$，称集合$[x]_R = \{ y | y \in A, <x, y> \ in R \}$，为x关于R的等价类（equivalence class）x为[x]_R的生成元（generator）

等价关系中，由某个元素为第一元素(生成元)，得到的第二元素集合（等价类）。

1. 等价类是非空的
2. 对任意的$x, y \in A$,如果$y \in [x]_R$，则有$[x]_R = [y]_R$，否则$[x]_R \cap [y]_R = \varnothing$
3. $\cup_{x\in A} {[x]_R} = A$

商集#

由等价关系R确定的一切等价类的集合，称为集合A上关于R的商集(quotient set)，记为A/R，即：$A/R = \{ [x]_R | x \in A \}$

等价类（集合）的集合

等价类可用于：分组的报文转发、软件测试项目的分类、商品促销的分类

即：将二元关系，按照第一元素进行分类

集合#

对于给定非空集合A，对于集合的集合$\pi = {S_1, S_2, ..., S_n}$满足

1. π的元素$S_i$都是A的子集
2. π的每个元素互不相交，$S_i \land S_j = \varnothing$。
3. π的所有元素，构成了A，$\cup S_i = A$

那么：集合π就是集合A的一个划分(partition)，π中的集合元素叫做划分的块(block)或者类(class)

可比、覆盖#

对于非空集合A上的偏序关系R，A的任意两个元素x, y

• 如果 x <= y 或 y <= x，则x与y可比
• 如果 x <= y 且 不存在 $z \in A$ 使得 x <= z <= y，则 y 覆盖 x

覆盖，不存在中间元素

哈斯图#

将有向关系图，简化得到的图叫做哈斯图。

1. 取消结点的自环
2. 取消传递性得到的边
3. 将有向边向上，去掉箭头。(起点在下方，终点在上方)。

良序定理#

所有集合都可以良序排序，即：存在一种方法实现良序排序。

偏序关系、全序关系、良序关系#