等价关系

等价关系（equivalence relation）把一个集合中的对象按某种“视为相同”的规则分组。关系 $\sim$ 定义在集合 $A$ 上时，须同时满足：每个 $a$ 有 $a\sim a$（自反）；若 $a\sim b$ 则 $b\sim a$（对称）；若 $a\sim b$ 且 $b\sim c$ 则 $a\sim c$（传递）。

用余数分组整数

在整数上规定 $a\sim b$ 当且仅当 $3\mid (a-b)$。例如 $2\sim 8$，因为 $8-2=6$；但 $2\nsim 6$，因为差 4 不是 3 的倍数。自反性来自 $3\mid 0$；对称性来自差改号仍可整除；传递性来自 $$a-c=(a-b)+(b-c).$$ 若右边两项都是 3 的倍数，其和也是。因此这确实是等价关系。

与 2 等价的整数构成等价类 $[2]=\{\dots ,-4,-1,2,5,8,\dots \}$。全体整数恰被 $[0],[1],[2]$ 三类覆盖，且任意两类要么相同、要么没有公共元素。原因是：一个元素若同时落入两类，传递与对称性便迫使两个代表等价，两类因而相同。

同一类不等于同一个对象

在上例中，$2\sim 8$，但整数 $2\ne 8$。等价关系保留了问题关心的属性——这里是除以 3 的余数——而忽略其他差别。不能只凭“看起来像”给对象分类；例如“两个整数相差不超过 1”虽然自反、对称，却不传递：$1$ 与 $2$、$2$ 与 $3$ 都符合，$1$ 与 $3$ 不符合。

参考资料

• MIT，Mathematics for Computer Science，Relations and Partial Orders。
• MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
• 继续阅读：同余、偏序关系、集合。