等价关系

父级：order-theory

二元关系 ~ 的另一大分类（与序关系族是一对孪生兄弟）。

等价关系

集合上的一个关系 ~，满足

• 自反性 — a ~ a；
• 对称性 — a ~ b ⟹ b ~ a；
• 传递性 — a ~ b 且 b ~ c ⟹ a ~ c。

它给出什么：等价类与商集

~ 把集合划分成若干两两不相交的等价类 [a] = { x : x ~ a }；这些等价类的全体构成商集 S/~。反过来，每一个划分都是一个等价关系——两者是同一份数据。

与序关系的鲜明对比

对称性 vs 反对称性，就是全部的区别：

• a≤b 且 b≤a ⟹ 同一等价类（等价关系）vs ⟹ 相等（partial order）。
• 预序可以正则地拆分成一个等价关系（其对称核 a~b ⟺ a≤b≤a）加上商集上的一个偏序。所以"预序 = 等价关系 + 序关系"——这两个关系族正是预序的两个组成部分。

它们出现在哪里

相等、模 n 同余、"基数相同"、同构、Myhill–Nerode 不可区分性（其等价类正是 DFA 状态所对应的那个 ≡）、双模拟（modal logic）。凡是你在"把无关紧要的区别商掉"的地方，起作用的正是一个等价关系。