关系与等价类

本页是导论的核心，讲三件层层递进的事：关系（用有序对刻画"元素之间有没有某种联系"）、等价关系（其中负责"分类"的那一类）、等价类与商集（把分好的类当成新对象）。

商集是这一页真正要交出去的东西：后面定义一个数域、构造 \(\mathbb{Z}/n\mathbb{Z}\)、乃至更一般的商空间，用的都是"把等价的东西看成同一个东西"这一手。

前置知识

• 集合与卡氏积：有序组、\(X \times X\) 的含义
• 集合的相等：\(A = B\) 当且仅当 \(A \subseteq B\) 且 \(B \subseteq A\)

二元关系

定义（二元关系）

设 \(X\) 是一个集合，\(R \subseteq X \times X\)，则称 \(R\) 是 \(X\) 上的一个（二元）关系。若 \((x, y) \in R\)，则称 \(x\) 与 \(y\) 是 \(R\)-相关的，记作

\[ x \mathrel{R} y. \]

也就是说，\(X\) 上的关系就是 \(X \times X\) 的一个子集；\(x \mathrel{R} y\) 与 \((x, y) \in R\) 是同一件事的两种写法。当 \(X\) 有限时，记 \(n = \#X\)，则由 \(\#(X \times X) = n^2\) 可知，\(X\) 上共有 \(2^{n^2}\) 个不同的二元关系。

等价关系

在各种各样的关系中，有一类关系的作用是"把元素按某种标准归类"。这类关系需要满足三条性质。

定义（等价关系）

设 \(R\) 是集合 \(X\) 上的一个关系。若 \(R\) 同时满足以下三条性质，则称 \(R\) 是 \(X\) 上的一个等价关系：

1. 自反性（reflexivity）：对任意 \(x \in X\)，都有 \(x \mathrel{R} x\)；
2. 对称性（symmetry）：对任意 \(x, y \in X\)，若 \(x \mathrel{R} y\)，则 \(y \mathrel{R} x\)；
3. 传递性（transitivity）：对任意 \(x, y, z \in X\)，若 \(x \mathrel{R} y\) 且 \(y \mathrel{R} z\)，则 \(x \mathrel{R} z\)。

理解

等价关系的三条性质恰好刻画了"同类"这个直觉：

• 自反性：自己与自己同类；
• 对称性：同类是相互的；
• 传递性：同类的"同类"仍是同类。

注意等价关系只负责分类，不负责比较大小。因此"小于"不是等价关系，而"同余""相等""相似"是。

思考

下面这些关系，哪些是等价关系？先自己判断，再看下面的例子。

• 在 \(\mathbb{Z}\) 上，"除以 \(n\) 余数相同"；
• 在学生集合上，"住在同一宿舍"；
• 在 \(\mathbb{Z}\) 上，"\(x\) 整除 \(y\)"；
• 在平面全体三角形的集合上，"相似"。

等价关系的常见例子

• 同余关系：在 \(\mathbb{Z}\) 上，固定 \(n \in \mathbb{N}^*\)，规定 \(a \equiv b \pmod n \iff n \mid (a - b)\)，读作"\(a\) 与 \(b\) 模 \(n\) 同余"。这三条性质分别来自 \(n \mid 0\)、\(n \mid (b - a)\) 以及整除的传递性。
• 同宿舍关系：在学生集合上，"住同一宿舍"是等价关系——前提是每个学生都确实住在某个宿舍里，否则自反性不成立。
• 老乡关系：按出生省份划分，"来自同一省份"是等价关系。
• 相似关系：在平面上全体三角形的集合中，"相似"是等价关系。
• 反例：\(\mathbb{Z}\) 上的整除关系满足自反性与传递性，但不满足对称性（\(2 \mid 4\) 而 \(4 \nmid 2\)），故不是等价关系。

在数域上的例子

设 \(X = \mathbb{Z}\)，下面都是 \(\mathbb{Z}\) 上的关系：

关系 \(R\)	\(x \mathrel{R} y\) 的含义	是否为等价关系
同余	\(n \mid (x - y)\)	是
相等	\(x = y\)	是
整除	\(x \mid y\)	否（缺对称性）
小于	\(x < y\)	否（缺自反性、对称性）
相邻	\(\lvert x - y \rvert \le 1\)	否（缺传递性）

等价类与商集

等价类

定义（等价类）

设 \(R\) 是集合 \(X\) 上的等价关系，\(x \in X\)。集合

\[ [x]_R = \{y \in X \mid y \mathrel{R} x\} \]

称为 \(x\) 关于 \(R\) 的等价类，\(x\) 称为该等价类的一个代表元。当不会引起歧义时，\([x]_R\) 简记为 \([x]\)。（有的教材把等价类写成 \(\overline{x}\)，指的是同一个东西；本笔记统一用方括号。）

等价类具有下列基本性质：

1. 每个等价类都是 \(X\) 的子集；
2. 每个等价类都非空，因为由自反性 \(x \in [x]\)；
3. 代表元的选取不唯一：若 \(y \in [x]\)，则 \(y\) 也是 \([x]\) 的代表元；
4. 任意两个等价类要么相等、要么不相交，即"互不相容"。

其中第 3、4 条由下面的引理统一给出。

引理

设 \(R\) 是 \(X\) 上的等价关系，\(x, y \in X\)，则

\[ x \mathrel{R} y \iff [x]_R = [y]_R. \]

证明

（\(\Leftarrow\)） 设 \([x] = [y]\)。由自反性 \(x \in [x] = [y]\)，即 \(x \mathrel{R} y\)。

（\(\Rightarrow\)） 设 \(x \mathrel{R} y\)。任取 \(z \in [x]\)，则 \(z \mathrel{R} x\)；对 \(z \mathrel{R} x\) 与假设 \(x \mathrel{R} y\) 用传递性，得 \(z \mathrel{R} y\)，故 \(z \in [y]\)，从而 \([x] \subseteq [y]\)。

同理（把 \(x, y\) 互换）可得 \([y] \subseteq [x]\)。于是 \([x] = [y]\)。

推论

设 \(R\) 是 \(X\) 上的等价关系，\([x], [y]\) 是任意两个等价类，则

\[ [x] = [y] \quad \text{或} \quad [x] \cap [y] = \varnothing . \]

证明

若 \([x] \cap [y] \ne \varnothing\)，取 \(z \in [x] \cap [y]\)。由 \(z \in [x]\) 得 \(z \mathrel{R} x\)，即 \(x \mathrel{R} z\)；由 \(z \in [y]\) 得 \(z \mathrel{R} y\)。对 \(x \mathrel{R} z\)、\(z \mathrel{R} y\) 用传递性得 \(x \mathrel{R} y\)，再由引理得 \([x] = [y]\)。

商集

定义（商集）

设 \(R\) 是集合 \(X\) 上的等价关系。\(X\) 的子集族

\[ X / R = \{[x]_R \mid x \in X\} \]

称为 \(X\) 关于 \(R\) 的商集。它的元素是等价类，而不是 \(X\) 的元素。

商集的实例

• 同余类：取 \(X = \mathbb{Z}\)，\(R\) 为模 \(n\) 同余关系（\(n \in \mathbb{N}^{*}\)）。对每个整数 \(k\)，\(k\) 所在的等价类（也叫 \(k\) 的同余类）是

  \[ [k] = \{k + nt \mid t \in \mathbb{Z}\}, \]

  也就是"除以 \(n\) 余 \(k\) 的全体整数"。把每个类的元素摊开写，就是

  \[ \begin{aligned} [0] &= \{\dots,\ -2n,\ -n,\ 0,\ n,\ 2n,\ \dots\}, \\ [1] &= \{\dots,\ 1-2n,\ 1-n,\ 1,\ 1+n,\ 1+2n,\ \dots\}, \\ [2] &= \{\dots,\ 2-2n,\ 2-n,\ 2,\ 2+n,\ 2+2n,\ \dots\}, \\ &\quad\ \vdots \\ [n-1] &= \{\dots,\ -n-1,\ -1,\ n-1,\ 2n-1,\ 3n-1,\ \dots\}. \end{aligned} \]

  商集就是由这些等价类组成的集合——它的元素是上面这些集合，而不是整数：

  \[ \mathbb{Z}/R = \{[0],\ [1],\ [2],\ \dots,\ [n-1]\}. \]

  这里可以观察三点：

  1. 它共有 \(n\) 个元素（\(n \ge 2\) 时 \([0], [1], \dots, [n-1]\) 互不相同；\(n = 1\) 时它们全是 \(\mathbb{Z}\) 本身，商集只有一个元素），通常记作 \(\mathbb{Z}/n\mathbb{Z}\)；
  2. 这些类两两不交：一个整数不可能既余 \(1\) 又余 \(2\)；
  3. 它们的并集是整个 \(\mathbb{Z}\)：每个整数除以 \(n\) 的余数必在 \(0, 1, \dots, n-1\) 之中。

  后两点合起来说明 \(\{[0], [1], \dots, [n-1]\}\) 恰好是 \(\mathbb{Z}\) 的一个划分——这正是下面一节的例子。

  关于记号

  本笔记统一用 \([k]\) 表示等价类（方括号能直接看出"这是一个类"，比横线清楚）。有的教材写成 \(\overline{k}\)，指的是同一个东西；在数域等页面读到它时，按 \([k]\) 理解即可。

• 星期的循环：把日期按"相差整数个星期"归类，商集恰好有 \(7\) 个元素，对应星期一至星期日。

• 三角形的相似类：全体三角形按相似关系分类，每个等价类就是一族形状相同的三角形。

等价关系与划分

"分成互不相交的部分"这一直觉可以用划分精确表述。

定义（划分）

设 \(X\) 是非空集合，\(\{X_i\}_{i \in I}\) 是 \(X\) 的一族非空子集。若

\[ X = \bigcup_{i \in I} X_i, \qquad X_i \cap X_j = \varnothing \quad (i \ne j), \]

则称 \(\{X_i\}_{i \in I}\) 是 \(X\) 的一个划分。当 \(I = \{1, 2, \dots, n\}\) 时，即

\[ X = X_1 \cup X_2 \cup \cdots \cup X_n, \qquad X_i \cap X_j = \varnothing \quad (i \ne j). \]

两句话合成一句：划分就是"不交并"

定义里的两条条件各负责一半，缺一不可：

• \(X_i \cap X_j = \varnothing\)（\(i \ne j\)）说的是"不交"：各块互不重叠，一个元素至多属于一块；
• \(\bigcup_{i \in I} X_i = X\) 说的是"并"：各块合起来盖满整个 \(X\)，一个元素至少属于一块。

两条合起来，就是"\(X\) 是各块的不交并"（也叫无交并，英文 disjoint union），记作

\[ X = \bigsqcup_{i \in I} X_i . \]

这里 \(\bigsqcup\) 只是把"不交"这条信息写进符号里，它所表示的集合与 \(\bigcup\) 完全一样。一句话概括：\(X\) 的每个元素恰好属于其中的一块。

图 1：集合 $X$ 的一个划分 $X = X_1 \sqcup X_2 \sqcup X_3 \sqcup X_4$。四块涂色区域分别代表 $X_1, X_2, X_3, X_4$，小点代表 $X$ 中的元素。

定理（等价关系与划分的对应）

设 \(X\) 是非空集合。

1. 若 \(R\) 是 \(X\) 上的等价关系，则商集 \(X / R\) 是 \(X\) 的一个划分；

2. 反之，若 \(\{X_i\}_{i \in I}\) 是 \(X\) 的一个划分，则规定

   \[ x \mathrel{R} y \iff \text{存在 } i \in I \text{ 使得 } x, y \in X_i, \]

得到的 \(R\) 是 \(X\) 上的等价关系，并且 \(X / R = \{X_i\}_{i \in I}\)。

因此，\(X\) 上的等价关系与 \(X\) 的划分之间存在一一对应。

证明

1. 三条条件各就各位：由自反性 \(x \in [x]\)，所以每个元素都落在某个等价类里，即 \(\bigcup_{[x] \in X / R} [x] = X\)（这是"并"）；由推论，任意两个不同的等价类不相交（这是"不交"）；又每个等价类非空。三条合起来正是说 \(X\) 是全体等价类的不交并

\[ X = \bigsqcup_{[x] \in X / R} [x], \]

即 \(X / R\) 是 \(X\) 的一个划分。

2. 自反性：\(x\) 必属于某个 \(X_i\)，故 \(x \mathrel{R} x\)。对称性显然。传递性：若 \(x, y \in X_i\) 且 \(y, z \in X_j\)，由 \(y \in X_i \cap X_j\) 与划分的两两不交性得 \(i = j\)，故 \(x, z \in X_i\)，即 \(x \mathrel{R} z\)。

最后看等价类：由定义，\([x] = X_{i}\)，其中 \(X_i\) 是含 \(x\) 的那一块，故 \(X / R = \{X_i\}_{i \in I}\)，且由划分确定的等价关系是唯一的。

命题（不交并的计数）

设 \(X\) 是有限集，且 \(X\) 是有限多块的不交并 \(X = \bigsqcup_{i \in I} X_i\)，则

\[ \#X = \sum_{i \in I} \#X_i . \]

证明

把各块的元素分别数一遍再相加：由"不交"，没有元素被数到两次；由"并"，没有元素被漏掉。所以这个和恰好把 \(X\) 的每个元素数了一次。

这一节为什么重要

这一节交出去的是两件后面会反复使用的工具。

一是"不交并"这种读法。 "\(X\) 的不交并的元素个数等于各块元素个数之和"看着像句废话，却是一切分类计数的依据——用它的前提是分类确实构成不交并，也就是既不重叠、也不遗漏：

• 逆序与逆序数把全部逆序按"后一个数"（或按"前一个数的位置"）分类，靠的正是这条性质，才写下 \(\tau = \sum m_i\)
• 奇排列与偶排列的个数由 \(S_n = A_n \sqcup B_n\) 得到 \(\#A_n + \#B_n = n!\)。

分类一旦重叠或遗漏，"相加"就失去意义——这正是每次计数都要先验证"不重不漏"的原因。

二是"把等价的东西看成同一个东西"。 把一个集合 \(X\) 按等价关系 \(R\) 收缩成 \(X / R\)，正是构造新代数结构（如 \(\mathbb{Z}/n\mathbb{Z}\)）时的标准手段。

例题

例题 1

在 \(\mathbb{Z}\) 上定义关系 \(a \mathrel{R} b \iff a + b\) 为偶数。判断 \(R\) 是否为等价关系，并写出商集。

解 自反性：\(2a\) 为偶数，故 \(a \mathrel{R} a\)。对称性：\(a + b\) 与 \(b + a\) 相同，故对称。传递性：若 \(a + b\)、\(b + c\) 均为偶数，则 \(a + c = (a + b) + (b + c) - 2b\) 也是偶数，故 \(a \mathrel{R} c\)。因此 \(R\) 是等价关系。

等价类由奇偶性决定：偶数类 \([0] = \{2t \mid t \in \mathbb{Z}\}\)，奇数类 \([1] = \{2t + 1 \mid t \in \mathbb{Z}\}\)，故 \(X / R = \{[0], [1]\}\)。这正对应模 \(2\) 同余的两个商类。

例题 2

在 \(\mathbb{Z}\) 上取模 \(6\) 同余关系，写出 \([0]\)、\([7]\)、\([-2]\)，并指出 \([7]\) 与哪些等价类相同。

解 \([0] = \{6t \mid t \in \mathbb{Z}\}\)，\([7] = \{6t + 7 \mid t \in \mathbb{Z}\} = \{6t + 1 \mid t \in \mathbb{Z}\}\)，\([-2] = \{6t - 2 \mid t \in \mathbb{Z}\} = \{6t + 4 \mid t \in \mathbb{Z}\}\)。

因为 \(7 \equiv 1 \pmod 6\)，故 \([7] = [1]\)；又 \([7] = [13] = [-5] = \cdots\)，即同一个等价类的代表元不唯一。商集是这些等价类组成的集合：

\[ \mathbb{Z}/6\mathbb{Z} = \{[0],\ [1],\ [2],\ [3],\ [4],\ [5]\}, \]

其中 \([k] = \{6t + k \mid t \in \mathbb{Z}\}\)（例如 \([4] = \{\dots, -8, -2, 4, 10, 16, \dots\}\)，\([-2]\) 属于这一类而不单列）。

参见

• 连加与连乘：下一页，书写和式与积式的记号
• 集合与卡氏积：上一页，有序组
• 数域：等价类与商集是构造 \(\mathbb{Z}/n\mathbb{Z}\) 等代数结构的工具，数域的定义则建立在这些结构之上
• 首页：全站记号约定