9.5 等价关系

相关笔记： 9.4 关系的闭包 | 9.6 偏序关系

概览

本节系统介绍了等价关系（equivalence relation）的概念、性质及其与划分（partition）之间的深刻联系。等价关系是同时满足自反性、对称性和传递性的关系，它能将集合中的元素分成若干不相交的等价类。本节的核心结论是：等价关系与划分之间存在一一对应——每个等价关系确定一个划分，每个划分也确定一个等价关系。

等价关系：同时满足自反、对称、传递的关系，用 $\sim$ 表示

等价类 $[a]_{R}$ ：与元素 $a$ 等价的所有元素组成的集合

等价类性质（定理1）：两个等价类要么相等，要么不相交

等价关系与划分的一一对应（定理2）：等价类的集合构成划分，反之亦然

同余关系 $a \equiv b (mod m)$ ：最重要的等价关系实例

Bell 数 $B_{n}$ ： $n$ 元集合上的等价关系（划分）个数

一、知识结构总览

graph TB
    A["9.5 等价关系 Equivalence Relations"] --> B["等价关系的定义"]
    A --> C["等价类"]
    A --> D["等价类与划分"]
    A --> E["同余关系"]
    A --> F["Bell数与划分计数"]

    B --> B1["自反 + 对称 + 传递"]
    B --> B2["等价元素 a ~ b"]
    B --> B3["正例：相等关系、同余、字符串前缀"]
    B --> B4["反例：整除关系、接近关系"]

    C --> C1["定义：[a]_R = {s | (a,s) ∈ R}"]
    C --> C2["代表元：类中任一元素"]
    C --> C3["同余类 [a]_m"]
    C --> C4["字符串等价类"]

    D --> D1["定理1：等价类要么相等要么不相交"]
    D --> D2["定理2：等价关系 ↔ 划分 一一对应"]
    D --> D3["从划分构造等价关系"]
    D --> D4["从等价关系得到划分"]

    E --> E1["a ≡ b (mod m) 的定义"]
    E --> E2["自反性证明"]
    E --> E3["对称性证明"]
    E --> E4["传递性证明"]
    E --> E5["m 个同余类 [0]_m, [1]_m, ..., [m-1]_m"]

    F --> F1["Bell数 B_n 的定义"]
    F --> F2["递推公式"]
    F --> F3["初始条件 B_0 = 1"]

二、核心思想

核心思想

本节的核心思想是等价关系将集合"分类"。当我们只关心元素属于哪个类别，而不关心其具体身份时，等价关系提供了数学工具。例如，编译器只检查变量名的前 $n$ 个字符（将不同的长名称视为等价），整数除以 $m$ 的余数相同则视为等价。等价关系的本质是：在保持自反、对称、传递的前提下，用"等价类"代替单个元素进行推理。这一定理（定理2）建立了等价关系与划分之间的一一对应，是后续学习群论中”陪集”、拓扑学中”商空间”等概念的基础。

1. 等价关系的定义

等价关系（Equivalence Relation）

设 $R$ 是集合 $A$ 上的关系。若 $R$ 同时满足以下三个性质，则称 $R$ 为 $A$ 上的等价关系：

自反性：对任意 $a \in A$ ，有 $(a, a) \in R$

对称性：若 $(a, b) \in R$ ，则 $(b, a) \in R$

传递性：若 $(a, b) \in R$ 且 $(b, c) \in R$ ，则 $(a, c) \in R$

若 $a$ 和 $b$ 在等价关系 $R$ 下相关，记作 $a \sim b$ ，称 $a$ 和 $b$ 是等价的（equivalent）。

例1：相等关系是等价关系

设 $R$ 是整数集上的关系， $a R b$ 当且仅当 $a = b$ 或 $a = - b$ 。

自反性： $a = a$ ，故 $(a, a) \in R$

对称性：若 $a R b$ ，则 $a = b$ 或 $a = - b$ ，即 $b = a$ 或 $b = - a$ ，故 $b R a$

传递性：若 $a R b$ 且 $b R c$ ，则 $a = \pm b$ 且 $b = \pm c$ ，故 $a = \pm c$ ，即 $a R c$

因此 $R$ 是等价关系。

例2：实数上的"差为整数"关系

设 $R$ 是实数集上的关系， $a R b$ 当且仅当 $a - b$ 是整数。

自反性： $a - a = 0$ 是整数，故 $a R a$

对称性：若 $a R b$ ，则 $a - b$ 是整数，故 $b - a = - (a - b)$ 也是整数，故 $b R a$

传递性：若 $a R b$ 且 $b R c$ ，则 $a - b$ 和 $b - c$ 都是整数，故 $a - c = (a - b) + (b - c)$ 也是整数，故 $a R c$

因此 $R$ 是等价关系。

2. 同余关系

同余模 $m$ （Congruence Modulo $m$ ）

设 $m$ 为正整数。整数集上的关系

$R = {(a, b) ∣ a \equiv b (mod m)}$

称为==同余模 $m$ == 关系，其中 $a \equiv b (mod m)$ 表示 $m$ 整除 $a - b$ 。

同余模 $m$ 是等价关系

设 $m$ 为正整数，则同余模 $m$ 是整数集上的等价关系。

证明：

自反性： $a - a = 0 = 0 \cdot m$ ，故 $m ∣ (a - a)$ ，即 $a \equiv a (mod m)$ 。

对称性：设 $a \equiv b (mod m)$ ，则 $m ∣ (a - b)$ ，即存在整数 $k$ 使得 $a - b = k m$ 。于是 $b - a = (- k) m$ ，故 $m ∣ (b - a)$ ，即 $b \equiv a (mod m)$ 。

传递性：设 $a \equiv b (mod m)$ 且 $b \equiv c (mod m)$ ，则 $m ∣ (a - b)$ 且 $m ∣ (b - c)$ ，即存在整数 $k, l$ 使得 $a - b = k m$ 且 $b - c = l m$ 。于是

$a - c = (a - b) + (b - c) = k m + l m = (k + l) m$

故 $m ∣ (a - c)$ ，即 $a \equiv c (mod m)$ 。

因此，同余模 $m$ 是等价关系。 $■$

例3：同余模 4 的等价类

同余模 4 将整数集分为 4 个等价类：

$[0]_{4} = {\dots, - 8, - 4, 0, 4, 8, \dots}$ （被 4 整除的整数）

$[1]_{4} = {\dots, - 7, - 3, 1, 5, 9, \dots}$ （除以 4 余 1 的整数）

$[2]_{4} = {\dots, - 6, - 2, 2, 6, 10, \dots}$ （除以 4 余 2 的整数）

$[3]_{4} = {\dots, - 5, - 1, 3, 7, 11, \dots}$ （除以 4 余 3 的整数）

每个整数恰好属于其中一个等价类。

3. 等价类

等价类（Equivalence Class）

设 $R$ 是集合 $A$ 上的等价关系。元素 $a \in A$ 的等价类（记为 $[a]_{R}$ 或简写为 $[a]$ ）定义为：

$[a]_{R} = {s \in A ∣ (a, s) \in R}$

即所有与 $a$ 等价的元素组成的集合。若 $b \in [a]_{R}$ ，则称 $b$ 是该等价类的一个代表元（representative）。

等价类中的任何元素都可以作为代表元——代表元的选择不具有特殊性。

例4：字符串前缀等价类

设 $R_{3}$ 是所有比特串上的关系： $s R_{3} t$ 当且仅当 $s = t$ ，或 $s$ 和 $t$ 都至少有 3 位且前 3 位相同。

例如， $[011]_{R_{3}} = {011, 0110, 0111, 01100, 01101, 01110, 01111, \dots}$ 。

长度小于 3 的比特串各自构成只含自身的等价类： $[λ] = {λ}$ ， $[0] = {0}$ ， $[1] = {1}$ ， $[00] = {00}$ ， $[01] = {01}$ ， $[10] = {10}$ ， $[11] = {11}$ 。

例5：C 语言标识符等价类

在标准 C 中，编译器只检查标识符的前 31 个字符。两个标识符被视为相同当且仅当它们在关系 $R_{31}$ 下等价。

标识符 “Number of tropical storms”（25 个字符）的等价类只含自身

标识符 “Number of named tropical storms”（恰好 31 个字符）的等价类包含所有以这 31 个字符开头的标识符

“Number of named tropical storms in the Atlantic in 2017” 与 “Number of named tropical storms” 属于同一等价类（前 31 个字符相同）

4. 等价类的性质

定理1：等价类要么相等要么不相交

设 $R$ 是集合 $A$ 上的等价关系， $a, b \in A$ 。以下三个命题等价：

(i) $a R b$

(ii) $[a] = [b]$

(iii) $[a] \cap [b] \neq = \emptyset$

证明：

(i) $\Rightarrow$ (ii)：设 $a R b$ 。要证 $[a] = [b]$ ，分别证 $[a] \subseteq [b]$ 和 $[b] \subseteq [a]$ 。

设 $c \in [a]$ ，即 $a R c$ 。由 $a R b$ 和 $R$ 的对称性得 $b R a$ 。由 $b R a$ 、 $a R c$ 和 $R$ 的传递性得 $b R c$ ，故 $c \in [b]$ 。因此 $[a] \subseteq [b]$ 。

类似地，设 $c \in [b]$ ，即 $b R c$ 。由 $a R b$ 和 $b R c$ 及传递性得 $a R c$ ，故 $c \in [a]$ 。因此 $[b] \subseteq [a]$ 。

综上 $[a] = [b]$ 。

(ii) $\Rightarrow$ (iii)：设 $[a] = [b]$ 。因为 $R$ 是自反的， $a \in [a]$ ，故 $[a] \neq = \emptyset$ ，从而 $[a] \cap [b] = [a] \neq = \emptyset$ 。

(iii) $\Rightarrow$ (i)：设 $[a] \cap [b] \neq = \emptyset$ ，则存在 $c \in [a] \cap [b]$ ，即 $a R c$ 且 $b R c$ 。由对称性得 $c R b$ 。由传递性， $a R c$ 且 $c R b$ 推出 $a R b$ 。

由于三个命题互相蕴含，它们是等价的。 $■$

5. 等价关系与划分的一一对应

划分（Partition）

集合 $S$ 的划分是 $S$ 的一组不相交的非空子集 ${A_{i} ∣ i \in I}$ （ $I$ 为指标集），使得：

对所有 $i \in I$ ， $A_{i} \neq = \emptyset$

当 $i \neq = j$ 时， $A_{i} \cap A_{j} = \emptyset$

$⋃_{i \in I} A_{i} = S$

即划分将 $S$ 不重叠、不遗漏地分成若干块。

定理2：等价关系与划分的一一对应

设 $R$ 是集合 $S$ 上的等价关系。则 $R$ 的等价类构成 $S$ 的一个划分。反之，给定 $S$ 的一个划分 ${A_{i} ∣ i \in I}$ ，存在等价关系 $R$ 使得其等价类恰好是 $A_{i}$ （ $i \in I$ ）。

证明（等价关系 $\Rightarrow$ 划分）：

设 $R$ 是 $S$ 上的等价关系。需要验证等价类满足划分的三个条件：

非空性：对任意 $a \in S$ ，因为 $R$ 自反， $a \in [a]$ ，故 $[a] \neq = \emptyset$ 。

不相交性：由定理1，若 $[a] \neq = [b]$ ，则 $[a] \cap [b] = \emptyset$ 。

并集为 $S$ ： $⋃_{a \in S} [a] = S$ ，因为每个 $a \in S$ 都属于其自身的等价类 $[a]$ 。

证明（划分 $\Rightarrow$ 等价关系）：

设 ${A_{i} ∣ i \in I}$ 是 $S$ 的划分。定义关系 $R$ ： $(x, y) \in R$ 当且仅当 $x$ 和 $y$ 属于划分中的同一个子集 $A_{i}$ 。

自反性：每个 $a \in S$ 属于某个 $A_{i}$ ， $a$ 与自身在同一子集中，故 $(a, a) \in R$ 。

对称性：若 $(a, b) \in R$ ，则 $a, b$ 在同一子集中，故 $b, a$ 也在同一子集中，即 $(b, a) \in R$ 。

传递性：若 $(a, b) \in R$ 且 $(b, c) \in R$ ，则 $a, b$ 在同一子集 $X$ 中， $b, c$ 在同一子集 $Y$ 中。因为 $b \in X \cap Y$ 且 $X \neq = \emptyset$ 、 $Y \neq = \emptyset$ ，由划分的不相交性得 $X = Y$ 。故 $a, c$ 也在同一子集中，即 $(a, c) \in R$ 。

因此 $R$ 是等价关系，其等价类恰好是划分中的子集 $A_{i}$ 。 $■$

例6：从划分构造等价关系

设 $S = {1, 2, 3, 4, 5, 6}$ ，划分为 $A_{1} = {1, 2, 3}$ ， $A_{2} = {4, 5}$ ， $A_{3} = {6}$ 。

对应的等价关系为： $R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3),$ $(4, 4), (4, 5), (5, 4), (5, 5), (6, 6)}$

6. Bell 数与划分计数

Bell 数（Bell Numbers）

设 $p (n)$ 表示 $n$ 元集合上的等价关系个数（由定理2，也等于 $n$ 元集合的划分数）。 $p (n)$ 称为Bell 数，记作 $B_{n}$ 。

$B_{n}$ 满足以下递推关系：

$B_{n} = \sum_{j = 0}^{n - 1} (j n - 1) B_{n - j - 1}$

初始条件： $B_{0} = 1$ 。

前几个 Bell 数为： $B_{0} = 1$ ， $B_{1} = 1$ ， $B_{2} = 2$ ， $B_{3} = 5$ ， $B_{4} = 15$ ， $B_{5} = 52$ ， $B_{6} = 203$ ， $\dots$

Bell 数递推公式的直观理解

考虑 $n$ 元集合 ${a_{1}, a_{2}, \dots, a_{n}}$ 的所有划分。固定元素 $a_{1}$ ，考虑 $a_{1}$ 所在的块的大小：

若 $a_{1}$ 所在的块有 $j + 1$ 个元素（ $j$ 个其他元素与 $a_{1}$ 同块），则从剩余 $n - 1$ 个元素中选 $j$ 个与 $a_{1}$ 同块，有 $(j n - 1)$ 种选法。剩下的 $n - j - 1$ 个元素需要划分，有 $B_{n - j - 1}$ 种方式。

$j$ 的取值范围是 $0$ 到 $n - 1$ （ $j = 0$ 时 $a_{1}$ 独占一块）。

对所有 $j$ 求和即得递推公式。

三、补充理解与易混淆点

补充理解

补充1：等价关系的历史与应用

等价关系的概念可追溯到 19 世纪末。Leopold Kronecker 在研究代数数论时系统使用了同余关系。等价关系在现代数学中无处不在：在代数中用于定义商群和商环，在拓扑学中用于定义商空间和等价度量，在集合论中用于定义基数（通过双射等价关系）。

在计算机科学中，等价关系有广泛应用：编译器中的标识符等价（如本节讨论的 C 语言前缀匹配）、数据库中的实体识别（record linkage）、图论中的连通分量（连通关系是等价关系）、程序分析中的指针等价（alias analysis）等。

Equivalence Relation - Wikipedia — 等价关系的百科介绍

Bell Number - Wikipedia — Bell 数的百科介绍来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill, Section 9.5. 来源：Halmos, P. R. (1960). Naive Set Theory. Van Nostrand, Chapter 12 (Partitions).

补充2：等价关系与函数的逆像

等价关系与函数有深刻的联系。给定函数 $f : A \to B$ ，定义 $A$ 上的关系 $R_{f}$ ： $(x, y) \in R_{f}$ 当且仅当 $f (x) = f (y)$ 。则 $R_{f}$ 是 $A$ 上的等价关系。

反之，给定 $A$ 上的等价关系 $R$ ，可以构造一个函数 $f : A \to A / R$ （ $A / R$ 是等价类的集合），使得 $f (a) = [a]$ 。这个函数称为自然投影（canonical projection）或商映射。

这说明：每个等价关系都可以看作某个函数的"等值核"，每个函数也自然诱导一个等价关系。这一对应关系在代数、拓扑和范畴论中都是基本工具。来源：Enderton, H. B. (1977). Elements of Set Theory. Academic Press, Chapter 3. 来源：Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill, Section 9.5.

易混淆点

误区1：等价关系 vs. 一般二元关系

❌ 认为自反+对称就足以保证等价关系

✅ 必须同时满足自反、对称、传递三个条件

典型反例： $R = {(x, y) \in R^{2} ∣ ∣ x - y ∣ < 1}$ 是自反且对称的，但不是传递的（例如 $2.8 R 1.9$ 且 $1.9 R 1.1$ ，但 $∣2.8 - 1.1∣ = 1.7 > 1$ ，故 $2.8 R 1.1$ ）

误区2：等价类 vs. 子集

❌ 认为等价类是任意选取的子集

✅ 等价类由等价关系唯一确定，且满足定理1的关键性质：要么相等，要么不相交

❌ 认为不同代表元一定给出不同的等价类

✅ 若 $b \in [a]$ ，则 $[a] = [b]$ ，代表元的选择不影响等价类本身

误区3：整除关系不是等价关系

❌ 认为”整除”关系是等价关系（因为它看起来”公平”）

✅ 正整数集上的整除关系是自反和传递的，但不是对称的（例如 $2 ∣ 4$ 但 $4 ∤ 2$ ）

整除关系实际上是偏序关系（见 9.6 节），不是等价关系

四、习题精选

习题概览

题号范围核心考点难度
1-3 判断关系是否为等价关系，指出缺少的性质 ⭐
4-6 构造等价关系并求等价类 ⭐⭐
7-10 证明特定关系是等价关系 ⭐⭐
11-14 比特串等价关系 ⭐⭐
15-16 有序对上的等价关系 ⭐⭐⭐
17-18 微积分相关等价关系（导数相等） ⭐⭐⭐
19-20 URL/网页等价关系 ⭐⭐
21-23 有向图判断等价关系 ⭐⭐
24-25 比特串等价关系（含 1 的个数相同） ⭐⭐⭐
26-34 求等价类 ⭐⭐
35-38 同余类计算 ⭐⭐
39-40 有序对等价类的几何解释 ⭐⭐⭐
41-46 判断集合族是否为划分 ⭐⭐⭐
47-48 从划分构造等价关系 ⭐⭐⭐
49-54 划分的加细（refinement） ⭐⭐⭐⭐
55-56 等价关系的交与并 ⭐⭐⭐
57-58 Bell 数递推与计算 ⭐⭐⭐⭐
59-67 项链/棋盘着色等价关系 ⭐⭐⭐⭐

题号范围	核心考点	难度
1-3	判断关系是否为等价关系，指出缺少的性质	⭐
4-6	构造等价关系并求等价类	⭐⭐
7-10	证明特定关系是等价关系	⭐⭐
11-14	比特串等价关系	⭐⭐
15-16	有序对上的等价关系	⭐⭐⭐
17-18	微积分相关等价关系（导数相等）	⭐⭐⭐
19-20	URL/网页等价关系	⭐⭐
21-23	有向图判断等价关系	⭐⭐
24-25	比特串等价关系（含 1 的个数相同）	⭐⭐⭐
26-34	求等价类	⭐⭐
35-38	同余类计算	⭐⭐
39-40	有序对等价类的几何解释	⭐⭐⭐
41-46	判断集合族是否为划分	⭐⭐⭐
47-48	从划分构造等价关系	⭐⭐⭐
49-54	划分的加细（refinement）	⭐⭐⭐⭐
55-56	等价关系的交与并	⭐⭐⭐
57-58	Bell 数递推与计算	⭐⭐⭐⭐
59-67	项链/棋盘着色等价关系	⭐⭐⭐⭐

题1：判断等价关系

题目

以下哪些关系是 ${0, 1, 2, 3}$ 上的等价关系？指出非等价关系缺少的性质。

a) ${(0, 0), (1, 1), (2, 2), (3, 3)}$

b) ${(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}$

解答

a) 这是相等关系（恒等关系）。

自反：每个元素都有 $(a, a)$ ，满足

对称：只有 $(a, a)$ 形式的有序对， $(a, a)$ 的对称还是 $(a, a)$ ，满足

传递：只有 $(a, a)$ 形式，若 $(a, b) \in R$ 且 $(b, c) \in R$ ，则 $a = b = c$ ，故 $(a, c) = (a, a) \in R$ ，满足

因此 a) 是等价关系。

b)

自反： $(0, 0), (2, 2), (3, 3)$ 都在，但 $(1, 1)$ 不在，不满足自反性

对称：每对 $(a, b)$ 都有 $(b, a)$ ，满足

传递： $(0, 2)$ 和 $(2, 3)$ 在 $R$ 中，但 $(0, 3)$ 不在 $R$ 中，不满足传递性

因此 b) 不是等价关系（缺少自反性和传递性）。

$■$

题2：证明比特串等价关系

题目

设 $R$ 是所有比特串上的关系， $s R t$ 当且仅当 $s$ 和 $t$ 包含相同个数的 1。证明 $R$ 是等价关系。

解答

设 $l (x)$ 表示比特串 $x$ 中 1 的个数。

自反性：对任意比特串 $s$ ， $l (s) = l (s)$ ，故 $s R s$ 。

对称性：若 $s R t$ ，则 $l (s) = l (t)$ ，故 $l (t) = l (s)$ ，即 $tR s$ 。

传递性：若 $s R t$ 且 $tR u$ ，则 $l (s) = l (t)$ 且 $l (t) = l (u)$ ，故 $l (s) = l (u)$ ，即 $s R u$ 。

因此 $R$ 是等价关系。

等价类： $[s] = {t ∣ t 中有 l (s) 个 1}$ 。例如， $[011]$ 是所有恰好含 2 个 1 的比特串的集合。

$■$

题3：求同余类

题目

求整数 $n$ 在模 5 下的同余类 $[n]_{5}$ ，其中 $n = 2, 3, 6, - 3$ 。

解答

$[n]_{5} = {n + 5 k ∣ k \in Z}$ 。

$[2]_{5} = {\dots, - 8, - 3, 2, 7, 12, \dots}$ （所有除以 5 余 2 的整数）

$[3]_{5} = {\dots, - 7, - 2, 3, 8, 13, \dots}$ （所有除以 5 余 3 的整数）

$[6]_{5} = {\dots, - 9, - 4, 1, 6, 11, \dots}$ （因为 $6 \equiv 1 (mod 5)$ ，所以 $[6]_{5} = [1]_{5}$ ）

$[- 3]_{5} = {\dots, - 8, - 3, 2, 7, 12, \dots}$ （因为 $- 3 \equiv 2 (mod 5)$ ，所以 $[- 3]_{5} = [2]_{5}$ ）

注意 $[6]_{5} = [1]_{5}$ 和 $[- 3]_{5} = [2]_{5}$ 体现了定理1：等价类中的任何元素都可以作为代表元。

$■$

题4：判断划分

题目

以下哪些集合族是 ${1, 2, 3, 4, 5, 6}$ 的划分？

a) ${{1, 2}, {3, 4}, {5}}$

b) ${{1, 2, 3}, {4, 5, 6}}$

解答

划分需要满足三个条件：子集非空、两两不相交、并集为全集。

a) ${{1, 2}, {3, 4}, {5}}$

非空：满足

不相交： ${1, 2} \cap {3, 4} = \emptyset$ ， ${1, 2} \cap {5} = \emptyset$ ， ${3, 4} \cap {5} = \emptyset$ ，满足

并集： ${1, 2} \cup {3, 4} \cup {5} = {1, 2, 3, 4, 5} \neq = {1, 2, 3, 4, 5, 6}$ ，不满足

因此 a) 不是划分（缺少元素 6）。

b) ${{1, 2, 3}, {4, 5, 6}}$

非空：满足

不相交： ${1, 2, 3} \cap {4, 5, 6} = \emptyset$ ，满足

并集： ${1, 2, 3} \cup {4, 5, 6} = {1, 2, 3, 4, 5, 6}$ ，满足

因此 b) 是划分。

$■$

题5：Bell 数递推计算

题目

利用递推公式 $B_{n} = \sum_{j = 0}^{n - 1} (j n - 1) B_{n - j - 1}$ ，已知 $B_{0} = 1$ ，计算 $B_{1}, B_{2}, B_{3}, B_{4}$ 。

解答

$B_{1}$ ： $B_{1} = \sum_{j = 0}^{0} (j 0) B_{0 - j} = (0 0) B_{0} = 1 \times 1 = 1$

$B_{2}$ ： $B_{2} = \sum_{j = 0}^{1} (j 1) B_{1 - j} = (0 1) B_{1} + (1 1) B_{0} = 1 \times 1 + 1 \times 1 = 2$

$B_{3}$ ： $B_{3} = \sum_{j = 0}^{2} (j 2) B_{2 - j} = (0 2) B_{2} + (1 2) B_{1} + (2 2) B_{0} = 1 \times 2 + 2 \times 1 + 1 \times 1 = 5$

$B_{4}$ ： $B_{4} = \sum_{j = 0}^{3} (j 3) B_{3 - j} = (0 3) B_{3} + (1 3) B_{2} + (2 3) B_{1} + (3 3) B_{0} = 1 \times 5 + 3 \times 2 + 3 \times 1 + 1 \times 1 = 15$

验证：3 元集合 ${a, b, c}$ 的 5 种划分： ${{a, b, c}}$ ， ${{a}, {b, c}}$ ， ${{b}, {a, c}}$ ， ${{c}, {a, b}}$ ， ${{a}, {b}, {c}}$ 。 $B_{3} = 5$ 正确。

$■$

解题思路提示

等价关系相关问题的解题方法论：

证明等价关系：逐一验证自反性、对称性、传递性，缺一不可

否定等价关系：只需找到一个不满足的性质即可（通常最容易检查对称性）

求等价类：明确等价关系的定义，找出所有满足条件的元素

判断划分：检查三个条件——非空、不相交、并集为全集

划分与等价关系的互化：利用定理2，划分的子集就是等价类

五、视频学习指南

视频资源

资源链接对应内容备注
Rosen 8e Section 9.5 教材原文完整定义、定理与例题英文教材
MIT 6.042J Lecture 10 链接等价关系与等价类英文，MIT开放课程
TrevTutor - Equivalence Relations 链接等价关系完整讲解英文，适合入门

资源	链接	对应内容	备注
Rosen 8e Section 9.5	教材原文	完整定义、定理与例题	英文教材
MIT 6.042J Lecture 10	链接	等价关系与等价类	英文，MIT开放课程
TrevTutor - Equivalence Relations	链接	等价关系完整讲解	英文，适合入门

六、教材原文

教材原文

“In some programming languages the names of variables can contain an unlimited number of characters. However, there is a limit on the number of characters that are checked when a compiler determines whether two variables are equal.”

“These two relations, R and congruence modulo 4, are examples of equivalence relations, namely, relations that are reflexive, symmetric, and transitive. In this section we will show that such relations split sets into disjoint classes of equivalent elements.”

“The equivalence classes of an equivalence relation on a set form a partition of the set. Conversely, every partition of a set can be used to form an equivalence relation.”

参见 Wiki

等价关系 — 等价关系的定义与判定
等价类 — 等价类的定义与性质
划分 — 集合划分的定义
同余关系 — 同余模 $m$ 的定义与证明
Bell数 — Bell 数的定义与递推公式
代表元 — 等价类的代表元
商集 — 等价类集合 $A / R$

关系

CS Wiki

探索

9.5 等价关系

一、知识结构总览

二、核心思想

1. 等价关系的定义

2. 同余关系

3. 等价类

4. 等价类的性质

5. 等价关系与划分的一一对应

6. Bell 数与划分计数

三、补充理解与易混淆点

补充理解

易混淆点

四、习题精选

题1：判断等价关系

题2：证明比特串等价关系

题3：求同余类

题4：判断划分

题5：Bell 数递推计算

五、视频学习指南

六、教材原文

参见 Wiki

关系图谱

目录

反向链接