集合论与图论 · 等价关系、划分与偏序
集合论与图论
等价关系与偏序 · 手写笔记补充
1. 等价关系与等价类
补充来源：《集图笔记(1)》PDF 第 14—15 页。
上自反、对称且传递的关系称为等价关系，常记作 。例如整数上的模 同余关系（）：
的等价类与商集定义为
自反性保证 ，所以等价类非空且覆盖 。对任意 ，
证明
若 ，任取 ，由 、 传递得到 ，故 ；对称交换 可得反向包含。
若两类有公共元素 ，则 且 ，由对称性和传递性得 。因此两个等价类要么相同，要么不相交。
2. 划分及其对应
的划分是一个集族 ，满足：
- 每个块 均非空；
- 不同块两两不交；
- 。
等价关系的所有等价类构成划分。反之，给定划分，定义
同块关系自反、对称、传递，其等价类恰为原划分的各块。这两种构造互逆，故 上的等价关系与 的划分一一对应。
2.1. 划分的加细
若 的每个块都包含于 的某个块，则称 比 更细，即 是 的加细。
例如 比 更细。对应的等价关系满足
块切得越细，被视为等价的元素对越少。手写稿中“加细”的方向按这一定义统一。
3. 第二类 Stirling 数
将 个不同元素划分为 个非空、无标号块的方案数记为 。因此 元集上等价关系的个数是 。
边界值为
固定一个元素 ，分两类计数：
- 单独成块：其余 个元素分成 块，有 种。
- 不单独成块：先把其余元素分成 块，再选择一个块放入 ，有 种。
故
特别地， 时
第一式将每个元素分配到两个有标号块，去掉两个空块情形后除以 ；第二式中恰有一块含两个元素，其余均为单元素块。
例如 ，，因此四元集共有 个划分，也就有 个等价关系。
4. 偏序关系
自反、反对称且传递的关系称为偏序，偏序集记作 。例如 上的 、 上的整除，以及 上的包含关系。
若 为偏序，其逆关系也是偏序，称为对偶序。真包含、严格小于属于严格序；把自身也计入的祖先关系可作为非严格偏序的例子。
由偏序定义严格关系
它反自反且传递。反之，反自反且传递的严格关系加上 后得到偏序。
若 或 ，则 可比；否则不可比。任意两元素都可比的偏序称为全序。
被 覆盖，是指 且不存在 满足 。例如整除偏序中 被 覆盖，而 不被 覆盖，因为中间有 （也有 ）。
有限偏序集的 Hasse 图只画覆盖边，较小元素放在下方，省略自环、箭头以及可由传递性推出的边。覆盖关系本身一般不传递；从图中恢复偏序时需补自反和传递关系。
链、反链及其分解接续见 Lesson9.typ。