數學證明/關係

介紹

直觀地說，關係根據某些規則和屬性將成對的物件關聯起來。也就是說，關係表明了兩個物件之間某種關係或聯絡。以婚姻為例。在婚姻登記處，有一個記錄，其中丈夫的姓名與其對應妻子的姓名相關聯，以跟蹤婚姻狀況。記錄中的條目可以解釋為 有序對 $(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}$ 是所有不同的等價類。