数学证明/关系

介绍

直观地说，关系根据某些规则和属性将成对的对象关联起来。也就是说，关系表明了两个对象之间某种关系或联系。以婚姻为例。在婚姻登记处，有一个记录，其中丈夫的姓名与其对应妻子的姓名相关联，以跟踪婚姻状况。记录中的条目可以解释为 有序对 $(a,b)$ ，其中 $a$ 是丈夫，而 $b$ 是妻子。

用数学表达，设 $M$ 和 $W$ 分别是所有男人和女人的集合。那么，笛卡尔积 $M\times W=\{(a,b):a\in M{\text{ and }}b\in W\}$ 由所有人员对组成（第一和第二个坐标分别是男性和女性）。之后，我们知道婚姻登记处的记录， $R$ ，是 $M\times W$ 的一个子集。如果一个男人和一个女人在 $R$ 中形成一个有序对，比如 $(m,w)$ ，那么这意味着他们结婚了。那么，自然可以说 $m$ 与 $w$ 相关。换句话说，如果我们发现 $(m,w)\in R$ ，那么这意味着他们 通过此关系 $R$ 相关。同样，知道 $R$ 究竟是什么（我们有婚姻登记处的记录）与知道所有丈夫和妻子的关系是相同的。

因此，自然地将集合 $R$ 定义为关系。让我们正式定义下面的关系。

术语

定义。 （关系）从集合 $A$ 到集合 $B$ 的关系 $R$ 是 $A\times B$ 的一个子集，即 $R\subseteq A\times B$ 。特别是，当 $A=B$ 时，我们说 $R$ 是 $A$ 上的关系，我们有 $R\subseteq A\times A$ 。如果 $(a,b)\in R$ ，那么我们说 $a$ 与 $b$ 由 $R$ 相关，并写成 $aRb$ 。另一方面，如果 $(a,b)\notin R$ ，那么我们说 $a$ 与 $b$ 由 $R$ 不相关，并写成 $a\not Rb$ 。

示例。 令 $A=\{a,b,c\}$ ， $B=\{1,2,3,4\}$ ，并且 $R=\{(a,1),(b,1),(b,2),(c,3)\}$ 。由于集合 $R$ 是 $A\times B$ 的子集， $R$ 定义了从集合 $A$ 到集合 $B$ 的关系。此外，在这个关系中， $a$ 与 1 相关， $b$ 与 1 和 2 相关， $c$ 与 3 相关。因此，我们有 $aR1,bR1,bR2$ 和 $cR3$ 。但是，我们有，比如 $a\not R2$ 或 $d\not R4$ ，因为 $(a,2),(d,4)\notin R$ 。

练习。

(a) 建议一个集合 $S$ ，它不是从集合 $A$ 到集合 $B$ 的关系。

(b) 建议一个集合 $T$ ，它是从集合 $A$ 到集合 $R$ 的关系。

解答

(a) $S=\{(a,5)\}$ ( $(a,5)\notin A\times B$ ，所以 $S$ 不是 $A\times B$ 的子集）。

(b) $T=\left\{{\big (}a,(a,1){\big )}\right\}$ .

练习。 令 $A$ 和 $B$ 是两个非空集合。 $\varnothing$ 和 $A\times B$ 是从 $A$ 到 $B$ 的关系吗？描述这两个集合所代表的关系。

解答

$\varnothing$ 和 $A\times B$ 都是从 $A$ 到 $B$ 的关系，因为它们都是 $A\times B$ 的子集。

对于 $\varnothing$ ，这意味着没有任何关系，即 $A$ 中的元素与 $B$ 中的元素之间没有关系。

对于 $A\times B$ ，这意味着所有元素都有关系，即 $A$ 中的每个元素都与 $B$ 中的每个元素都有关系。

示例： 设 $H$ 是所有人类的集合。那么， $R=\{(a,b):a{\text{ is the son of }}b\}$ 。那么， $R$ 是 $H\times H$ 的子集，并定义了父子关系。

示例： “小于”的概念定义了 $\mathbb {R}$ 上的关系。更准确地说，与该概念对应的关系是 $R=\{(a,b):a<b\}\subseteq \mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}$ 。例如， $1R2$ 但 $2\not R1$ 。

示例。 整数的同余关系定义了在 $\mathbb {Z}$ 上的关系。更准确地说，相应的关系是 $R=\{(a,b):a\equiv b{\pmod {n}}\}\subseteq \mathbb {Z} \times \mathbb {Z}$ （ $n\in \mathbb {N}$ 且 $n\geq 2$ ）。例如，当 $n=3$ 时，则 $2R5$ ，但 $1\not R3$ 。

练习。 考虑在 $\mathbb {R}$ 上的关系，对应于“等于”的概念： $R=\{(x,y):x=y\}\subseteq \mathbb {R} ^{2}$ 。

(a) 在笛卡尔坐标系中绘制 $R$ 的图像。

(b) 还考虑在 $\mathbb {R}$ 上的关系 $S,T$ ，分别对应于“小于”和“大于”的概念。在 (a) 的图中也绘制 $S$ 和 $T$ 的图像。

解答

(a) 和 (b)

        y
        |    y=x     
########|#####/%%%
########|####/%%%% 
########|###/%%%%%
########|##/%%%%%%
########|#/%%%%%%%
########|/%%%%%%%%
--------*--------- x
#######/|%%%%%%%%% 
######/%|%%%%%%%%%
#####/%%|%%%%%%%%%
####/%%%|%%%%%%%%%
###/%%%%|%%%%%%%%%

*----*
|####|
|####| : y>x (relation T)
*----*

*----*
|%%%%|
|%%%%| : y<x (relation S)
*----*

备注。

集合 $R,S,T$ 给出了 $\mathbb {R}$ 的划分。正如我们将看到的，关系的概念和划分的概念之间存在密切的联系。

示例。 令 $A=\{1,2\}$ 。在 ${\mathcal {P}}(A)$ 上定义一个关系 $R=\{(S,T)\in {\mathcal {P}}(A)\times {\mathcal {P}}(A):S\subseteq T\}$ 。用列举法表示 $R$ 。

解。首先，我们有 ${\mathcal {P}}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$ 。因此， $R=\{(\varnothing ,\varnothing ),(\varnothing ,\{1\}),(\varnothing ,\{2\}),(\varnothing ,\{1,2\}),(\{1\},\{1\}),(\{1\},\{1,2\}),(\{2\},\{2\}),(\{2\},\{1,2\}),(\{1,2\},\{1,2\})\}.$

练习。 令 $A=\{1,2\}$ 和 $B=\{3,4\}$ 。考虑 $A\times B$ 上的关系 $R$ ，它由以下定义： $(a,b)R(c,d){\text{ if }}a+d=b+c.$ 用列举法表示 $R$ 。

解答

首先， $A\times B=\{(1,3),(1,4),(2,3),(2,4)\}$ 。因此， $R=\{{\big (}(1,3),(1,3){\big )}{\big (}(1,3),(2,4){\big )},{\big (}(1,4),(1,4){\big )},{\big (}(2,3),(2,3){\big )},{\big (}(2,4),(1,3){\big )},{\big (}(2,4),(2,4){\big )}\}.$

定义。 （定义域和值域）设 $R$ 是从集合 $A$ 到集合 $B$ 的关系。 $R$ 的 定义域，记为 $\operatorname {dom} R$ ，是 $A$ 的子集，定义为 $\operatorname {dom} R=\{a\in A:(a,b)\in R{\text{ for some }}b\in B\}.$ $R$ 的值域，记为 $\operatorname {ran} R$ ，是 $B$ 的子集，定义为 $\operatorname {ran} R=\{b\in B:(a,b)\in R{\text{ for some }}a\in A\}.$

备注。

你可能已经了解了函数的 定义域 和值域。对于关系和函数使用相同的术语并非巧合。这是因为函数实际上是一种关系。也就是说，函数实际上只是关系的一种特殊情况。

示例。 令 $A=\{a,b,c\}$ ， $B=\{1,2,3,4\}$ ，以及 $R=\{(a,1),(b,1),(b,2),(c,3)\}$ 。那么， $\operatorname {dom} R=\{a,b,c\}=A$ 并且 $\operatorname {ran} R=\{1,2,3\}$ .

示例。 考虑关系 $R$ 在 $\mathbb {Z}$ 上： $R=\{(a,b):a{\text{ and }}b{\text{ are both even}}\}$ 。那么， $\operatorname {dom} R$ 是所有偶数的集合，而 $\operatorname {ran} R$ 也是所有偶数的集合。

练习。 考虑关系 $R$ 在 $\mathbb {Z}$ 上： $R=\{(a,b):a{\text{ and }}b{\text{ are of different parity}}\}$ 。求 $\operatorname {dom} R$ 和 $\operatorname {ran} R$ .

解答

$\operatorname {dom} R=\mathbb {Z}$ 并且 $\operatorname {ran} R=\mathbb {Z}$ .

定义.（逆关系）设 $R$ 是从集合 $A$ 到集合 $B$ 的关系。 逆关系 $R^{-1}$ 是从 $B$ 到 $A$ 的关系是 $R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$

备注。

同样地，您可能已经学习过类似的概念（以及类似的符号）——函数的逆函数。实际上，逆函数可以定义为函数的逆关系，前提是逆关系也是一个函数。
我们可以看到，逆关系是通过“反转”原关系中每个有序对的元素顺序得到的。
当 $R$ 为空时，逆关系 $R^{-1}$ 也是空的，因为空集中没有有序对。

例子. 设 $A=\{a,b,c\}$ ， $B=\{1,2,3,4\}$ ，且 $R=\{(a,1),(b,1),(b,2),(c,3)\}$ 。那么，逆关系 $R^{-1}$ 是 $\{(1,a),(1,b),(2,b),(3,c)\}$ .

练习。 构造一个集合的例子 $A,B$ 和一个非空的从集合 $A$ 到集合 $B$ 的关系 $R$ ，使得 $R=R^{-1}$ .

解答

取 $A=B=\{1\}$ ，并且 $R=\{(1,1)\}$ 。然后， $R^{-1}=\{(1,1)\}=R$ .

自反、对称和传递关系

在介绍与关系相关的术语后，我们将研究定义在集合上的关系的三个性质。

定义。 （自反、对称和传递）设 $A$ 是一个集合，并且 $R$ 是定义在 $A$ 上的关系。那么，

$R$ 是 自反的，如果对于每个 $x\in A$ ，都有 $xRx$ 。
$R$ 是 对称的，如果对于每个 $x,y\in A$ ，都有 $xRy\implies yRx$ 。
$R$ 是传递的，如果对于每一个 $x,y,z\in A$ ， $(xR{\color {darkgreen}y}{\text{ and }}{\color {darkgreen}y}Rz)\implies xRz$ .

练习。 令 $A$ 为一个集合， $R$ 为在 $A$ 上定义的关系。写出 (i) $R$ 不是自反的；(ii) $R$ 不是对称的；(iii) $R$ 不是传递的。

解答

(i) 存在 $x\in A$ 使得 $x\not Rx$ .

(ii) 存在 $x,y\in A$ 使得 $xRy$ 但 $y\not Rx$ .

(iii) 存在 $x,y,z\in A$ 使得 $xRy$ 且 $yRz$ ，但 $x\not Rz$ .

示例. 令 $A=\{1,2\}$ ，并令在 $A$ 上定义的关系为 $R=\{(1,1),(2,2),(1,2)\}.$ 那么， $R$ 是自反的，因为 $(1,1),(2,2)\in R$ 。但 $R$ 不是对称的，因为 $(1,2)\in R$ 但 $(2,1)\notin R$ 。

练习. $R$ 是传递的吗？解释原因。

解答

$R$ 是传递的，因为

$1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$ ;
$1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$ .

(关系 $R$ 中没有更多满足 $(x,y)\in R$ 和 $(y,z)\in R$ 的有序对 $(x,{\color {darkgreen}y})$ 和 $({\color {darkgreen}y},z)$ 。)

示例。 整数同余关系 $R=\{(a,b):a\equiv b{\pmod {n}}\}$ 定义了在 $\mathbb {Z}$ 上的关系 ( $n\in \mathbb {N}$ 且 $n\geq 2$ )。证明 $R$ 是自反的、对称的和传递的。

证明。

自反性: 对于任意 $x\in \mathbb {Z}$ ， $x\equiv x{\pmod {n}}$ 。因此，对于任意 $x\in \mathbb {Z}$ ，都有 $xRx$ 。

对称性: 对于任意 $x,y\in \mathbb {Z}$ ， $xRy\implies x\equiv y{\pmod {n}}\implies x-y=kn\implies y-x=(-k)n\implies y\equiv x{\pmod {n}}\implies yRx$ ，其中 $k$ 是某个整数。

传递性: 对于所有 $x,y,z\in \mathbb {Z}$ ， ${\begin{aligned}xRy{\text{ and }}yRz&\implies x-y=kn{\text{ and }}y-z=k'n{\text{ for some }}k,k'\in \mathbb {Z} \\&\implies x-z=(x-y)+(y-z)=(k+k')n\\&\implies xRz.&(k+k'\in \mathbb {Z} )\end{aligned}}$

$\Box$

练习. 以下每个关系具有哪种性质，自反性、对称性和传递性？证明你的答案。

(a) $R=\{(x,y)\in \mathbb {R} ^{2}:x\leq y\}$ .

(b) $R=\{(x,y)\in \mathbb {R} ^{2}:x<y\}$ .

(c) $R=\{(x,y)\in \mathbb {Z} \times \mathbb {Z} :xy>0\}$ .

解答

(a) $R$ 是自反的，不对称的，且是传递的。

证明。

自反性: 对于所有 $x\in \mathbb {R}$ ， $x\leq x$ 。所以， $xRx$ .

非对称: 取 $x=1$ 和 $y=2$ 。那么， $1\leq 2$ ，所以 $xRy$ 。然而， $2>1$ 。所以， $y\not Rx$ 。

传递性: 对于所有 $x,y,z\in \mathbb {R}$ ， $xRy{\text{ and }}yRz\implies x\leq y{\text{ and }}y\leq z{\text{ and }}x\leq z\implies xRz$ （这实际上遵循“ $\leq$ ”的性质）。

$\Box$

(b) $R$ 非自反，非对称，但具有传递性。

证明。

自反性: 取 $x=1$ 。那么，1 不小于它本身。因此， $1\not R1$ 。

非对称: 取 $x=1$ 和 $y=2$ 。那么， $1<2$ ，所以 $xRy$ 。然而， $2>1$ 。所以， $y\not Rx$ 。

传递性: 对于所有 $x,y,z\in \mathbb {R}$ ， $xRy{\text{ and }}yRz\implies x<y{\text{ and }}y<z{\text{ and }}x<z\implies xRz$ （这实际上遵循“ $<$ ”的性质）。

$\Box$

(c) $R$ 是自反的、对称的，但不是传递的。

证明。

自反性：对于每个 $x\in \mathbb {Z}$ ，

情况 1： $x\geq 0$ 。然后， $x(x)\geq 0$ 。因此， $xRx$ 。

情况 2： $x<0$ 。然后， $x(x)>0$ 。因此， $xRx$ 。

对称性：对于每个 $x,y\in \mathbb {Z}$ ， $xRy\implies xy\geq 0\implies yx=xy\geq 0\implies yRx$ 。

非传递性：取 $x=1,y=0$ 和 $z=-1$ 。然后， $xy=0$ 和 $yz=0$ 。因此， $xRy$ 和 $yRz$ 。然而，由于 $xy=-1<0$ ， $x\not Rz$ 。

$\Box$

练习。 令 $R$ 为集合 $A$ 上的关系。证明或反驳以下说法：

(a) 如果 $R$ 是自反的，则 $R^{-1}$ 也是自反的；

(b) 如果 $R$ 是对称的，那么 $R^{-1}$ 是对称的；

(c) 如果 $R$ 是传递的，那么 $R^{-1}$ 是传递的。

等价关系和等价类

在研究集合上的关系可以具有的三个性质后，让我们关注那些具有 所有三个 性质的关系。

定义。 (等价关系) 令 $A$ 为一个集合。在 $A$ 上定义的关系 $R$ 是一个 等价关系，如果它是自反的、对称的和传递的。

备注。

要证明一个关系不是等价关系（即，反驳该关系是等价关系），只要证明以下任何一个即可：(i) 它不是自反的；(ii) 它不是对称的；(iii) 它不是传递的，通过考虑上述定义的否定。

示例。 令 $A=\{1,2\}$ 。另外，令在 $A$ 上定义的关系为 $R=\{(1,1),(2,2),(1,2),(2,1)\}.$ 证明或反驳 $R$ 是一个等价关系。

证明。

自反性：由于 $(1,1),(2,2)\in R$ ， $R$ 是自反的。

对称性：由于 $(1,1)\in R\implies (1,1)\in R$ ， $(2,2)\in R\implies (2,2)\in R$ ， $(1,2)\in R\implies (2,1)\in R$ ，并且 $(2,1)\in R\implies (1,2)\in R$ ， $R$ 是对称的。

传递性：因为对于每一个 $x,y,z\in A$ ， $xRy{\text{ and }}yRz\implies xRz$ ， $R$ 是传递的。

$\Box$

练习。 给出另一个定义在 $A$ 上的等价关系。

解答

$R=\{(1,1),(2,2)\}$ 。可以证明它是自反的、对称的和传递的。

示例。 由于整数的同余关系定义了一个自反的、对称的和传递的关系，因此它定义了 $\mathbb {Z}$ 上的等价关系。

假设 $R$ 是集合 $A$ 上的等价关系。直观上，对于由 $R$ 关联的元素，它们非常“密切相关”。因此，当我们考虑由与集合 A 中给定元素相关的元素组成的集合时，集合中的元素是“密切相关的”，因此，从某种意义上说，该集合形成了一个由“亲属”组成的“组”。然后，似乎我们可以根据等价关系将集合 $A$ 的元素分类到不同的“组”中。正如我们将看到的，这大致上就是这种情况。因此，这样的“组”非常重要。现在，让我们正式定义“组”是什么。

定义。 （等价类）

一个用于说明等价类的图。整个圆圈表示定义关系的集合，当两个点之间有连接线时，表示这两个点（代表集合中的元素）由等价关系关联。

令 $R$ 是定义在集合 $A$ 上的等价关系。对于每一个 $a\in A$ ，集合 $[a]=\{x\in A:xRa\}$ ，它包含了 $A$ 中所有与 $a$ 相关的元素，被称为 （等价）类 $a$ 由 $R$ 确定。

示例。 令 $A=\{1,2,3,4\}$ ，并在 $A$ 上定义一个关系 $R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,1),(3,1),(2,3),(3,2)\}.$ 可以证明该关系 $R$ 是一个等价关系。其等价类由 $[1]=\{1,2,3\},[2]=\{1,2,3\},[3]=\{1,2,3\},[4]=\{4\}.$ 由于 $[1]=[2]=[3]$ ，因此只有两个 不同的 等价类。图形化地，情况看起来像这样

*----------**
|  .  .   / |
| 2   3  /  |
|  .    /.  |
| 1    /  4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]    [4]
=[3]

练习。 在 $A$ 上构造一个等价关系 $R$ ，使得等价类由 $[1]=\{1,2\},[2]=\{1,2\},[3]=\{3,4\},[4]=\{3,4\}.$

解答

$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)$ 。图形化地，情况看起来像这样

*---*-------*
|  .| .     |
| 2 | 3     |
|  .\    .  |
| 1  \    4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]  [3]=[4]

示例。（模 $n$ 的整数）回想一下，整数的同余关系定义了在 $\mathbb {Z}$ 上的一个等价关系 $R$ 。使用该等价关系，我们可以定义每个 $a\in \mathbb {Z}$ 的等价类 $[a]$ ，如下所示

$[0]=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=\{\dotsc ,-2n,-n,0,n,2n,\dotsc \}$
$[1]=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=\{\dotsc ,-2n+1,-n+1,1,n+1,2n+1,\dotsc \}$
...
$[n-1]=\{x\in \mathbb {Z} :xR(n-1)\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=\{\dotsc ,-2n+(n-1),-n+(n-1),n-1,n+(n-1),2n+(n-1),\dotsc \}=\{\dotsc ,-2n-1,-n-1,-1,2n-1,\dotsc \}$
$[n]=\{x\in \mathbb {Z} :xRn\}=\{x\in \mathbb {Z} :x\equiv n{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=[0]$
$[n+1]=\{x\in \mathbb {Z} :xR(n+1)\}=\{x\in \mathbb {Z} :x\equiv n+1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=[1]$

我们可以观察到，从 $[n]$ 开始，这些类与之前的类并不不同。实际上，如果我们“反向”考虑这些类

$[-1]=\{x\in \mathbb {Z} :xR(-1)\}=\{x\in \mathbb {Z} :x\equiv -1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=[n-1]$
$[-2]=\{x\in \mathbb {Z} :xR(-2)\}=\{x\in \mathbb {Z} :x\equiv -2{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-2{\pmod {n}}\}=[n-2]$
...

它们也不会产生新的类。

因此，我们得出结论，只有 $n$ 个不同的等价类，即 $[0],[1],\dotsc ,[n-1]$ 。通常，这些等价类的集合， $\{[0],[1],\dotsc ,[n-1]\}$ ，用 $\mathbb {Z} _{n}$ 表示，称为 模 $n$ 的整数。注意 $\mathbb {Z} _{n}$ 本身是一个有限集，但它的每个元素都是一个无限集。

备注。

我们可以用以下方式说明等价类（每列都是一个等价类，整个表格是 $\mathbb {Z}$ ）

*----*----*---...---*-----*
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
|-n  |-n+1|         |-2n-1|
| 0  | 1  |  ....   | n-1 |
| n  |n+1 |         |2n-1 |
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
*----*----*---...---*-----*

当我们考虑模 $m$ 的整数和模 $n$ 的整数（ $m\neq n$ ）一起时，对于元素可能会出现一些歧义。例如， $\mathbb {Z} _{2}=\{[0],[1]\}$ 和 $\mathbb {Z} _{3}=\{[0],[1],[2]\}$ 。然而，例如， $\mathbb {Z} _{2}$ 中的 " $[0]$ " 和 $\mathbb {Z} _{3}$ 中的 " $[0]$ " 是不同的。其中一个包含所有偶数，另一个包含所有 3 的倍数。

为了避免这种歧义，我们可以给类添加下标。例如，我们可以写 $\mathbb {Z} _{2}=\{[0]_{2},[1]_{2}\}$ 和 $\mathbb {Z} _{3}=\{[0]_{3},[1]_{3},[2]_{3}\}$ 。

练习. 在 $\mathbb {Z}$ 上定义的关系 $R$ 由 $aRb{\text{ if }}3a+b\equiv 0{\pmod {4}}.$ (a) 证明 $R$ 是一个等价关系。

(b) 用 $[0]_{4},[1]_{4},[2]_{4},[3]_{4}$ 表示 $R$ 的每个等价类 $[0]_{R},[1]_{R},[2]_{R},[3]_{R}$ 。（提示: 使用 $R$ 的对称性）。

解答

(a)

证明。

自反性: 对于每个 $x\in \mathbb {Z}$ ，由于 $3x+x=4x\equiv 0{\pmod {4}}$ ， $xRx$ .

对称性: 对于每个 $x,y\in \mathbb {Z}$ ，由于 $xRy\implies 3x+y\equiv 0{\pmod {4}}\implies 9x+3y\equiv 0{\pmod {4}}\implies 9x-8x+3y\equiv \underbrace {-8x} _{\text{multiple of 4}}\equiv 0{\pmod {4}}\implies yRx$ .

传递性：对于任意 $x,y,z\in \mathbb {Z}$ ， ${\begin{aligned}xRy{\text{ and }}yRz&\implies 3x+y\equiv 0{\pmod {4}}{\text{ and }}3y+z\equiv 0{\pmod {4}}\\&\implies (3x+y)+(3y+z)\equiv 0{\pmod {4}}\\&\implies 3x+z+4y\equiv 0{\pmod {4}}\\&\implies 3x+z\equiv -4y\equiv 0{\pmod {4}}\\&\implies xRz.\end{aligned}}$

$\Box$

(b) $[0]_{R}=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :0Rx\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {4}}\}=[0]_{4}.$ (根据 $R$ 的对称性， $xR0\implies 0Rx$ 。同样， $0Rx\implies xR0$ 。因此， $xR0\iff 0Rx$ 。) $[1]_{R}=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :1Rx\}=\{x\in \mathbb {Z} :3+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :4+x\equiv 1{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {4}}\}=[1]_{4}.$ $[2]_{R}=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :2Rx\}=\{x\in \mathbb {Z} :6+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :8+x\equiv 2{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 2{\pmod {4}}\}=[2]_{4}.$ $[3]_{R}=\{x\in \mathbb {Z} :xR3\}=\{x\in \mathbb {Z} :3Rx\}=\{x\in \mathbb {Z} :9+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :12+x\equiv 3{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 3{\pmod {4}}\}=[3]_{4}.$

等价类的性质

在本节中，我们将讨论等价类的一些性质。特别是，我们将解决这两个问题

什么时候两个等价类相等？
两个不同的等价类可以包含一个公共元素吗？

问题 1 的答案由以下定理给出。

定理。 令 $R$ 是定义在集合 $A$ 上的等价关系。对于每个 $a,b\in A$ ， $[a]=[b]{\text{ if and only if }}aRb.$

证明。 " $\Rightarrow$ " 方向：假设 $[a]=[b]$ 。由于 $R$ 是等价关系，特别是自反的，我们有 $aRa$ 。因此，根据定义，我们有 $a\in [a]$ 。然后，由于假设 $[a]=[b]$ ，我们有 $a\in [b]$ 。

" $\Leftarrow$ " 方向：假设 $aRb$ 。首先，对于每个 $x\in A$ ， ${\begin{aligned}x\in [a]&\implies xRa&({\text{definition}})\\&\implies xRb&(aRb{\text{ and }}{\text{transitivity of }}R)\\&\implies x\in [b].&({\text{definition}})\\\end{aligned}}$ 所以， $[a]\subseteq [b]$ 。

另一方面，首先，由于假设有 $aRb$ ，根据 $R$ 的对称性，我们有 $bRa$ 。现在，对于每一个 $y\in A$ ， ${\begin{aligned}y\in [b]&\implies yRb&({\text{definition}})\\&\implies yRa&(bRa{\text{ and transitivity of }}R)\\&\implies y\in [a].&({\text{definition}})\\\end{aligned}}$ 所以， $[b]\subseteq [a]$ 。

因此， $[a]=[b]$ 。

$\Box$

备注。

根据该定理，我们知道“ $aRb$ ”是“ $[a]=[b]$ ”的充要条件。此外，如果且仅如果 $a\not Rb$ ，则有 $[a]\neq [b]$ 。

现在，让我们考虑问题2。问题2 的答案确实是“否”。下面的推论证明了这个答案。

推论。 设 $R$ 是定义在非空集合 $A$ 上的等价关系。对于每一个 $a,b\in A$ ， $[a]\neq [b]{\text{ if and only if }}[a]\cap [b]=\varnothing .$

证明。 " $\Leftarrow$ " 方向： ${\begin{aligned}{}[a]\cap [b]=\varnothing &\implies [a]{\text{ and }}[b]{\text{ have distinct elements}}&([a]{\text{ and }}[b]{\text{ are nonempty}})\\&\implies [a]\neq [b].\end{aligned}}$ ( $[a]$ 和 $[b]$ 是非空的，因为 $R$ 是自反的。因此它们至少包含 $a$ 和 $b$ 分别。）

" $\Rightarrow$ " 方向：我们使用逆否证法。 ${\begin{aligned}{}[a]\cap [b]\neq \varnothing &\implies \exists x\in [a]\cap [b]\\&\implies xRa{\text{ and }}xRb\\&\implies aRx{\text{ and }}xRb&(R{\text{ is symmetric}})\\&\implies aRb&(R{\text{ is transitive}})\\&\implies [a]=[b].&({\text{above theorem}})\\\end{aligned}}$

$\Box$

备注。

从这个结果中，我们知道两个等价类要么相等，要么不相交（因为它们要么相等，要么不相等）。因此，两个不同的等价类不可能包含一个共同的元素。

现在我们已经到达了研究等价关系的一个关键点（这可能是研究等价关系的主要原因）：使用集合上的等价关系来构建该集合的划分，反之亦然。在讨论它之前，让我们定义一个集合的划分

定义。 （划分）非空集 $A$ 的划分是 $A$ 的一个集合，它包含 $A$ 的非空子集，且具有以下性质：每个 $A$ 的元素都属于唯一的一个子集。换句话说， $P$ 是 $A$ 的一个 两两不相交 且非空子集的集合，其 并集是 $A$ 。

示例。 令 $A=\{1,2,3\}$ 。则， $A$ 的一个划分是 $\{\{1\},\{2\},\{3\}\}$ 。另一个划分是 $\{\{1,2\},\{3\}\}$ 。但是， $\{\{1,2\},\{2,3\}\}$ 不是 $A$ 的划分，因为 $\{1,2\}$ 和 $\{2,3\}$ 不是不相交的（或元素“2”属于两个集合）。此外， $\{\{1\},\{3\}\}$ 不是 $A$ 的划分，因为 $\{1\}$ 和 $\{3\}$ 的并集不是整个集合 $A$ （或元素“2”不属于划分中的任何集合）。

练习. 是 $\{\{1,2,3\}\}$ $A$ 的一个划分吗？

解答

是的，因为 $A$ 的每个元素都属于划分中唯一的一个集合，即 $\{1,2,3\}$ 集合。

示例. 令 $A=\{1,2,3,4\}$ ，并令在 $A$ 上定义的关系为 $R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,1),(3,1),(2,3),(3,2)\}.$ 回想一下，两个不同的等价类由 $[1]=\{1,2,3\},[4]=\{4\}.$ 我们可以看到每个 $A$ 元素都属于 唯一一个 这些等价类。因此，集合 $\{[1],[4]\}=\{\{1,2,3\},\{4\}\}$ 给出了 $A$ 的一个划分。

此外，我们可以在 $A$ 上定义另一个等价关系 $R$ ，使得两个不同的等价类由 $[1]=\{1,2\},[3]=\{3,4\}.$ 我们也可以看到每个 $A$ 元素都属于 唯一一个 这些等价类。因此，集合 $\{[1],[3]\}=\{\{1,2\},\{3,4\}\}$ 。

示例. 回想一下，整数的同余关系定义了一个等价关系 $R$ 在 $\mathbb {Z}$ 上。此外，有 $n$ 个不同的等价类： $[0],[1],\dotsc ,[n-1]$ 。根据欧几里得除法引理，每个整数都属于 恰好一个 这些 $n$ 个等价类。因此，模 $n$ 的整数 $\mathbb {Z} _{n}=\{[0],[1],\dotsc ,[n-1]\}$ 给出了 $\mathbb {Z}$ 上的一个划分。

从前面的例子中我们可以观察到，集合的等价关系可以用来给出该集合的划分。下面的定理表明，一般情况下，集合 $A$ 上的等价关系可以用来给出该集合的划分。

定理. 设 $R$ 是在非空集合 $A$ 上定义的等价关系。那么由 $R$ 所确定的所有不同等价类的集合是 $A$ 的一个划分。

证明. 只需证明每个 $A$ 的元素都属于 恰好一个 不同的等价类。

对于每个 $x\in A$ ，由于 $R$ 是自反的，我们有 $x\in [x]$ 。由此我们可以保证 $A$ 的每个元素都属于 至少一个 不同的类。现在剩下要证明的是， $A$ 的每个元素也属于 至多一个 不同的类。

假设 $x$ 也属于类 $[y]$ 。那么，我们有 $xRy$ 。由于 $R$ 是一个等价关系，这意味着根据之前的定理 $[x]=[y]$ 。因此， $x$ 所属的任何两个等价类都是相等的。这意味着 $A$ 中的每个元素都不能属于多个不同的类。

因此， $A$ 中的每个 $x$ 都属于 恰好一个 不同的类，因此由 $R$ 给出的所有不同等价类的集合构成了 $A$ 的一个划分。

$\Box$

以下定理表明上述定理的逆命题也成立。更准确地说，我们可以利用集合的划分在该集合上构造一个等价关系。在介绍定理之前，让我们对如何以这种方式构造等价关系进行一些直观的猜测。首先，从之前的定理中，粗略地说，利用集合上的等价关系，我们可以创建几个不同类别中的元素“组”，其中元素是“亲属”。

现在，给定集合的划分，意味着我们有几个元素的“组”。这种“分组”直观地表明组内的元素在某种意义上是“亲属”。因此，直观地说，一个将“亲属”联系起来的关系似乎使关系相当“接近”，因此是一个等价关系。

以下定理形式化了这种直觉

定理。 令 $P$ 是非空集合 $A$ 的一个划分。定义一个关系 $R$ 在 $A$ 上，通过 $xRy{\text{ if there exists }}S\in P{\text{ such that }}x,y\in S.$ 。那么，关系 $R$ 是集合 $A$ 上的一个等价关系。

证明。 只需证明 $R$ 以这种方式定义的是自反的、对称的和传递的。

自反性：根据划分定义，对于每一个 $x\in A$ ， $x$ 属于 恰好一个 $S\in P$ ，因此存在 $S\in P$ 使得 $x\in S$ 。因此， $xRx$ 。

对称性：对于每一个 $x,y\in A$ ， ${\begin{aligned}xRy&\implies \exists S\in P,x,y\in S\\&\implies \exists S\in P,y,x\in S\\&\implies yRx.\end{aligned}}$ 传递性：对于每一个 $x,y,z\in A$ ，假设 $xRy$ 和 $yRz$ 。那么，存在 $S,T\in P$ 使得 $x,{\color {blue}y\in S}$ 和 ${\color {blue}y},z{\color {blue}\in T}$ 。但根据划分定义， $y$ 属于 恰好一个 划分 $P$ 中的集合。所以，我们有 $S=T$ 。因此，存在一个集合 $S$ （ $=T$ ）使得 $x,z\in S$ ，因此 $xRz$ 。

$\Box$

示例： 令 $R$ 是在 $\mathbb {Z}$ 上定义的关系，其中 $aRb{\text{ if }}|a|=|b|.$

(a) 证明 $R$ 是一个等价关系。

(b) 确定所有由 $R$ 产生的不同等价类，并以此给出在 $\mathbb {Z}$ 上的划分。

解答.

(a)

证明： 自反性：对于所有 $x\in \mathbb {Z}$ ， $|x|=|x|$ 。因此， $xRx$ 。

对称性：对于所有 $x,y\in \mathbb {Z}$ ， $xRy\implies |x|=|y|\implies |y|=|x|\implies yRx$ 。

传递性：对于所有 $x,y,z\in \mathbb {Z}$ ， $xRy{\text{ and }}yRz\implies |x|=|y|{\text{ and }}|y|=|z|\implies |x|=|z|\implies xRz$ 。

$\Box$

(b) 首先，一些等价类是 ${\begin{aligned}{}[0]&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :|x|=0\}=\{0\},\\{}[1]&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :|x|=1\}=\{-1,1\},\\{}[2]&=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :|x|=2\}=\{-2,2\},\dotsc \\\end{aligned}}$ 因此，所有不同的等价类是 $[0],[1],[2],\dotsc$ ( $-1\in [1]$ ，所以 $[-1]$ 与它们没有区别，等等）。因此， $A$ 上的划分是 $\{[0],[1],[2],\dotsc \}=\{[n]:n{\text{ is a nonnegative integer}}\}$ （也就是说，每个整数都属于 $[0],[1],[2],\dotsc$ 中的某一个）。

练习。 令 $R$ 是定义在 $\mathbb {Z}$ 上的关系，由 $aRb{\text{ if }}a+b{\text{ is even}}.$

(a) 证明 $R$ 是一个等价关系。

(b) 通过 $R$ 确定所有不同的等价类，并因此给出 $\mathbb {Z}$ 上的划分。

解答

(a)

证明。 自反性：对于每个 $x\in \mathbb {Z}$ ，由于 $x+x=2x$ 是偶数， $xRx$ 。

对称性：对于每个 $x,y\in \mathbb {Z}$ ， $xRy\implies x+y{\text{ is even}}\implies y+x=x+y{\text{ is even}}\implies yRx$ 。

传递性：对于每个 $x,y,z\in \mathbb {Z}$ ， ${\begin{aligned}xRy{\text{ and }}yRz&\implies x+y{\text{ is even}}{\text{ and }}y+z{\text{ is even}}\\&\implies (x+y)+(y+z)=x+2y+z{\text{ is even}}\\&\implies x+2y+z-2y{\text{ is even}}&(-2y{\text{ is even}})\\&\implies x+z{\text{ is even}}\\&\implies xRz.\\\end{aligned}}$

$\Box$

(b) 首先，一些等价类是 ${\begin{aligned}{}[0]_{R}&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x{\text{ is even}}\}=[0]_{2},\\{}[1]_{R}&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x+1{\text{ is even}}\}=\{x\in \mathbb {Z} :x{\text{ is odd}}\}=[1]_{2}.\\\end{aligned}}$ 因为每个整数都属于 $[0]_{2}$ 和 $[1]_{2}$ 中的某一个（即所有其他等价类都与它们不区分），因此可以得出 $[0]_{R}$ 和 $[1]_{R}$ 是所有不同的等价类。