请说明等价关系的定义,并举出集合划分(商集)与模 n 同余等例子,解释等价类与划分的关系。
设 R 是集合 A 上的二元关系,若 R 同时满足:
则称 R 为等价关系。
等价类:与 a 等价的全体 [a] = {x∈A | (x,a)∈R}。等价类互不相交且并为 A,构成 A 的一个划分(partition);反过来任一划分也唯一确定一个等价关系。等价类的集合称为商集 A/R。
经典例子——模 n 同余:整数上 a ≡ b (mod n)(n | a−b)是等价关系。模 3 同余把整数分为 3 个等价类 [0],[1],[2](即余数 0/1/2),商集即 ℤ₃。
应用:哈希分桶、编译器中的作用域分组、类型系统等,本质都是用等价关系把元素归并成互不相交的类。
题目与答案就在本页;收藏、批注和错题重练在应用内