5.2 等价关系与偏序：分类、依赖和格
有些关系把对象归入同一类，例如“两个请求具有相同规范化 URL”；另一些关系表达先后或包含，例如“任务 A 必须在任务 B 之前完成”。前者通向等价关系，后者通向偏序。
等价关系产生分类
集合 A 上的等价关系 ~ 同时满足：
自反：a~a
对称：a~b → b~a
传递：a~b ∧ b~c → a~c元素 a 的等价类：
[a]={x∈A | x~a}对固定正整数 n，模 n 同余：
a≡b (mod n) ⇔ n | (a-b)它把整数划分为 n 个剩余类。模 3 时：
[0], [1], [2]每个整数恰好落入一个类。
等价关系与划分互相对应
集合 A 的划分是一组非空子集，满足：
- 两两不相交；
- 并集为
A。
等价关系的等价类形成划分。反过来，给定划分，可以定义：
a~b ⇔ a 与 b 位于同一块这一定是等价关系。
因此“选择对象代表”通常包含两层：
- 定义哪些对象被视作等价；
- 为每个等价类选择规范代表。
URL 规范化、编译器公共子表达式和缓存键设计都在做类似工作。规范化函数必须保证等价对象得到同一代表，同时不要把本不等价的对象错误合并。
例如明确定义 a~b ⇔ a.casefold()==b.casefold()，固定版本的字符串转换是一个确定函数，其输出相等自然满足自反、对称和传递。Python 3 的 casefold 会把德语 ß 折叠为 ss：
words = ["Straße", "STRASSE", "strasse", "Street"]
groups = {}
for word in words:
groups.setdefault(word.casefold(), []).append(word)
print(groups)
# {'strasse': ['Straße', 'STRASSE', 'strasse'], 'street': ['Street']}这只验证选定键规则形成的分类，不能证明它适合每个业务。这里没有做 Unicode 规范化，也没有定义邮箱或 URL 的大小写规则；升级 Unicode 数据版本时，持久化键还应考虑兼容性。
程序相等与哈希
非空对象的 equals 应表现为等价关系。Java 21 Object 契约 要求自反、对称、传递，以及相关字段不变时的结果一致性；相等对象还必须拥有相同 hashCode。
固定且稳定的哈希函数确实会通过“哈希值相同”定义一种等价关系，但它通常比对象相等更粗：不相等对象也可能落入同一类。正确方向是：
a.equals(b) → a.hashCode()==b.hashCode()反方向不成立。把哈希值当唯一身份可能合并不相等对象。
浮点数、代理对象、跨类型数值和可变字段会使相等性设计更复杂。对象放入哈希集合后，不应改变参与相等和哈希的状态。
偏序：允许不可比较
集合 A 上的偏序 ≤ 满足：
自反：a≤a
反对称：a≤b ∧ b≤a → a=b
传递：a≤b ∧ b≤c → a≤c(A,≤) 称为偏序集。
集合包含 ⊆ 是偏序。两个集合 {read} 与 {write} 互不包含，因此不可比较。偏序不要求任何两个元素都能排序。
若任意 a,b 都有 a≤b 或 b≤a，则是全序。整数上的普通 ≤ 是全序。
严格偏序可以由：
a<b ⇔ a≤b ∧ a≠b得到，它反自反且传递。
Hasse 图去掉可推导边
有限偏序可用 Hasse 图表示：
- 不画自反环；
- 不画能由传递性推导的边；
- 较大的元素通常放上方。
对幂集 𝒫({a,b}) 按包含排序：
{a,b}
/ \
{a} {b}
\ /
∅∅⊆{a,b} 没有直接边，因为可经 {a} 或 {b} 推导。
最小、极小、最小上界不要混淆
- 最小元素：
m≤x对所有 x 成立，若存在则唯一； - 极小元素：没有其他元素严格小于它，可能有多个；
- 最大/极大：对偶定义。
一个任务依赖偏序里可能有多个当前可执行的极小任务，却没有唯一最小任务。
对集合 S：
- 上界
u满足所有s∈S都有s≤u； - 最小上界（join）是所有上界中最小的；
- 下界和最大下界（meet）对偶。
“最小上界”不是 S 中最小元素，也未必属于 S。
格把 join 与 meet 变成运算
若偏序集中任意两个元素都有唯一最小上界和最大下界，则称为格。
幂集按包含构成格：
A ∨ B = A∪B // join
A ∧ B = A∩B // meet在固定全集的幂集上，加上补集、空集和全集后形成布尔代数。数据流分析可把抽象状态组织成格，通过 join 合并路径状态。有限高度格上，从底元素开始用单调转移函数沿上升链迭代，可以达到不动点；无限高度格可能需要 widening 等加速机制。只有“状态是格”还不足以保证迭代终止。
“格”不是任意层级结构。若某对元素没有唯一 join 或 meet，就不是格。
依赖图与拓扑顺序
无环依赖图按正长度路径定义的可达关系形成严格偏序；若包含零长度路径，则是自反的非严格偏序。拓扑排序给出一个与偏序兼容的线性顺序：若 a 必须先于 b，排序中 a 出现在 b 前。
不可比较任务可以按多种顺序排列，所以拓扑序可能不唯一。检测到环说明无法形成严格依赖顺序；构建系统应报告环路路径，而不是任意打破边。
Python 3.9+ 标准库 graphlib 的输入映射是“节点→前驱集合”，方向与很多邻接表相反。下面只验证依赖约束和最后一个任务，不依赖两个并列任务的具体顺序：
from graphlib import TopologicalSorter, CycleError
predecessors = {"build": {"lint", "test"}, "lint": set(), "test": set()}
order = tuple(TopologicalSorter(predecessors).static_order())
positions = {task: i for i, task in enumerate(order)}
assert all(positions[p] < positions[task]
for task, parents in predecessors.items() for p in parents)
print(order[-1]) # build; lint and test may appear in either order.
try:
tuple(TopologicalSorter({"A": {"B"}, "B": {"A"}}).static_order())
except CycleError:
print("cycle")普通树中的严格“祖先”关系是严格偏序，加入“节点等于自身”后才是非严格偏序。符号链接若作为额外边参与可达性，可能引入环；多条路径本身不会破坏偏序，无环性才是这里的关键条件。
子类型往往先是预序
子类型通常满足自反和传递，但两个语法不同的类型可能互为子类型。若不把互为子类型的类型视为等价类，反对称性未必按语法相等成立。因此在形式化语境中，子类型关系常先称为预序，再对相互可替代的类型取商得到偏序。
实际语言规则还涉及型变、结构/名义类型和 null，不能只用集合包含图概括全部语义。
完成检查
- 证明模 5 同余是等价关系，并写出五个等价类；
- 给字符串定义“不区分大小写相等”，说明规范代表如何选择；
- 画
𝒫({a,b,c})的 Hasse 图； - 找出其中
{a}与{b,c}的 join 和 meet； - 为一个有五个任务的依赖图给出两个不同拓扑序；
- 构造一个有多个极小元素但没有最小元素的偏序。