動機
商集構造從一個決定開始:把某些不同描述視為同一個對象。這個決定會帶來進一步的後果。如果描述 與 被認同,而 又與 被認同,那麼 也必須與 被認同。因此,只列出最初希望認同的有序對,未必已經得到新對象之間合理的相等關係。
商集存在以後,還有另一個問題:用代表元寫出的公式,在改用同一類的另一個代表元時,是否給出相同答案?這就是商集上的公式良定義的意思。它是一項需要證明的結論,不能靠約定把原本有歧義的規則變成有效定義。
本篇在 ZF 中說明這兩個步驟。我們使用前文對有序對、函數圖像、自然數與商集的構造,不假設選擇公理。
從有限認同生成關係
固定集合 及關係 。記 表示 。這裏不要求 自反、對稱或傳遞;它的有序對只指定我們最初要施加的認同。
定義 1.4.1
(-路徑與生成的關係)
從 到 的一條 -路徑是有限序列 ,其中 ,並滿足 、,以及對每個 ,
路徑的長度是步數 ,所以長度零的路徑仍有一個頂點。我們容許沿 中的有序對朝任何一個方向走,因為兩個對象是否被認同,不應取決於最初把哪一個寫在前面。定義
在 內使用分離公理,便得到集合關係 。路徑本身也有明確的集合界限:每個序列的圖像均包含於 ,因此所有候選圖像都屬於 。再以分離選出定義域為有限非空初始段、並滿足邊條件的函數即可。這裏沒有使用所謂「任意定義域上所有函數構成的集合」。
定理 1.4.2
(包含給定關係的最小等價關係)
是 上包含 的等價關係。如果 是 上任何包含 的等價關係,那麼 。
證明
(路徑給出最小等價關係)
只有頂點 的路徑說明 。把一條路徑倒轉便證明對稱性,因為每一步都容許雙向通過。給定從 到 及從 到 的路徑,把它們接起來,共同端點 只寫一次,就得到從 到 的路徑;即使其中一條長度為零也成立。因此 傳遞。若 ,便有長度一的路徑,所以 。
現在設 如命題所述。路徑的每一步都是一個 -步驟:若該步反向經過某個 -有序對,就使用 的對稱性。對路徑長度歸納,長度零時使用自反性,每增加一步使用傳遞性,便知兩端點 -相關。因此 。
同一個構造也可以寫成交集。令
這是非空集合,因為 屬於其中;即使 也一樣。其成員的交集仍然自反、對稱、傳遞,並包含 :每一項性質都能從所有成員傳到交集。因此,由剛證明的最小性,
交集描述的是每一種容許的認同體系都必須包含的關係;有限路徑則為屬於該關係提供具體見證。兩個構造都沒有選擇代表元。
證明透視
有限路徑為何恰好完成所需的閉包
證明需要兩個方向。先證明路徑關係足夠大:它包含原有的有序對,而且滿足等價關係公理。再證明它沒有過大:任取一個包含原關係的等價關係,把所有路徑的端點關係都放進其中。第二個方向排除了意外加入不必要認同的可能。
「把缺少的有序對補進去」這句話會隱藏兩項任務。有限路徑使傳遞性的來源具體可見,而與任意包含關係比較的論證,給出了不依賴逐項搜尋所有閉包的最小性證明。
等價關係與分劃
定義 1.4.3
(分劃與商集)
的一個分劃是集合 ,其成員稱為塊,要求每塊非空、各塊的並為 ,而不同塊互不相交。空集的分劃是 ,不是 ,因為後者包含空塊。
對 上的等價關係 ,定義
前文以 作為界限構造了 。商集的成員是 的完整子集,並非某個未指明的「首選元素」的名稱。
定理 1.4.4
(分劃恰好是等價類的全體)
等價關係 的各等價類構成 的分劃,而且
反過來,一個分劃 透過「某一塊同時包含 」定義等價關係。這兩個構造互為逆構造。
證明
(等價類與塊互相決定)
自反性給出 ,所以每個類非空,而所有類覆蓋 。若 且 ,由對稱性與傳遞性得到 ;交換角色得到反向包含,因此兩個類相等。反過來,若兩個類相等,則 ,所以 。
若 同時屬於 與 ,則 、,再使用對稱性和傳遞性便得到 。因此有交點的類必相等,不同類便互不相交。
現在從分劃出發。每個點都屬於唯一一塊:存在性來自聯集條件;兩塊若包含同一點,便因相交而相等。「同屬一塊」顯然自反、對稱。若 同屬一塊,而 同屬另一塊,這兩塊因都包含 而相等,所以 同屬一塊。這證明了傳遞性。所得關係中 的等價類恰好是包含 的唯一塊,因此恢復原分劃。若從 出發,命題顯示的等價式又從類的分劃恢復 。空集情形同樣滿足所有結論。
投影 定義為 ,它是滿射。商集中的點 在 下的纖維,恰好就是原集合的子集 。同一個類在這裏有「目標中的點」與「定義域中的一組點」兩種角色,因此要分清楚兩個集合。
函數何時能夠經過商集
定義 1.4.5
(核等價關係)
給定函數 ,定義它的核等價關係為
這裏的「核」表示輸出相等,毋須有群或向量空間結構。由相等關係的自反、對稱、傳遞性,立即知道 是等價關係。
定理 1.4.6
(經過等價類的分解)
設 是 上的等價關係。存在唯一函數 滿足 ,當且僅當 。條件成立時, 是滿射當且僅當 是滿射; 是單射當且僅當 。
證明
(以唯一輸出經過商集分解)
若已有這樣的分解,且 ,則 ,所以 。這證明必要的包含關係。
反過來,設 。在 內定義圖像
每個類至少有一個這樣的輸出。若 都代表 ,則它們 -相關,所以 ,輸出唯一。分離公理因而給出函數圖像 ,定義所需的 。任何其他分解都必須把 送到 ,而每個類都有這種形式,所以分解唯一。
與 的值域完全相同,故有關於滿射的結論。若 是單射,且 ,兩個輸入類便必須相等,因此 。於是 ,結合已知包含關係得到相等。反過來,若 ,且 ,則 ,故 ,兩個類相等。這證明單射性。
特別地,我們得到一個典範雙射
因此,任意集合函數都能分成三個步驟:滿射投影、到像集的雙射,以及像集到原定陪域的包含映射。這是 ZF 中關於任意集合的定理。
概念視角結構
唯一輸出取代代表元選擇
寫下 ,不是要求從每一個類選一個 。圖像證明考察所有可能代表元,並證明它們給出同一個輸出。唯一性使我們毋須選擇規則便得到函數。
若不同代表元給出不同答案,加入額外資料後選擇首選代表元,也許能定義另一個函數。但這不能證明原規則與代表元無關。由不同描述的等價類構造數系或模型時,這一區分尤其有用。
對於由生成元指定的關係,檢驗還可以簡化: 能經過 分解,當且僅當 總蘊含 。必要性來自 。充分性來自輸出相等能沿每條路徑傳遞,因此 。也可以說, 是包含 的等價關係,直接應用最小性即可。
比較與合併等價關係
固定集合 上的等價關係都是 的子集,所以它們構成一個集合,並以包含關係排成偏序。較小的關係認同較少的有序對,對應的分劃也較細。於是有兩個問題:兩個可比較的關係所給出的商集有何聯繫?能認同兩個關係中任何一個所認同之物的最小關係又是甚麼?
定理 1.4.7
(較細與較粗關係的商集)
設 是 上的等價關係,投影分別為 與 。存在唯一函數 滿足 ,即 ,而且它是滿射。在 上由
給出的關係 是良定義的等價關係。它等於核關係 ,而 誘導出雙射 。
證明
(兩次應用分解定理)
分劃一節證明的類等式說明 當且僅當 ,所以 。因此假設 正是分解定理所需的條件 ,由此得到唯一的 。由於 是滿射, 也是滿射。
其次, 的意思是 ,即 。所以上式描述的正是核關係 ,它是 上的等價關係。 只由類本身定義,因此這個條件不可能依賴所取的代表元 。最後,對 及 應用分解定理,得到誘導映射 :它是滿射,因為 是滿射;它是單射,因為 就是整個核。
定義 1.4.8
(兩個關係的複合)
對關係 ,定義
與函數一樣,先作用的是 。關係的複合滿足結合律: 與 都恰好在存在 使 、、 時包含 。此外 。
定理 1.4.9
(兩個等價關係的交與合)
設 與 是 上的等價關係。
- 是等價關係,並且是同時包含於 與 的最大等價關係。
- 包含 的最小等價關係是 ,稱為 與 的合。 成立,當且僅當對某個 ,存在 中的 ,使每個 都滿足 及 。
- 是等價關係,當且僅當 。此時 。
證明
(交替鏈與可交換的複合)
第 1 部分。 自反、對稱、傳遞三條性質,各自都是說:只要某些有序對屬於關係,另一些有序對也屬於它。若這些性質對 與 都成立,則對 也成立。任何同時包含於 與 的等價關係都包含於 。
第 2 部分。 由本篇第一條定理, 是包含 的最小等價關係。交替鏈是一條 -路徑,由此得到一個方向的包含。反過來,取一條從 到 的 -路徑。由於 與 都對稱,每一步不論沿哪個方向走,都可看作向前的 -步或向前的 -步。若相鄰兩步類型相同,就在它們之間重複中間的頂點,並利用另一個關係的自反性,以該關係標記這個平凡的新步。若路徑以 -步開始,就在前面重複第一個頂點並標記為 ;若以 -步結束,就在末端重複最後一個頂點並標記為 。新路徑端點不變,並按 交替,所以長度是偶數。長度零的路徑就是 的情況。
第 3 部分。 在定義中取 或 ,由 與 的自反性得 ;特別地, 是自反的。由於 與 都等於自身的逆,。若 是等價關係,它便對稱,所以 。
反過來,設 。此時 等於自身的逆,所以對稱。 的自反性與傳遞性給出 ,同理 。由結合律,
這特別給出傳遞性。所以 是包含 的等價關係,因而包含 。 中每個有序對都由一條兩步的 -路徑連接,所以 。
例題 1.4.10
(同餘關係總是可交換)
對正整數 ,以 表示 上的模 同餘。設 為正整數。若 且 ,則 。反過來,若 ,令 ,則 且 。因此
這個描述對 與 是對稱的,所以兩個關係可交換。由 Bézout 恆等式,,其中 是最大公因數,所以兩者的合是 。由於 ,其中 是最小公倍數,兩者的交是 。
取 、,合就是奇偶性,交就是模 同餘。由於 ,比較定理給出從模 的四個類到兩個奇偶類的滿射。關係 有兩塊 與 ,正好對應 。
例題詳解
有序對列表會迫使更大的類出現
例題 1.4.11
(三個描述成為一個等價類)
令 ,四個標籤互不相同,且 。 內任意兩點之間都有路徑;但沒有路徑能把 連接到其他頂點,因為沒有容許的邊接觸 。所以 的塊是 與 。關係包含第一塊內全部九個有序對,以及 這一個有序對。
上的函數能下降到這個商集,當且僅當 ;在 處的值沒有約束。只檢查 會漏掉另一個指定認同;容許 則違反傳遞性迫使成立的認同。
兩個等價關係的並未必是等價關係
反例模式
兩個等價關係的並
聲稱:集合上兩個等價關係的並仍是等價關係。在 上,令 的塊為 , 的塊為 。它們的並使 與 相關、 與 相關,卻沒有使 與 相關,因此不傳遞。包含二者的最小等價關係是 ;本例中它只有一塊,就是整個集合。
相比之下, 就是這個集合上的相等關係。交集保留等價關係公理,聯集一般需要再取有限路徑閉包。
忘掉正負號後,像集仍須準確描述
例題 1.4.12
(按平方相等對整數取商)
定義 為 。由 得到 ,所以 或 。核的類是 ,以及每個正整數 對應的 。誘導映射把每個類送到其共同的平方。
它是到 的雙射,卻不是到整個 的滿射;例如 不是平方數。按輸出相等取商,恰好消除了不單射的問題,卻不會擴大值域。如果改為按奇偶性認同整數,平方規則就不能下降為取值在整數中的函數,因為 與 同奇偶,但平方不同。
運算也有相容性條件
例題 1.4.13
(類之間的變換不必保持代表元相等)
令 是 上「奇偶性相同」的關係。映射 能誘導 ,當且僅當 蘊含 。這裏不要求同一類上的輸出逐字相等,只要求它們仍屬於同一個目標類。
若 ,偶數差 在應用 後仍為偶數,所以誘導映射交換兩個類。相反, 不滿足條件:,但 與 的奇偶性不同。即使商集只有兩個點,一個看起來合理的代表元公式也可能無效。
常見錯誤
常見錯誤
(等價類既不是 的元素,也不是它的代表元)
等價類是 的子集,也是 的元素;它通常不是 的元素。類也不等於它的某個代表元:不同代表元可以給出完全相同的類。
常見錯誤
(最小不是最大)
最小性與最大性的包含方向不同。 包含所要求的有序對,卻包含於每一個含有這些有序對的等價關係。它不是最大的這種關係;最大的關係是 。
常見錯誤
(輸出相等與輸出類相等)
取值在 中的函數要下降到以 為目標的函數,必須在每個類上有相等的輸出。取值在另一個商集中的函數,則需要輸出的類相等。最後的例題說明這兩個條件不能互換。
快速檢查
快速檢查
(當 及 時, 與 分別是甚麼?)
分開處理 非空與 的情形。
解答 · 答案
若 ,就只能有長度零的路徑,所以 是相等關係,沒有不同點被認同。若 且 非空,任意兩點都可一步相連,商集只有一個點。若 ,商集則為空。這些邊界情形同時檢驗了路徑長度約定與分劃中塊非空的約定。
練習
快速檢查
(生成的塊)
令 ,。求 ,並證明不會被迫產生其他認同。
解答 · 答案
所求塊為 與 。在 內,路徑 反向經過第二個指定有序對,因此任意兩點連通; 中兩點直接連通。「屬於 中同一塊」是包含 的等價關係,故由最小性,不會產生跨越兩塊的路徑認同。因此 。
快速檢查
(對序關係取閉包)
在 上令 為通常的 關係。求 ,並解釋為何這個構造沒有保留原有序資訊。
解答 · 答案
對任意 ,總有 或 ,所以兩點有長度一的路徑。於是 ,商集為 。取等價閉包時,每個生成關係都被容許反向使用。它記錄認同所迫使的相等關係,因此不能保留真正序關係中的方向與區別。
快速檢查
(商集的子集)
設 是 上的等價關係。證明 的子集與那些由 -類的並構成的子集 一一對應,並以特徵函數 解釋這一對應。
解答 · 答案
把 送到 ,所得顯然是類的並。反過來,對類的並 ,取 。每個類非空,而不同類不交,所以一個包含於 的類必屬於 。兩個構造因此互為逆,包括空集情形。特徵函數 在每個類上為常數,當且僅當是否屬於 在每個類上保持不變,也就是 為類的並。分解定理把它與 中對應子集的特徵函數聯繫起來。
快速檢查
(限制到子集)
設 , 是 上的等價關係。把 限制到 ,證明 定義單射 。它何時是滿射?
解答 · 答案
這裏 ,且 。若兩個代表元給出相同的限制類,它們便 -相關,因此給出相同的完整類,證明映射良定義。若完整類相同,這兩個屬於 的點就在限制關係下相關,所以限制類相同,證明單射。其像恰好是與 相交的完整類,因此滿射的充要條件是 與每個 -類相交。構造此映射毋須同時選取代表元。
快速檢查
(投影的右逆)
證明投影 有右逆,當且僅當存在 的子集,恰好與每個 -類相交於一點。說明商集分解定理的哪一步避免了這項額外要求。
解答 · 答案
若 滿足 ,則 。其值域與每個類相交,而為不同類選出的值不可能落入 ,所以交點唯一。反過來,若 與每個類恰交於一點,則「 當且僅當 」由唯一存在定義函數,並滿足 。 為空時, 均取空集,結論也成立。分解證明使用的是:所有代表元在 中本來已有同一個輸出,因此每個類有唯一輸出;它不需要從類本身選出一點。這個關於給定商集的等價命題,沒有斷言 ZF 中每個商映射都有右逆。
快速檢查
(誘導運算)
對二元運算 ,證明公式 良定義,當且僅當 與 蘊含 。若 滿足結合律,證明誘導運算也滿足結合律。
解答 · 答案
必要性來自 、:良定義的運算必須給出相同的結果類。充分性來自所給蘊含保證輸出類與兩個代表元都無關。每對類有唯一輸出類,以分離便能定義圖像,毋須同時選擇代表元。若 結合,則對任意代表元 ,兩種加括號方式分別由 與 代表,而兩者在 中相等,所以其類相等。每三個類可由商集定義局部取得代表元;這個證明只用了有限次存在見證。
快速檢查
(不可交換的複合)
在 (三個標記互不相同)上,如前述關於並的反例,令 的塊為 , 的塊為 。計算 與 ,證明兩者都不是等價關係,並求 。
解答 · 答案
有序對 屬於 ,當且僅當有某個 使 且 。從 出發,唯一的 是 ,所以 。從 或 出發,可取 ,所以 可以是 中任何一個。因此 由除 以外的全部九個有序對組成;它的逆 由除 以外的全部有序對組成。兩者都不對稱,這正是定理第 3 部分對不可交換關係的預測。交替鏈 連接 與 ,所以 ,只有一塊。
快速檢查
(加細的三種說法)
設 與 是 上的等價關係。證明以下三者等價:(i) ;(ii) 每個 -類都包含於某個 -類;(iii) 每個 -類都是若干 -類的聯集。
解答 · 答案
(i)⇒(ii):若 ,則 ,所以 。(ii)⇒(i):若 ,設 是包含 的 -類。則 ,又因各類分劃 ,,所以 。(ii)⇒(iii):對 -類 及 , 的 -類包含於唯一含 的 -類,即 。所以 。(iii)⇒(ii): 的 -類是若干 -類的聯集,其中一個含 ;同樣因為各類分劃 ,這個類必定是 。因此 。
總結
有限的可逆路徑恰好構造出由指定認同所迫使的等價關係,其等價類分劃了原集合。函數能經過商集分解,恰好要求它在各類上的輸出為常數;按函數的整個核取商,便得到到像集的雙射。證明一直使用集合界限和唯一輸出,而從每個類選取一個代表元是另一項問題。