集合论与图论 · 关系闭包
集合论与图论
关系闭包 · 手写笔记补充
1. 关系闭包
补充来源：《集图笔记(1)》PDF 第 12—14 页。
固定基集 。关系 关于某性质的闭包，是包含 且具有该性质的最小关系 ：
- ；
- 具有所要求的性质；
- 任意具有该性质且包含 的关系 ，都满足 。
第三条是“最小”的含义，不能只验证“补完后具有该性质”。
自反、对称、传递性质都对非空关系族的交封闭，且全关系 具有这三种性质。因此，可将所有满足条件的超关系取交，分别得到自反、对称、传递闭包，记作 。
1.1. 自反闭包与对称闭包
自反关系必须包含每个 ，故每个包含 的自反关系都包含 ；后者又显然自反。对称闭包同理：每条原边都必须补上反向边。
1.2. 传递闭包
证明
它包含 。若 、，则 ，故正次幂之并传递。
若 传递且 ，由归纳法得 对每个 成立，因此 ，最小性成立。
传递闭包对应正长度可达性。若 ，则
对于不同端点，可从游走中删去回路得到至多 条边的路径；同一端点的正长度可达性由至多 条边的简单有向圈见证。因此需要保留 来覆盖自环的可达情形。
例如 ，则 。若 ，没有可继续接上的两条边，，所以 。
在 上取 ，每个 对应距离恰为 的点对，没有有限阶截断能给出全部传递闭包。
2. 闭包的共同性质
对 均有：
- 扩张性：。
- 单调性：。
- 幂等性：。
单调性可由最小性直接得到： 是具有所需性质且包含 的关系，因此 。
最后一个包含可以严格：、 各自传递，但合并后新增路径 ，闭包还需补 。
2.1. 原有性质是否保留
自反性经 、 后仍保留；对称性经 、 后仍保留；传递性经 后仍保留。
其中 保持对称性，是因为对称关系中每条有向游走都可反向行走； 保持传递性，是因为新补的恒等边不会产生新的端点组合。
一般不保持传递性。取 ，原关系传递； 中有 ，却没有 ，所以不传递。
3. 闭包的复合次序
自反闭包与另外两种闭包分别可交换，因为补恒等边既不产生新的反向边，也不改变正长度路径的端点；它只把零长度可达关系加入结果。
对称闭包与传递闭包满足
但通常不相等。仍取 ： 不含 ， 却包含它。
等价闭包
它自反、对称、传递，且是包含 的最小等价关系。先把边双向化，再取可达关系，最后补全孤立顶点的自环；所得等价类正是忽略原边方向后的连通分量。