4.3 等价关系与划分

第 4.2 节分别介绍了四种关系性质。现在我们把其中三种组合起来，刻画一种熟悉的想法：两个对象虽然不同，但按照某个指定标准可以视为等价。

例如， $7$ 与 $19$ 是不同整数，但除以 $3$ 都余 $1$ ；两个文件的字节内容不同，却可能具有相同文件类型。“等价”只有在判断标准明确以后才有意义。

等价关系的三项要求

集合 $A$ 上的关系 $\sim$ 称为等价关系，如果它同时满足：

1. 自反：对每个 $a\in A$ ，都有 $a\sim a$ ；

2. 对称： $a\sim b$ 会推出 $b\sim a$ ；

3. 传递： $a\sim b$ 且 $b\sim c$ 会推出 $a\sim c$ 。

符号 $\sim$ 常用于表示等价关系，但真正使它成为等价关系的是这三条性质，而不是符号本身。

考虑整数集 $\mathbb Z$ 上的关系“具有相同奇偶性”。

每个整数都与自身具有相同奇偶性，所以它自反；

如果 $a$ 与 $b$ 奇偶性相同，那么 $b$ 与 $a$ 也相同，所以它对称；

如果 $a$ 与 $b$ 奇偶性相同， $b$ 与 $c$ 也相同，那么 $a$ 与 $c$ 相同，所以它传递。

因此，“具有相同奇偶性”是等价关系。

相比之下，整数上的“距离不超过 $2$ ”自反且对称，却不传递。因为

1\sim3,\qquad 3\sim5,

但 $1\not\sim5$ 。缺少传递连接，使它不能成为等价关系。

等价类

设 $\sim$ 是 $A$ 上的等价关系。对元素 $a\in A$ ， $a$ 的等价类定义为

[a]=\{x\in A\mid x\sim a\}.

它恰好包含所有被认为与 $a$ 等价的元素。

在集合

A=\{1,2,3,4,5,6\}

上的同奇偶关系中，

[1]=\{1,3,5\}, \qquad [2]=\{2,4,6\}.

同时还有

[1]=[3]=[5], \qquad [2]=[4]=[6].

符号 $[a]$ 表示一个集合，并不是把 $a$ 变换后得到的单个数值。

下面三个事实解释了为什么等价类会形成整齐分组。

每个元素都属于自己的等价类

由自反性， $a\sim a$ ，所以

a\in[a].

因此不会有元素无处归类。

等价的代表元拥有同一个等价类

假设 $a\sim b$ 。若 $x\in[a]$ ，则 $x\sim a$ 。把 $x\sim a$ 与 $a\sim b$ 用传递性连接起来，得到 $x\sim b$ ，即 $x\in[b]$ 。因此 $[a]\subseteq[b]$ 。

由对称性又有 $b\sim a$ ，同样的推理给出 $[b]\subseteq[a]$ 。所以

a\sim b\Rightarrow[a]=[b].

两个等价类要么相等，要么不相交

如果 $[a]$ 与 $[b]$ 共享元素 $x$ ，那么 $x\sim a$ 且 $x\sim b$ 。由对称性得到 $a\sim x$ ，再由传递性得到 $a\sim b$ 。根据上一条事实，

[a]=[b].

所以两个等价类绝不会只重叠一部分：它们要么完全相同，要么交集为空。

划分从另一个方向描述同一分组

集合 $A$ 的一个划分，是一些子集组成的集合，其中每个子集称为一个块，并满足：

1. 每个块都不是空集；

2. 不同块互不相交；

3. 所有块的并集等于 $A$ 。

例如，

\mathcal P=\big\{\{1,3,5\},\{2,4,6\}\big\}

是 $\{1,2,3,4,5,6\}$ 的一个划分。

等价关系会产生一个划分：收集所有不同的等价类即可。

反过来，一个划分也会产生等价关系。给定划分 $\mathcal P$ ，定义

a\sim b \quad\Longleftrightarrow\quad a\text{ 与 }b\text{ 位于 }\mathcal P\text{ 的同一个块中}.

这个关系自反，因为每个元素与自身共享一个块；它对称，因为“同一个块”可以交换顺序；它传递，因为若 $a$ 与 $b$ 同块、 $b$ 与 $c$ 同块，块之间互不相交的规则迫使三者都在同一个块中。

因此，等价关系与划分是同一结构的两种视角：

\boxed{\text{等价关系}} \quad\longleftrightarrow\quad \boxed{\text{由等价类组成的划分}}.

正在加载交互实验...

把物件拖入分类区域，也可以使用键盘移动按钮，同时观察所诱导的关系矩阵。挑战会出现遗漏、重叠和有效分类，使等价关系的三条性质与划分的三条规则之间的联系变得可操作、可观察。

正在加载概念检查...

正在加载本节练习...

模 $m$ 同余

奇偶性把整数分成两个类。模同余把这个想法推广到任意正整数模数。

先回忆整除：对整数 $d,n$ 且 $d\ne0$ ，

d\mid n

表示存在整数 $k$ 使 $n=dk$ 。

给定正整数 $m$ ，如果 $m$ 整除两个整数 $a,b$ 的差，就称 $a$ 与 $b$ 模 $m$ 同余：

a\equiv b\pmod m \quad\Longleftrightarrow\quad m\mid(a-b).

例如，

17\equiv5\pmod{12},

因为

17-5=12=12\cdot1.

另外，

-1\equiv4\pmod5,

因为 $-1-4=-5=5(-1)$ 。负整数不会造成问题，整除定义中的商见证可以是负数。

为什么模同余是等价关系

我们直接按照定义验证三条性质。

自反。 对每个整数 $a$ ，

a-a=0=m\cdot0,

所以 $m\mid(a-a)$ ，即 $a\equiv a\pmod m$ 。

对称。 如果 $a\equiv b\pmod m$ ，则存在整数 $k$ 使 $a-b=mk$ 。于是

b-a=-mk=m(-k),

所以 $b\equiv a\pmod m$ 。

传递。 如果 $a\equiv b\pmod m$ 且 $b\equiv c\pmod m$ ，则存在整数 $k,\ell$ 使

a-b=mk,\qquad b-c=m\ell.

两式相加得到

a-c=(a-b)+(b-c)=m(k+\ell).

因为 $k+\ell$ 是整数，所以 $a\equiv c\pmod m$ 。

剩余类与商集

每个整数除以 $m$ 后，都恰好有一个余数属于

0,1,\ldots,m-1.

这 $m$ 个余数标记了 $m$ 个不同等价类：

[r]_m=\{n\in\mathbb Z\mid n\equiv r\pmod m\}.

对于模 $4$ ，

\begin{aligned} [0]_4&=\{\ldots,-8,-4,0,4,8,\ldots\},\\ [1]_4&=\{\ldots,-7,-3,1,5,9,\ldots\},\\ [2]_4&=\{\ldots,-6,-2,2,6,10,\ldots\},\\ [3]_4&=\{\ldots,-5,-1,3,7,11,\ldots\}. \end{aligned}

所有不同等价类组成的集合称为商集：

\mathbb Z/m\mathbb Z =\{[0]_m,[1]_m,\ldots,[m-1]_m\}.

这里的斜线不是普通除法，而表示“把模 $m$ 同余的整数压缩到同一个类中”。

正在加载交互实验...

改变模数，把正整数或负整数发射到时钟周围。数值会沿轨道进入自己的剩余类站点；等价测试还会显示两个数的差是否恰好走完整数圈。

正在加载概念检查...

正在加载本节练习...

注意

同一个等价类可以有许多代表元。在模

4

中，

[1]_4

、

[5]_4

和

[-3]_4

表示同一个集合，因为

1\equiv5\equiv-3\pmod4

。

本节衔接

等价关系把应当视为同类的元素分组。下一节会研究另一组性质：自反、反对称、传递。这个组合不会形成簇，而会描述先后顺序、包含关系和层级结构。

4.3 等价关系与划分

第 4.2 节分别介绍了四种关系性质。现在我们把其中三种组合起来，刻画一种熟悉的想法：两个对象虽然不同，但按照某个指定标准可以视为等价。

等价关系的三项要求

集合 $A$ 上的关系 $\sim$ 称为等价关系，如果它同时满足：

1. 自反：对每个 $a\in A$ ，都有 $a\sim a$ ；

2. 对称： $a\sim b$ 会推出 $b\sim a$ ；

3. 传递： $a\sim b$ 且 $b\sim c$ 会推出 $a\sim c$ 。

符号 $\sim$ 常用于表示等价关系，但真正使它成为等价关系的是这三条性质，而不是符号本身。

考虑整数集 $\mathbb Z$ 上的关系“具有相同奇偶性”。

每个整数都与自身具有相同奇偶性，所以它自反；

如果 $a$ 与 $b$ 奇偶性相同，那么 $b$ 与 $a$ 也相同，所以它对称；

如果 $a$ 与 $b$ 奇偶性相同， $b$ 与 $c$ 也相同，那么 $a$ 与 $c$ 相同，所以它传递。

因此，“具有相同奇偶性”是等价关系。

相比之下，整数上的“距离不超过 $2$ ”自反且对称，却不传递。因为

1\sim3,\qquad 3\sim5,

但 $1\not\sim5$ 。缺少传递连接，使它不能成为等价关系。

等价类

设 $\sim$ 是 $A$ 上的等价关系。对元素 $a\in A$ ， $a$ 的等价类定义为

[a]=\{x\in A\mid x\sim a\}.

它恰好包含所有被认为与 $a$ 等价的元素。

在集合

A=\{1,2,3,4,5,6\}

上的同奇偶关系中，

[1]=\{1,3,5\}, \qquad [2]=\{2,4,6\}.

同时还有

[1]=[3]=[5], \qquad [2]=[4]=[6].

符号 $[a]$ 表示一个集合，并不是把 $a$ 变换后得到的单个数值。

下面三个事实解释了为什么等价类会形成整齐分组。

每个元素都属于自己的等价类

由自反性， $a\sim a$ ，所以

a\in[a].

因此不会有元素无处归类。

等价的代表元拥有同一个等价类

假设 $a\sim b$ 。若 $x\in[a]$ ，则 $x\sim a$ 。把 $x\sim a$ 与 $a\sim b$ 用传递性连接起来，得到 $x\sim b$ ，即 $x\in[b]$ 。因此 $[a]\subseteq[b]$ 。

由对称性又有 $b\sim a$ ，同样的推理给出 $[b]\subseteq[a]$ 。所以

a\sim b\Rightarrow[a]=[b].

两个等价类要么相等，要么不相交

如果 $[a]$ 与 $[b]$ 共享元素 $x$ ，那么 $x\sim a$ 且 $x\sim b$ 。由对称性得到 $a\sim x$ ，再由传递性得到 $a\sim b$ 。根据上一条事实，

[a]=[b].

所以两个等价类绝不会只重叠一部分：它们要么完全相同，要么交集为空。

划分从另一个方向描述同一分组

集合 $A$ 的一个划分，是一些子集组成的集合，其中每个子集称为一个块，并满足：

1. 每个块都不是空集；

2. 不同块互不相交；

3. 所有块的并集等于 $A$ 。

例如，

\mathcal P=\big\{\{1,3,5\},\{2,4,6\}\big\}

是 $\{1,2,3,4,5,6\}$ 的一个划分。

等价关系会产生一个划分：收集所有不同的等价类即可。

反过来，一个划分也会产生等价关系。给定划分 $\mathcal P$ ，定义

a\sim b \quad\Longleftrightarrow\quad a\text{ 与 }b\text{ 位于 }\mathcal P\text{ 的同一个块中}.

因此，等价关系与划分是同一结构的两种视角：

\boxed{\text{等价关系}} \quad\longleftrightarrow\quad \boxed{\text{由等价类组成的划分}}.

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

模 $m$ 同余

奇偶性把整数分成两个类。模同余把这个想法推广到任意正整数模数。

先回忆整除：对整数 $d,n$ 且 $d\ne0$ ，

d\mid n

表示存在整数 $k$ 使 $n=dk$ 。

给定正整数 $m$ ，如果 $m$ 整除两个整数 $a,b$ 的差，就称 $a$ 与 $b$ 模 $m$ 同余：

a\equiv b\pmod m \quad\Longleftrightarrow\quad m\mid(a-b).

例如，

17\equiv5\pmod{12},

因为

17-5=12=12\cdot1.

另外，

-1\equiv4\pmod5,

因为 $-1-4=-5=5(-1)$ 。负整数不会造成问题，整除定义中的商见证可以是负数。

为什么模同余是等价关系

我们直接按照定义验证三条性质。

自反。 对每个整数 $a$ ，

a-a=0=m\cdot0,

所以 $m\mid(a-a)$ ，即 $a\equiv a\pmod m$ 。

对称。 如果 $a\equiv b\pmod m$ ，则存在整数 $k$ 使 $a-b=mk$ 。于是

b-a=-mk=m(-k),

所以 $b\equiv a\pmod m$ 。

传递。 如果 $a\equiv b\pmod m$ 且 $b\equiv c\pmod m$ ，则存在整数 $k,\ell$ 使

a-b=mk,\qquad b-c=m\ell.

两式相加得到

a-c=(a-b)+(b-c)=m(k+\ell).

因为 $k+\ell$ 是整数，所以 $a\equiv c\pmod m$ 。

剩余类与商集

每个整数除以 $m$ 后，都恰好有一个余数属于

0,1,\ldots,m-1.

这 $m$ 个余数标记了 $m$ 个不同等价类：

[r]_m=\{n\in\mathbb Z\mid n\equiv r\pmod m\}.

对于模 $4$ ，

\begin{aligned} [0]_4&=\{\ldots,-8,-4,0,4,8,\ldots\},\\ [1]_4&=\{\ldots,-7,-3,1,5,9,\ldots\},\\ [2]_4&=\{\ldots,-6,-2,2,6,10,\ldots\},\\ [3]_4&=\{\ldots,-5,-1,3,7,11,\ldots\}. \end{aligned}

所有不同等价类组成的集合称为商集：

\mathbb Z/m\mathbb Z =\{[0]_m,[1]_m,\ldots,[m-1]_m\}.

这里的斜线不是普通除法，而表示“把模 $m$ 同余的整数压缩到同一个类中”。

正在加载交互实验...

改变模数，把正整数或负整数发射到时钟周围。数值会沿轨道进入自己的剩余类站点；等价测试还会显示两个数的差是否恰好走完整数圈。

正在加载概念检查...

正在加载本节练习...

注意

同一个等价类可以有许多代表元。在模

4

中，

[1]_4

、

[5]_4

和

[-3]_4

表示同一个集合，因为

1\equiv5\equiv-3\pmod4

。

4.3 等价关系与划分

4.3 等价关系与划分

等价关系的三项要求

等价类

每个元素都属于自己的等价类

等价的代表元拥有同一个等价类

两个等价类要么相等，要么不相交

划分从另一个方向描述同一分组

模 mmm 同余

为什么模同余是等价关系

剩余类与商集

本节衔接

4.3 等价关系与划分

4.3 等价关系与划分

等价关系的三项要求

等价类

每个元素都属于自己的等价类

等价的代表元拥有同一个等价类

两个等价类要么相等，要么不相交

划分从另一个方向描述同一分组

模 mmm 同余

为什么模同余是等价关系

剩余类与商集

本节衔接

模 $m$ 同余

模 $m$ 同余