把對象歸類,為甚麼還需要證明
設一個程式儲存了許多單詞,而某項操作只需要知道單詞的長度。保留每個字母,就保留了這項操作不會使用的資訊。我們可以把所有長度為三的單詞視為一個對象,把所有長度為四的單詞視為另一個對象,如此類推。但後續操作若要直接作用於這些組,就必須保證:同一組中的任何單詞都給出相同結果。
這裏有兩個不同的問題。第一,提出的規則是否真的把原集合分成互不重疊的組?第二,操作是否尊重這種分組?等價關係回答第一個問題,公式的良定義性回答第二個問題。給對象加上一對方括號,並不能自動解決其中任何一個問題。
關係及其不同性質
定義 1.2.1
(集合上的二元關係)
集合 上的二元關係是一個子集 ,其中 是所有由 中元素組成的有序對的集合。當 時,記作 。關係的常見性質為:
- 自反性:每個 都滿足 ;
- 對稱性:對任意 , 蘊含 ;
- 反對稱性: 與 同時成立時,必有 ;
- 傳遞性:對任意 , 與 蘊含 。
同時具有自反性、對稱性和傳遞性的關係稱為等價關係。
每個性質都有自己的量詞。要否定傳遞性,必須找到三個元素,使前提中的兩個有序對都屬於關係,而結論中的有序對不屬於關係。如果某個必要前提也不成立,那麼僅僅找出一個不屬於關係的有序對,並不能反駁傳遞性。
常見錯誤
(反對稱並非對稱的反面)
對稱性與反對稱性並不是彼此的邏輯否定。相等關係同時具有兩者:等式可以反向書寫,而兩個方向都相等的元素當然是同一元素。整數上的通常大小關係具有反對稱性和傳遞性,卻不具有對稱性。等價關係一般不具有反對稱性,因為它正是為了容許不同元素被視為等價。
例題 1.2.2
(接近不一定能形成分類)
在 上定義 當且僅當 。這個關係自反且對稱,但不傳遞:、 成立, 卻不成立。與 有關係的元素組成 ,與 有關係的元素組成 ;這兩個集合有交集卻不相等。因此,看似表達相似性的規則,未必能把集合劃分為若干類。
等價類與集合劃分
定義 1.2.3
(等價類與商集)
設 是 上的等價關係。元素 的等價類為
商集 是所有不同等價類組成的集合 。它的元素是 的子集,而不是 原來的單個元素。商映射 把 映為 。
的一個劃分,是一族非空、兩兩不交且並集為 的子集。空集的劃分是空族。等價類的代表元是從該類中取出的一個元素;等價類本身是整個子集,並不等於選定的代表元。
定理 1.2.4
(等價關係與集合劃分描述同一種分組)
對於 上的等價關係,有
所有不同等價類構成 的一個劃分。反過來,每個劃分都能定義一個等價關係:兩個元素等價,當且僅當它們屬於同一個塊。這兩個構造互為逆過程。
證明
(由關係得到類,由塊得到關係)
設 。若 ,則 ,結合 ,由傳遞性得到 。所以 。由對稱性得到 ,同理可得反向包含。若 ,由自反性可知 ,於是 。
每個類都非空,因為 ;每個元素也都屬於自己的類。如果兩個類有公共元素 ,則 且 。利用對稱性和傳遞性可得 ,所以這兩個類相等。因此,不同的類兩兩不交,而且覆蓋整個 。
反過來,給定一個劃分,每個元素恰好屬於一個塊。元素與自己屬於同一塊,說明關係自反;同屬一個塊顯然具有對稱性。如果 屬於同一塊, 屬於同一塊,那麼這兩個塊都包含 ,因此必須相等,於是 也屬於同一塊。這就證明了三個等價關係公理。每個元素的等價類恰好是原來的塊,所以兩個構造確實互為逆過程。當 為空時,所有結論都按空集的約定成立。
證明透視
為甚麼一個公共元素就迫使兩個類相等
關鍵不只是每個元素都有所屬的類。給定交集中的一個點,對稱性讓我們轉向其中一個代表元,傳遞性再把它與另一個代表元連接起來。先證明兩個代表元等價,才能進一步證明一個類的每個元素都屬於另一個類。如果沒有傳遞性,前面「接近」的例子中那種相交而不相等的集合就仍然可能出現。
例題 1.2.5
(餘數把無窮多個整數分成有限個類)
固定整數 ,定義 當且僅當 整除 。由於 ,關係具有自反性;把可整除的差取負,得到對稱性;把兩個可整除的差相加,得到傳遞性。
記 的類為 。由帶餘除法,每個整數都有唯一一個位於 的餘數。兩個整數餘數相同,當且僅當它們的差能被 整除。因此,商集 恰有 個元素。例如 ,儘管 是不同整數。每個類都是無限集,但所有類組成的集合是有限集。
常見錯誤
(類是集合,不是它的代表元)
不能由 推出 :因為 ,兩個類是 的同一個子集。類是否相等由關係判定,即 當且僅當 ,而不是比較所選的代表元。選取代表元 也不會令類變小: 是無限集。
合併分類規則時要小心
同一個集合上兩個等價關係的交仍是等價關係。一個元素與自己在兩個關係中都有關係;反向關係在兩者中都成立;兩步關係的傳遞推論也可以分別在兩者中使用。取交的意思是:只有兩個原規則都判定等價,才把對象分到同一類。對整數而言,要求模二餘數相同且模三餘數相同,等價於要求模六餘數相同。
反例模式
等價關係的並集未必是等價關係
聲稱:同一集合上兩個等價關係的並集是等價關係。在 上,第一個劃分的塊為 ,第二個劃分的塊為 。在並集關係中, 經由第一個關係與 有關係, 經由第二個關係與 有關係,但 不屬於任何一個,所以並集關係不傳遞。自反性與對稱性在並集下仍然保持,因為兩者都是逐對檢驗的。修正方法是改用由並集生成的等價關係(見下文),在這個例子中它把三個元素合併為一類。
如果確實需要包含一批指定有序對的最小等價關係,可以這樣構造:當兩個元素能由有限條指定關係連接起來,而且每條關係容許向任一方向經過時,聲明它們等價。容許長度為零的鏈。零步鏈保證自反性,反向經過整條鏈保證對稱性,拼接兩條鏈保證傳遞性。任何包含指定有序對的等價關係,都必須把每條這種鏈的兩個端點判為等價,因此這個構造是最小的。上面的例子中,它把三個元素全部合併。「兩個規則都要滿足」與「任一規則都可用於連接」,產生的是不同分類。
函數、纖維與資訊的流失
函數 給每個 指定唯一一個 。它的像為 。對於 ,它在 上的纖維是 ;這裏的符號表示原像,並不要求存在反函數。像集之外的元素對應空纖維,空纖維不是劃分中的塊。
若 蘊含 ,則稱 為單射;若每個 都有原像,則稱它為滿射。既單又滿的函數稱為雙射。這些定義要求區分定義域、聲明的陪域以及實際的像集。
定理 1.2.6
(每個函數恰好把同一非空纖維內的元素視為等價)
設 ,定義 當且僅當 。這給出一個等價關係,其等價類正是所有非空纖維。函數
是雙射。特別地, 為單射,當且僅當它的每個等價類都是單元素集。
證明
(纖維就是等價類)
自反性、對稱性和傳遞性直接來自 中相等關係的對應性質。按照定義, 所在的類由所有函數值為 的輸入組成,恰好是在 上的纖維。
檢查 是否單射或滿射之前,必須先檢查它是不是一個函數。若 ,則 ,所以 。輸出不依賴代表元的選擇。 中每個元素都形如 ,因此映射是滿射。如果兩個類輸出相同,那麼它們的代表元有相同的 值,因而等價,所以這兩個類相等,證明了單射性。最後,每個纖維都不含兩個不同輸入,恰好等價於 為單射。
例題 1.2.7
(有限映射、它的等價類與陪域)
設 ,,並規定
非空纖維為 。共有三個等價類, 把它們分別對應到 。在 上的纖維為空。因此,誘導到像集的映射是雙射,但原來以 為陪域的函數並不是滿射。各類大小也不相同:不能因為第一個類有兩個元素,就把六個輸入除以二來論證類的總數。
操作甚麼時候能直接作用於類
現在獨立於函數 ,固定 上的一個等價關係 。我們想只保留 ,仍然能夠計算 。這恰好要求:分類時丟掉的資訊不影響 的值。
定理 1.2.8
(代表元無關性的判據)
存在函數 滿足 ,其中 ,當且僅當
若 存在,則它唯一,而且由 給出。
證明
(通過代表元定義函數)
若 且 ,則 ;在兩邊作用 ,就得到 。反過來,設上述蘊含成立。要給一個類指定 值,可以任取一個代表元 ,使用 。其他代表元都與 等價,因此給出相同值。這就定義了一個函數,且有 。對於唯一性,每個類都形如某個 ;任何滿足分解等式的函數都必須把它映到 。證明不需要集合有限這一假設。
例如,字母重排不改變單詞長度,所以長度能定義為字母重排等價類上的函數。它不是單射:ab 與 aa 屬於不同的重排類,但長度都是二。在非空單詞上,「取第一個字母」是一個普通函數,卻不能誘導重排類上的函數,因為 ab 與 ba 等價,而首字母不同。
輸出也是等價類的情形
設 是 上的等價關係, 是一個普通函數。規則
良定義,當且僅當 蘊含 。證明只需把前面的判據應用於函數 。所需的輸出是類,因此必須作為類相等;輸出的代表元只需等價,不必是同一個元素。若要求 ,就比實際需要更強了。
例題 1.2.9
(完整檢驗一個等價類上的算術公式)
設 ,,考慮
這個規則良定義,當且僅當 整除 。對於必要性,取同一個輸入的兩個代表元 。只有當 時,輸出 和 才相等。對於充分性,若 ,則 ;在所給假設下,這個差被 整除。
因此, 是合法規則,因為 。它在 上的輸出分別是 ,所以既不是單射,也不是滿射。規則 則不合法: 表示同一個輸入,卻給出不同的輸出類。只用代表元 列一張有限表,當然可以定義某個函數,但這不能證明所聲稱的公式對所有代表元都成立。
練習
快速檢查
(在 上,當 為偶數時定義 。列出所有等價類,並計算這個關係包含多少個有序對。)
分別計算每個塊內部的有序對,包括對角線上的有序對。
解答 · 答案
等價類為 和 。關係為 ,這裏的並集是不交並集,因此共有 個有序對。如果只數不同元素組成的無序對,就會漏掉對角線上的有序對,並把一個有序對與其逆序對視為同一個對象;這回答的是另一個計數問題。
快速檢查
(證明: 上的一個關係同時是等價關係和偏序,當且僅當它就是 上的相等關係。)
偏序具有自反性、反對稱性和傳遞性。利用等價關係額外具備的對稱性。
解答 · 答案
若 ,由對稱性得 ,再由反對稱性得 。因此 除了相等的有序對之外,不含其他有序對。自反性又保證每個相等的有序對都在 中,所以 。反過來,相等關係具有自反性、對稱性、反對稱性和傳遞性,因此同時具有這兩種結構。論證也適用於 。
快速檢查
(設 的劃分為 、。一個函數把 映到紅色,把 映到藍色。證明它能誘導商集上的函數。若另一個函數只把 映到紅色,其餘輸入都映到藍色,還能誘導嗎?)
對於失敗的規則,給出同一輸入類的兩個代表元,並比較輸出。
解答 · 答案
第一個函數在每個塊上都是常值,因此它誘導的函數把類 映到紅色,把類 映到藍色。代表元無關性判據證明其存在,商映射的滿射性證明其唯一。對於第二個規則,,但提出的輸出分別為紅色和藍色,所以它不能誘導商集上的函數,儘管它在原四元素集合上是一個合法的普通函數。
快速檢查
(求所有使規則 良定義的整數 。當 時,求這個商集映射的像,以及每個非空纖維的大小。)
定義域有六個類,陪域有八個類。先檢查代表元無關性,再計算輸出。
解答
所需條件是 ,等價於 ,也等價於 。最後一個推論可由 以及 得出 。反過來,若 是四的倍數,則 顯然是八的倍數。
當 時,定義域中的偶數類 都映到 ,奇數類 都映到 。因此像有兩個元素,每個非空纖維由三個定義域中的類組成。陪域中其餘六個類的纖維為空。模六的同一個類,其代表元的奇偶性不變,這也與良定義性的證明一致。
快速檢查
(設 、 是 上的等價關係。證明:交關係的等價類恰好是一個 類與一個 類的所有非空交集。說明 為空時的結論。)
先確定一個元素在交關係中的等價類。
解答
令 。它是等價關係,並且對每個 ,
這個交集包含 ,所以非空。反過來,若一個 類 與一個 類 的交非空,取 。由等價類定理, 且 ,所以 。因此這些非空交集恰好給出全部等價類。當 為空時,三個劃分都是空族,也不存在非空交集。
聯繫與邊界
劃分計數筆記研究這裏構造出的塊;自動機把未來行為相同的前綴歸類;強連通分支把能夠互相到達的頂點歸類。每項應用都必須證明自己的等價性和相容性條件。這裏建立的是共同的集合論基礎,不表示已經完整講授自動機最小化、圖算法或代數商結構。