4. 關係、等價類與次序

學習目標與定義

識別等價關係和偏序，證明與劃分的對應關係，並檢查商集運算的良定義性。$X$ 上的關係 $R$ 是 $X\times X$ 的子集；當 $(x,y)\in R$ 時寫 $xRy$。

若對每個 $x$ 有 $xRx$，關係是自反的；若 $xRy$ 蘊含 $yRx$，它是對稱的；若 $xRy$ 和 $yRz$ 蘊含 $xRz$，它是傳遞的。等價關係滿足這三個條件。$x$ 的等價類為 $[x]=\{y\in X:yRx\}$，$X/R$ 是這些類組成的集合。代表元是用於命名類的元素，不是類本身。

偏序是自反、反對稱且傳遞的。反對稱意味著 $xRy$ 和 $yRx$ 同時成立會迫使 $x=y$，而不是說每一對元素都不滿足對稱性。全序還要求每一對元素都可比較。包含關係是 $\mathcal P(X)$ 上的偏序，但通常不是全序。

定理：等價關係與劃分

等價關係的各類非空、覆蓋 $X$，且任意兩類相等或不相交。反過來，任何由非空不相交塊組成的劃分，都可通過屬於同一塊來定義等價關係。

證明。 自反性使每個 $x$ 屬於 $[x]$，證明非空性和覆蓋性。若 $z\in[x]\cap[y]$，則 $zRx$ 且 $zRy$，由對稱性和傳遞性得 $xRy$。若 $w\in[x]$，則 $wRx$ 和 $xRy$，故 $wRy$，所以 $[x]\subseteq[y]$。交換 $x,y$ 得到相等。反過來，每點屬於唯一的塊；同屬一塊具有自反性和對稱性。若 $x,y$ 同屬一塊而 $y,z$ 同屬另一塊，兩塊有交集，故相同，從而具有傳遞性。

商集運算與例題

對整數 $m\ge2$，若 $m\mid(a-b)$，定義 $a\sim b$。整除性驗證自反、對稱和傳遞：差分別是 $0$、$m$ 的倍數的相反數及倍數之和。由整數除法，商集的類為 $[0],\ldots,[m-1]$。

定義加法 $[a]+[b]=[a+b]$ 和乘法 $[a][b]=[ab]$。要使定義良好，替換任一代表元都不能改變所得類。若 $a-a'=ms$、$b-b'=mt$，則 $(a+b)-(a'+b')=m(s+t)$，並且

$$ab-a'b'=(a-a')b+a'(b-b')=m(sb+a't).$$

所以兩種運算都良定義。相反，試圖定義 $[a]\le[b]$ 當且僅當 $a\le b$ 會失敗：模三時 $[0]=[3]$，但 $0\le1$、$3\nleq1$ 對同一對類給出衝突結果。

次序例題。 在正整數上，整除關係是偏序。若 $a\mid b$ 且 $b\mid a$，寫 $b=ka,a=\ell b$，其中 $k,\ell$ 為正整數；於是 $k\ell=1$，故 $a=b$。它不是全序，因為既無 $2\mid3$，也無 $3\mid2$。

分層練習

1. 基礎。 在 $\mathbb Z$ 上，當 $a-b$ 為偶數時定義 $aRb$。證明它是等價關係並列出各類。
2. 核心。 在 $\mathbb R$ 上，以 $|a-b|\le1$ 定義的 $aRb$ 是否為等價關係？逐一檢查各性質。
3. 核心。 在模五整數中解 $[2][x]=[1]$，並解釋答案為何不依賴代表元的選擇。
4. 證明。 對等價關係，證明 $[x]=[y]$ 當且僅當 $xRy$。

詳解

1. 零為偶數；偶數差的相反數仍為偶數；兩個偶數差之和仍為偶數。這分別證明自反、對稱和傳遞性。兩類分別是偶整數 $[0]$ 和奇整數 $[1]$。
2. 由於 $|a-a|=0$，它是自反的；由於絕對差對稱，它是對稱的。它不傳遞：$0R1$、$1R2$，但不滿足 $0R2$。故不是等價關係。
3. $2\cdot3=6\equiv1\pmod5$，所以 $[x]=[3]$ 是解。若 $2x\equiv1$，乘以 $3$ 得 $x\equiv3$，證明唯一性。上面已證明類的乘法良定義，所以把 $x$ 改變五的倍數不會改變乘積類。
4. 若類相等，自反性給出 $x\in[x]=[y]$，即 $xRy$。若 $xRy$，則 $x\in[x]$ 且 $x\in[y]$，所以兩類相交，由劃分定理它們相等。

總結與術語

劃分將集合分成不相交的非空塊；等價類是關係誘導的一個塊。若代表元的所有選擇都給出相同輸出，商集規則是良定義的。偏序允許不可比較的元素，全序不允許。逐一檢查定義性質，未經代表元檢驗，不要將公式轉移到類上。