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 同余：
a≡b (mod n) ⇔ n | (a-b)它把整数划分为 n 个剩余类。模 3 时：
[0], [1], [2]每个整数恰好落入一个类。
等价关系与划分互相对应
集合 A 的划分是一组非空子集，满足：
- 两两不相交；
- 并集为
A。
等价关系的等价类形成划分。反过来，给定划分，可以定义：
a~b ⇔ a 与 b 位于同一块这一定是等价关系。
因此“选择对象代表”通常包含两层：
- 定义哪些对象被视作等价；
- 为每个等价类选择规范代表。
URL 规范化、编译器公共子表达式和缓存键设计都在做类似工作。规范化函数必须保证等价对象得到同一代表，同时不要把本不等价的对象错误合并。
程序相等与哈希
对象的 equals 若用作集合和 Map 键，应表现为等价关系。Java 的契约要求相等具有自反、对称、传递和一致性等性质；相等对象还必须拥有相同 hashCode。
但 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 合并不同控制流路径，迭代到不动点。
“格”不是任意层级结构。若某对元素没有唯一 join 或 meet，就不是格。
依赖图与拓扑顺序
无环依赖图的可达关系形成严格偏序。拓扑排序给出一个与偏序兼容的线性顺序：若 a 必须先于 b，排序中 a 出现在 b 前。
不可比较任务可以按多种顺序排列，所以拓扑序可能不唯一。检测到环说明无法形成严格依赖顺序；构建系统应报告环路路径，而不是任意打破边。
文件系统若只看普通树中的“祖先”关系，可形成偏序；加入符号链接后可能出现环或多路径，不能再简单等同目录树偏序。
子类型往往先是预序
子类型通常满足自反和传递，但两个语法不同的类型可能互为子类型。若不把互为子类型的类型视为等价类，反对称性未必按语法相等成立。因此在形式化语境中，子类型关系常先称为预序，再对相互可替代的类型取商得到偏序。
实际语言规则还涉及型变、结构/名义类型和 null，不能只用集合包含图概括全部语义。
完成检查
- 证明模 5 同余是等价关系，并写出五个等价类；
- 给字符串定义“不区分大小写相等”，说明规范代表如何选择；
- 画
𝒫({a,b,c})的 Hasse 图； - 找出其中
{a}与{b,c}的 join 和 meet； - 为一个有五个任务的依赖图给出两个不同拓扑序；
- 构造一个有多个极小元素但没有最小元素的偏序。