最后更新: 2025-01-22 08:34 查看: 57 次反馈刷题

等价关系与划分

等价关系用于表示在现实的集合中＂物以类聚，人以群分＂的关系，因此等价关系和集合的划分有密切联系。

定义2．12 设 $A$ 是任意一个集合。 $A_i \subseteq A, A_i \neq \varnothing, i=1,2, \cdots, n_{\circ}$ 若 $\cup_{i=1}^n A_i=A$ ，且 $A_i \cap A_j=\varnothing(i$ ， $j=1,2, \cdots, n, i \neq j)$ ，则称 $\pi=\left\{A_1, A_2, \cdots, A_n\right\}$ 是 $A$ 的一个划分，其中每个 $A_i$ 称为划分 $\pi$ 的一个块。

例 2.21 设 $A=\{a, b, c\}$ ，考察下列几个由 $A$ 的子集所组成的集合是否是 $A$ 的划分：$P=\{\{a, b\}$ ， $\{c\}\}, S=\{\{a\},\{b\},\{c\}\}, T=\{\{a, b, c\}\}, U=\{\{a\},\{c\}\}, V=\{\{a, b\},\{b, c\}\}, W=\{\{a, b\},\{a, c\},\{c\}\}$ 。

解：因为 $\{a, b\} \cup\{c\}=\{a, b, c\},\{a, b\} \cap\{c\}=\varnothing$ ，所以 $P$ 是 $A$ 的划分；
因为 $\{a\} \cup\{b\} \cup\{c\}=\{a, b, c\}, \quad\{a\} \cap\{b\}=\{a\} \cap\{c\}=\{b\} \cap\{c\}=\varnothing$ ，所以 $S$ 是 $A$ 的划分；
$T$ 显然是 $A$ 的划分；
由于 $\{a\} \cup\{c\} \neq\{a, b, c\}$ ，所以 $U$ 不是 $A$ 的划分；
尽管 $\{a, b\} \cup\{b, c\}=\{a, b, c\}$ ，但 $\{a, b\} \cap\{b, c\}=\{b\} \neq \varnothing$ ，所以 $V$ 不是 $A$ 的划分；
类似可知 $W$ 也不是 $A$ 的划分。
定义 2.12 中的划分的块数也可以是无限的。
例 2.22 整数 $I$ 的划分 $\pi_1=\{E, O\}$ ，其中 $E$ 为偶数集，$O$ 为奇数集；$\pi_2=\{\{0\},\{-1,1\},\{-2,2\}$ ， $\{-3,3\}, \cdots\}$ 也是 $I$ 的一个划分，其划分的块数是无限的。

定义2．13 设 $R$ 是集合 $A$ 上的二元关系，若 $R$ 是自反的，对称的和传递的，则称 $R$ 是 $A$上的等价关系。若 $(a, b) \in R$ ，则称 $a$ 与 $b$ 等价。

如果给出了一个 $A$ 上的等价关系 $R$ ，怎样对 $A$ 进行划分呢？
例2．23 设 $A$ 是一个学生集合，定义 $A$ 上二元关系 $R:(a, b) \in R$ 当且仅当 $a$ 与 $b$ 同年龄，则容易验证 $R$ 是等价关系。 $A$ 按年龄进行分类，如设 $A_1$ 为 18 岁的学生集合，$A_1 \subseteq A$ ；设 $A_2$ 为 19 岁的学

生集合，$A_2 \subseteq A ; \cdots$ 这样的分类显然是 $A$ 的划分，$A_1, A_2, \cdots$ 则是 $A$ 的块。类似 $A$ 也可以按籍贯划分，也可以按专业划分等。

例 2.24 设整数集 $I$ 上的模 2 同余关系为 $R$ ，易验证 $R$ 是 $I$ 上的等价关系。把 I 分为两类：偶数集 $E$ 和奇数集 $O$ 。 $E=\{m \mid m \in I, m R 0\}, O=\{m \mid m \in I, m R 1\}$ 。显然，$E$ 和 $O$ 是 $I$ 的一个划分。

从上述例子可以体会到在等价关系与划分之间存在着某种联系，下面就介绍这种联系。
定义2．14 设 $R$ 是 $A$ 上的等价关系，对于每个 $a \in A$ ，与 $a$ 等价的元素全体所组成的集合称为由 $a$ 生成的关于 $R$ 的等价类，记为 $[a]_R$ ，即 $[a]_R=\{x \mid x \in A,(x, a) \in R\}, a$ 称为该等价类的代表元。

在不会引起误解的情况下，可把 $[a]_R$ 简记为 $[a]$ 。
定义2．15 设 $R$ 是 $A$ 上的一个等价关系，关于 $R$ 的等价类全体所组成的集合族称为 $A$ 上关于 $R$ 的商集，记为 $A / R$ ，即 $A / R=\{[a] \mid a \in A\}$ 。

例 $2.25(1)$ 对于例 2.24 中整数集 $I$ 上的模 2 同余关系 $R$ ，其等价类为 $[0]$ ，［1］。其中 $[0]=\{\cdots$ ， $-4,-2,0,2,4, \cdots\}=[2]=[4]=[-2]=[-4]=\cdots,[1]=\{\cdots,-3,-1,1,3, \cdots\}=[3]=[-1]=[-3]=\cdots$ ，因此 $A / R=\{[0],[1]\}$ 。
（2）整数集 $I$ 上的模 $n$ 同余关系 $R$ 也是 $I$ 上的等价关系。 $I$ 上关于 $R$ 的等价类为

$$
\begin{aligned}
& {[0]=\{\cdots,-2 n,-n, 0, n, 2 n, \cdots\}} \\
& {[1]=\{\cdots,-2 n+1,-n+1,1, n+1,2 n+1, \cdots\}} \\
& \cdots \\
& {[n-1]=\{\cdots,-n-1,-1, n-1,2 n-1,3 n-1, \cdots\}}
\end{aligned}
$$

这些类又称 $I$ 上模 $n$ 同余类。 $I$ 上关于 $R$ 的商集 $I / R=\{[0],[1], \cdots,[n-1]\}$ 。现在进一步研究集合 $A$ 上关于 $R$ 的等价类具有什么性质，有下面定理。

定理 2.13 设 $R$ 是 $A$ 上的等价关系，则
（1）对任一 $a \in A$ ，有 $a \in[a]$ ；
（2）对 $a, b \in A$ ，如果 $(a, b) \in R$ ，则 $[a]=[b]$ ；
（3）对 $a, b \in A$ ，如果 $(a, b) \notin R$ ，则 $[a] \cap[b]=\varnothing$ ；
（4）$\bigcup_{a \in A}[a]=A$ 。
证明：（1）对任一 $a \in A$ ，因为 $R$ 是 $A$ 上的等价关系，所以有 $(a, a) \in R$ ，则 $a \in[a]$ 。
（2）对 $a, b \in A$ ，如果 $(a, b) \in R$ ，分别证明 $[a] \subseteq[b],[b] \subseteq[a]$ 。
对任意的 $x \in[a]$ ，则有 $(x, a) \in R$ ；因为 $(a, b) \in R$ ，根据 $R$ 是传递的，则有 $(x, b) \in R$ ；即 $x \in[b]$ ，由此得 $[a] \subseteq[b]$ 。

对任意的 $x \in[b]$ ，则有 $(x, b) \in R$ ；因为 $(a, b) \in R, R$ 是对称的和传递的，则有 $(x, a) \in R$ ；即 $x \in[a]$ ，由此得 $[b] \subseteq[a]$ 。

所以 $[a]=[b]$ 。
（3）用反证法证明。假设 $[a] \cap[b] \neq \varnothing$ ，则存在 $x \in[a] \cap[b]$ ，因此 $x \in[a]$ 且 $x \in[b]$ ，即 $(x, a) \in R$ ， $(x, b) \in R$ ；因为 $R$ 是对称的和传递的，所以 $(a, b) \in R$ ，则导致矛盾。所以 $[a] \cap[b]=\varnothing$ 。
（4）对任意的 $x \in \bigcup_{a \in A}[A]$ ，存在 $b$ 使 $x \in[b]$ 。而 $[b] \subseteq A$ ，从而 $x \in A$ ，所以 $\bigcup_{a \in A}[a] \subseteq A$ 。
对任意的 $a \in A$ ，则 $a \in[a] \subseteq \bigcup_{a \in A}[a]$ ，所以 $A \subseteq \bigcup_{a \in A}[a]$ 。
因此 $\bigcup_{a \in A}[a]=A$ 。

由定理 2.13 （1）可知：$A$ 中每个元素所产生的等价类是非空的。由定理2．13（2），（3）可知：互相等价的元素属于同一个等价类，而不等价的元素其所属的等价类之间没有公共元素。由定理2．13（4）可知：$A$ 上等价关系 $R$ 的商集 $A / R=\{[a] \mid a \in A\}$ 就是 $A$ 的一个划分，$[a]$是该划分的一个块。

例 2.26 设 $A=\{1,2,3,4\}, R=\{(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2)\}$ 为等价关系。其等价类为 $[1]=\{1,3\},[2]=\{2,4\},[3]=\{1,3\},[4]=\{2,4\} ; A$ 的划分 $\pi=\{[1],[2]\}$ 。

给定的等价关系可以唯一地确定划分，反过来，给定一个划分，也可以唯一地确定一个等价关系。由此我们有下面定理。

定理 2.14 集合 $A$ 上的任一划分可以确定 $A$ 上的一个等价关系 $R$ 。
用构造方法进行证明。设集合 $A$ 上的任一划分 $\pi=\left\{A_1, A_2, \cdots, A_n\right\}$ ，构造 $A$ 上的二元关系 $R$ ： $R=\left(A_1 \times A_1\right) \cup\left(A_2 \times A_2\right) \cup \cdots \cup\left(A_n \times A_n\right)$ ，证明 $R$ 是等价关系。证明留作习题。

例2．27 设 $A=\{a, b, c\}$ 的一个划分 $\pi=\{\{a, b\},\{c\}\}$ ，由 $\pi$ 确定 $A$ 上的一个等价关系 $R$ 为

$$
R=(\{a, b\} \times\{a, b\}) \cup(\{c\} \times\{c\})=\{(a, a),(a, b),(b, a),(b, b),(c, c)\}
$$

定理2．15 设 $R_1$ 和 $R_2$ 是 $A$ 上的等价关系，$R_1=R_2$ 当且仅当 $A / R_1=A / R_2$ 。
证明留作习题。
定理 2.13 和定理 2.15 说明集合 $A$ 上的任一等价关系可以唯一地确定 $A$ 的一个划分。定理 2.14 和定理 2.15 说明集合 $A$ 的任一划分可以唯一地确定 $A$ 上的一个等价关系。总之，在集合 $A$ 上给出一个划分 $\pi=\pi_R$ 和给出一个等价关系 $R=R_\pi$ 是没有什么实质区别的。

对于集合 $A$ 上的等价关系 $R_1$ 和 $R_2$ 就有这样的问题：它们通过并和交运算而得到的关系是不是等价关系？若是，其对应的划分与 $R_1$ 和 $R_2$ 对应的划分又有何联系？

划分的积
定理 2.16 设 $R_1$ 和 $R_2$ 是 $A$ 上的等价关系，则 $R_1 \cap R_2$ 是 $A$ 上的等价关系。
根据定义 2.13 进行证明，即证明 $R_1 \cap R_2$ 是 $A$ 上的自反关系，对称关系和传递关系。证明留作习题。

定义2．16 设 $R_1$ 和 $R_2$ 是 $A$ 上的等价关系，由 $R_1$ 和 $R_2$ 确定的 $A$ 的划分分别为 $\pi_1$ 和 $\pi_2, A$ 上的等价关系 $R_1 \cap R_2$ 所确定的 $A$ 的划分称为 $\pi_1$ 和 $\pi_2$ 的积，记为 $\pi_1 \cdot \pi_2$ 。

定义2．17 设 $\pi$ 和 $\pi^{\prime}$ 是 $A$ 的划分，若 $\pi^{\prime}$ 的每一块包含在 $\pi$ 的一块中，称 $\pi^{\prime}$ 细分 $\pi$ ，或称 $\pi^{\prime}$加细 $\pi$ 。

例 $2.28 \pi^{\prime}=\{\{1\},\{2\},\{3,4\}\}, \pi=\{\{1,2\},\{3,4\}\}$ 。因为 $\{1\} \subseteq\{1,2\} \in \pi,\{2\} \subseteq\{1,2\} \in \pi$ ， $\{3,4\} \subseteq\{3,4\} \in \pi$ ，所以 $\pi^{\prime}$ 细分 $\pi$ 。

如果 $\pi^{\prime}$ 细分 $\pi$ ，定理 2.17 给出 $\pi$ 和 $\pi^{\prime}$ 对应的二元关系 $R$ 和 $R^{\prime}$ 之间的联系。
定理 2.17 设 $\pi, \pi^{\prime}$ 是 $A$ 的划分，它们确定 $A$ 上的等价关系分别为 $R, R^{\prime}$ ，则 $\pi^{\prime}$ 细分 $\pi$ 当且仅当 $R^{\prime} \subseteq R$ 。

先证明：如果 $\pi^{\prime}$ 细分 $\pi$ ，则 $R^{\prime} \subseteq R$ 。对任意的 $(a, b) \in R^{\prime}$ ，存在 $S^{\prime} \in \pi^{\prime}$ ，使得 $a, b \in S^{\prime}$ 。因为 $\pi^{\prime}$细分 $\pi$ ，所以存在 $S \in \pi$ ，使得 $S^{\prime} \subseteq S$ 。因此 $a, b \in S$ ，从而 $(a, b) \in R$ 。

再证明：如果 $R^{\prime} \subseteq R$ ，则 $\pi^{\prime}$ 细分 $\pi$ 。对任意的 $S^{\prime} \in \pi^{\prime}, S^{\prime}$ 非空，所以存在 $a \in S^{\prime}$ ，使得 $[a]_{R^{\prime}}=S^{\prime}$ 。对任意的 $x \in S^{\prime}$ ，必有 $(x, a) \in R^{\prime}$ 。因为 $R^{\prime} \subseteq R$ ，所以 $(x, a) \in R$ 。即 $x \in[a]_R \in \pi$ 。所以 $S^{\prime} \subseteq[a]_R$ ，即 $\pi^{\prime}$ 细分 $\pi$ 。

下面讨论 $\pi_1$ 与 $\pi_2$ 的积 $\pi_1 \cdot \pi_2$ 与 $\pi_1$ 和 $\pi_2$ 的联系。

定理 2.18 设 $\pi_1, \pi_2$ 是 $A$ 的划分，则
（1）$\pi_1 \cdot \pi_2$ 细分 $\pi_1$ 与 $\pi_2$ 。
（2）设 $\pi^{\prime}$ 是 $A$ 的划分，若 $\pi^{\prime}$ 细分 $\pi_1$ 与 $\pi_2$ ，则 $\pi^{\prime}$ 细分 $\pi_1 \cdot \pi_2$ 。
证明：（1）设 $\pi_1$ 和 $\pi_2$ 分别对应的 $A$ 上关系是 $R_1$ 和 $R_2$ ，则 $\pi_1 \cdot \pi_2$ 对应的关系为 $R_1 \cap R_2$ 。而 $R_1 \cap R_2 \subseteq R_1, R_1 \cap R_2 \subseteq R_2$ ，由定理 2．17，$\pi_1 \cdot \pi_2$ 细分 $\pi_1$ 与 $\pi_2$ 。
（2）设 $\pi^{\prime}$ 对应 A 上的关系是 $R^{\prime}, \pi_1$ 和 $\pi_2$ 分别对应的 $A$ 上的关系是 $R_1$ 和 $R_2$ ，则 $\pi_1 \cdot \pi_2$ 对应的关系为 $R_1 \cap R_2$ 。因为 $\pi^{\prime}$ 细分 $\pi_1$ 与 $\pi_2$ ，所以由定理 $2.17, R^{\prime} \subseteq R_1, R^{\prime} \subseteq R_2$ 。因此 $R^{\prime} \subseteq R_1 \cap R_2$ 。

定理 2.18 告诉我们，$\pi_1 \cdot \pi_2$ 细分 $\pi_1$ 与 $\pi_2$ ，并且是同时细分 $\pi_1$ 与 $\pi_2$ 的最小划分（即划分块数最少）。显然，对于 $a, b \in A, a, b$ 在划分 $\pi_1 \cdot \pi_2$ 的同一块中当且仅当 $a, b$ 在 $\pi_1$ 的同一块中，以及 $a$ ， $b$ 在 $\pi_2$ 的同一块中。

例2．29 设学生集合 $A=\{a, b, c, d, e, f, g, h, i, j, k\}$ ，按同年龄分为一组，得到 $A$ 的划分 $\pi_1=\{\{a, b, c, d\},\{e, f, g\},\{h, i\},\{j, k\}\}$ ，按同班级分为一组，得到 $A$ 的划分 $\pi_2=\{\{a, b, c, h\},\{d, i\}$ ， $\{e, f, j, k\},\{g\}\}$ 。那么 $\pi_1 \cdot \pi_2=\{\{a, b, c\},\{d\},\{e, f\},\{g\},\{h\},\{i\},\{j, k\}\}$ 。在 $\pi_1 \cdot \pi_2$ 同一组中的任两个学生既在同一年龄组中又在同一班级中。而不在 $\pi_1 \cdot \pi_2$ 同一组中的两个学生，还有可能在同一年龄组中或在同一班级中。

划分的和
设集合 $A$ 上的等价关系为 $R_1$ 和 $R_2$ ，容易证明 $R_1 \cup R_2$ 是 $A$ 上的自反和对称关系，但不是 $A$ 上的等价关系；然而 $R_1 \cup R_2$ 的传递闭包是 $A$ 上的等价关系。

定理 2.19 设 $R_1$ 和 $R_2$ 是集合 $A$ 上的等价关系，则 $\left(R_1 \cup R_2\right)^{+}$是 $A$ 上的等价关系。
证明留作习题。
定义 2.18 设 $R_1$ 和 $R_2$ 是集合 $A$ 上的等价关系，$R_1$ 和 $R_2$ 确定的 $A$ 的划分分别为 $\pi_1$ 和 $\pi_2$ 。 $A$上的等价关系 $\left(R_1 \cup R_2\right)^{+}$所确定 $A$ 的划分称为 $\pi_1$ 与 $\pi_2$ 划分的和，记为 $\pi_1+\pi_2$ 。

定理 2.20 设 $\pi_1, \pi_2$ 是 $A$ 的划分，则
（1）$\pi_1$ 与 $\pi_2$ 细分 $\left(R_1 \cup R_2\right)^{+}$。
（2）设 $\pi^{\prime}$ 是 $A$ 的划分，若 $\pi_1$ 与 $\pi_2$ 细分 $\pi^{\prime}$ ，则 $\pi_1+\pi_2$ 细分 $\pi^{\prime}$ 。
证明：（1）设 $\pi_1$ 和 $\pi_2$ 分别对应的 $A$ 上的等价关系是 $R_1$ 和 $R_2$ ，则 $\pi_1+\pi_2$ 对应的关系为 $\left(R_1 \cup R_2\right)^{+}$。因为 $R_1 \subseteq\left(R_1 \cup R_2\right)^{+}, R_2 \subseteq\left(R_1 \cup R_2\right)^{+}$，由定理 2.17 即得。
（2）设 $\pi^{\prime}$ 对应 $A$ 上的等价关系是 $R^{\prime}, \pi_1$ 和 $\pi_2$ 分别对应的 $A$ 上的等价关系是 $R_1$ 和 $R_2$ ，则 $\pi_1+\pi_2$ 对应的关系为 $\left(R_1 \cup R_2\right)^{+}$。因为 $\pi_1$ 与 $\pi_2$ 细分 $\pi^{\prime}$ ，由定理 2．17，$R_1 \subseteq R^{\prime}, R_2 \subseteq R^{\prime}$ 。因此 $R_1 \cup R_2 \subseteq R^{\prime}$ 。又因为 $R^{\prime}$ 传递，所以由闭包定义的第 3 个条件知 $\left(R_1 \cup R_2\right)^{+} \subseteq R^{\prime}$ ，即 $\left(R_1 \cup R_2\right)^{+}$是包含 $R_1 \cup R_2$ 的最小的等价关系。由定理 $2.17, \pi_1+\pi_2$ 细分 $\pi^{\prime}$ 。

定理 2.20 说明 $\pi_1+\pi_2$ 被 $\pi_1$ 与 $\pi_2$ 细分，并且是同时被 $\pi_1$ 与 $\pi_2$ 细分的最大划分（即划分块数最多）。

例 2.30 在例 2.28 中，学生集合的划分为 $\pi_1, \pi_2$ ，那么 $\pi_1+\pi_2=\{\{a, b, c, d, h, i\},\{e, f, g, j$ ， $k\}\}$ 。在 $\pi_1+\pi_2$ 同一组中的任两个学生弄不清他们分别在 $\pi_1, \pi_2$ 的哪一组中，但是不在 $\pi_1+\pi_2$ 同一组中的任两个学生必定不在同一年龄组中，也不在同一班级中。

划分 $\pi_1+\pi_2$ 还有下述特性。
定理 2.21 设集合 $A$ ，对于 $a, b \in A, a, b$ 在 $\pi_1+\pi_2$ 的同一块中，当且仅当在 $A$ 中存在元素序列 $a, c_l, \cdots, c_k, b$ ，使得序列中每相邻两个元素在 $\pi_1$ 的同一块中或在 $\pi_2$ 的同一块中。

证明：由 $\pi_1+\pi_2$ 的定义可知，$a, b$ 在 $\pi_1+\pi_2$ 的同一块中，对应于 $(a, b) \in\left(R_1 \cup R_2\right)^{+}$，由定理 2.9知，存在正整数 $k+1$ ，使 $(a, b) \in\left(R_1 \cup R_2\right)^{k+1}$ ，即存在 $k$ 个元素 $c_1, \cdots, c_k \in A$ ，使 $(a$ ， $\left.c_1\right) \in\left(R_1 \cup R_2\right), \cdots,\left(c_k, b\right) \in\left(R_1 \cup R_2\right)$ 。因为 $R_1, R_2$ 是 $A$ 上的等价关系，所以 $a, c_1$ 在 $\pi_1$ 或 $\pi_2$ 的同一块中，$\cdots, c_k b$ 在 $\pi_1$ 或 $\pi_2$ 的同一块中，$a$ 和 $b$ 是链接的。反之亦然。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：关系的闭包

下一篇：次序关系

本文对您是否有用？有用 (0) 无用 (0)