第9章 等價關係與商集

9.1 哪些不同對象可以歸為同一類

相等要求是同一對象，等價則可以依明示標準把不同對象分到一類。設關係∼定義在A上，若對所有x、y、z∈A同時具有自反性x∼x、對稱性x∼y⇒y∼x，以及傳遞性(x∼y且y∼z)⇒x∼z，就稱為等價關係。

三個性質都必要。「看起來很接近」通常不傳遞；「小於或等於」雖自反、傳遞，卻不對稱。不能只因某個分類直覺方便就跳過資格檢查。

9.2 等價類與分割

對x∈A，定義[x]={y∈A:y∼x}，稱為x的等價類。因自反性，x∈[x]，所以每個由元素產生的類都非空；全部等價類覆蓋A。商集A/∼是這些等價類所成的集合，而不是隨便抽出幾個代表元的集合。

兩個等價類若相交，就相等。若z∈[a]∩[b]，由z∼a、z∼b及對稱、傳遞，得a∼b。對任意y∈[a]，y∼a再接a∼b，得到y∈[b]；反向同理。故不同類必互不相交，形成A的分割。

9.3 例題

例題1 同奇偶形成等價關係

在ℤ上定義a∼b若2∣(a−b)。自反性來自a−a=2·0；若a−b=2k，則b−a=2(−k)，得對稱性；若a−b=2k、b−c=2ℓ，相加得a−c=2(k+ℓ)，得傳遞性。

因此等價類只有偶整數類[0]與奇整數類[1]。例如[−1]=[1]，因−1−1=−2為2的倍數；但−1與1不是同一個整數。類相等不表示代表元相等。

例題2 模3的類與商映射

在ℤ上定義a∼b若3∣(a−b)。三項性質與例題1同樣由0、負號、加法的整數見證得到。每個整數除以3的唯一餘數為0、1或2，所以ℤ/∼={[0],[1],[2]}。

商映射q:ℤ→ℤ/∼定義q(a)=[a]。它是滿射，因商集的每個元素本來就是某個[a]；它不是單射，因q(0)=q(3)但0≠3。這個滿射理由是對任意等價類的一般理由，不是只試三個箭頭。

例題3 從有限分割建立關係

設A={1,2,3,4,5}，分成非空區塊{1,4}、{2,5}、{3}，兩兩不交且聯集為A。定義x∼y當它們在同一區塊。

每個元素和自己同區塊，故自反；同區塊不分次序，故對稱。若x、y同塊且y、z同塊，因兩塊若共含y就必是同一塊，所以x、z也同塊，得傳遞。商集就是這三個區塊的集合。

例題4 代表元運算需要良定性

在模3商集上想定義[a]+[b]=[a+b]，必須證明換代表元不改結果。若a'∼a、b'∼b，則a'−a=3r、b'−b=3s，其中r、s∈ℤ。

因此(a'+b')−(a+b)=3(r+s)，故[a'+b']=[a+b]。這就證明了加法的良定性。只算出[1]+[2]=[0]是一個例子，不能代替任意代表元變換的理由。

9.4 類 代表元與記號

[a]是一整個集合，a只是其中一個代表。在模3情形，可用0、1、2標記三個類，但這是簡寫，不會讓[1]={1}。類內還有−2、4、7等無窮多整數。

從A到商集的操作會忘記部分差異，因此商集上的新函數或運算必須尊重等價關係。若同一類的不同代表能算出不同目標類，就不能把它當成類本身的良定操作。

9.5 練習

1. B05-C09-Q01 在A={1,2,3}上，普通相等是否為等價關係？列出商集。
2. B05-C09-Q02 在ℤ上，a∼b定義為|a|=|b|，證明為等價關係，並求[0]、[2]。
3. B05-C09-Q03 在ℤ上，aRb定義為a≤b，哪個等價關係資格失敗？
4. B05-C09-Q04 在ℝ上，aRb定義為|a−b|<1，逐項檢查三種性質。
5. B05-C09-Q05 在模3關係下，求[−2]、[4]是否相等，並判斷[4]與[0]。
6. B05-C09-Q06 設a、b、c、d為四個互異元素，A={a,b,c,d}，分割為{a,c}、{b,d}。列出對應關係的全部有序對。
7. B05-C09-Q07 在模3商集上計算[2]+[2]，再改用代表元5與−1核對，說明一般良定理由。
8. B05-C09-Q08 依第2題的絕對值等價關係，試用[a]+[b]=[a+b]定義加法，是否良定？
9. B05-C09-Q09 A=∅時，空關係是否為等價關係？商集是∅還是{∅}？
10. B05-C09-Q10 A={1,2,3}，R含所有自反對，再含(1,2)、(2,1)、(2,3)、(3,2)。它是否等價？若要保留原有關係，最少還需加哪些對？

9.6 完整解答

Q01

相等具自反、對稱與傳遞三性質，因此是等價關係。每個數只和自己相等，所以商集為{{1},{2},{3}}。商集有三個元素，而每個元素是一個單元素類，不要漏掉外層集合括號。

Q02

由實數相等的三性質，|a|=|a|、等號可反向、相等可傳遞，得到此關係的三性質。[0]={0}；[2]={−2,2}，因整數滿足|y|=2恰有這兩種可能。一般非零類將正負兩個整數歸為一類。

Q03

自反與傳遞成立，但對稱失敗：1≤2卻2不小於等於1。只要一項失敗就不是等價關係，不需把已成立的兩項也判錯。

Q04

自反成立，因|a−a|=0<1；對稱成立，因|a−b|=|b−a|。傳遞失敗：取a=0、b=3/4、c=3/2，前兩段距離都為3/4<1，但|a−c|=3/2≥1。因此「相距不到1」不能直接產生互不相交的等價類分割。

Q05

−2與4之差為−6，被3整除，所以[−2]=[4]，其餘數標記皆為[1]。4−0=4不被3整除，所以[4]≠[0]。判斷類相等時比較兩個代表是否等價，而不是代表的數值是否相等。

Q06

同在第一塊產生(a,a)、(a,c)、(c,a)、(c,c)；第二塊產生(b,b)、(b,d)、(d,b)、(d,d)。聯集共8對。跨不同塊的有序對不屬於關係，且每個自反對都保留。

Q07

[2]+[2]=[4]=[1]。5與−1都同2模3，所以改算5+(−1)=4仍落在[1]。這次代入只是核對；一般良定性由(a'+b')−(a+b)=3(r+s)建立，確保任何合格換代表元都得到相同類。

Q08

不良定。因[1]=[−1]，同樣的兩個輸入類可用1、1或−1、1作代表。第一路得到[2]，第二路得到[0]；在絕對值關係中這兩類不同。所以不能把代表元相加自動當作類的加法。

Q09

空關係在空集合上三種全稱資格都空真，因此是等價關係。商集定義為{[x]:x∈A}，此時沒有x可以產生等價類，故商集為∅，不是含一個空類的{∅}。每個實際產生的等價類非空，並不迫使商集一定有元素。

Q10

它自反且對稱，但不傳遞，因1R2且2R3卻沒有1R3。必須補(1,3)；為對稱還須補(3,1)。補完後就是A×A，三項資格全部成立，商集只有一類A。這兩對都由原關係的必要性迫使加入，故已是最少。

9.7 本章回看

等價關係把集合分成互不重疊的非空類；商集以類作元素。把分類壓成一個記號時，代表元選擇不能悄悄改變運算結果。