動機
在計算中,相等往往過於嚴格:兩個整數可以因餘數相同而被視為同一種情況,兩個任務之間也可能只有先後約束。這兩種情況都可以用一條規則描述:指明哪些有序對的元素算作相關。
定義
定義 12.5.1
(二元關係與關係圖)
集合 上的二元關係 是 的子集; 時記為 。有序對的次序不能隨意交換。關係圖以箭嘴表示相關的有序對, 則畫成環。
定義 12.5.2
(自反、對稱、傳遞與反對稱)
若每個 都滿足 ,稱關係自反;若 必然推出 ,稱為對稱;若 與 必然推出 ,稱為傳遞。若 與 同時成立必然推出 ,稱為反對稱。反對稱並不要求任意兩個元素一定有一個方向的箭嘴:它們可以不可比較。這些條件都是全稱命題,一個反例即可推翻;在空集上四者都因沒有反例而成立。
常見錯誤
(反對稱不等於不對稱)
反對稱只限制兩個不同元素:它們不可在兩個方向上都相關,並沒有禁止對稱。任何集合上的相等關係既對稱又反對稱, 上的關係 亦然。若有 與 ,這一對符合對稱,卻違反反對稱,因為 。
等價關係與劃分
定義 12.5.3
(等價關係、等價類與劃分)
自反、對稱且傳遞的關係稱為等價關係。 的等價類定義為 。 的一個劃分是若干非空、兩兩不交的子集,其聯集為 ;空族是空集的劃分。
定理 12.5.4
(等價類恰好構成劃分)
等價關係的不同等價類構成 的劃分。反過來,規定兩個元素當且僅當屬於同一個劃分塊時相關,得到一個等價關係。
證明
(等價類覆蓋 ,且相交的類相同)
由自反性,,因此等價類非空且覆蓋 。若 ,則 且 。對稱性給出 ,再由傳遞性得 。對任意 ,由 和 得 ;交換 的角色便得兩個類相等。所以相交的類必定相同。反過來,同屬一個塊顯然自反、對稱;若 同屬一個塊而 同屬另一個塊,由塊兩兩不交可知這兩個塊相同,傳遞性隨之成立。
證明透視
一個公共元素為何足夠?
不顯眼的一步,是把公共元素 當作連接 與 的橋。對稱性把 變成 ,傳遞性把 與 合成 ;同一模式說明每個類都含於另一個類,所以論證以相等作結。自反性只在開頭使用,用來保證類非空並覆蓋 。對稱性不能省略:在 上,關係 自反且傳遞,而 、,這兩個類相交卻不相等。
定義 12.5.5
(商集與代表元)
所有不同等價類組成商集 。代表元只是類的一個名稱,並非唯一選擇。若想透過選代表元定義類上的運算,必須證明更換代表元不會改變所得的類。
例題 12.5.6
(餘數及良定義運算)
給定整數 ,令 表示 整除 。 整除零,且整除性對取負和加法封閉,所以這是等價關係。共有 個類,可用 代表。定義 。若 且 ,則 整除 ,故 ;結果與代表元的選擇無關。
反例模式
依賴代表元的規則
在模 的整數類上,試圖定義整數值函數 並不良定義:,但規則分別給出 和 。使用代表元寫出的公式不一定定義了商集上的函數。
偏序與依賴關係
定義 12.5.7
(偏序、最小元素與極小元素)
偏序 是自反、反對稱且傳遞的關係; 稱為偏序集。例如,包含關係給固定集合的子集定義偏序,整除關係給正整數定義偏序。最小元素位於每個元素之下;極小元素下方沒有不同於它的元素。最小元素若存在則唯一且極小,但可以存在多個極小元素而沒有最小元素。
定義 12.5.8
(嚴格序、覆蓋關係與 Hasse 圖)
當 且 時記為 。對有限偏序集,畫 Hasse 圖時省略自環及由傳遞性得到的邊:當 且不存在 的 時,在 和 之間畫向上的邊。每個嚴格比較都可由向上走邊恢復:若不是覆蓋關係,就插入中間元素並重複;有限性保證過程終止。因此圖是關係的緊湊表示,並非所有相關對的完整列表。
常見錯誤
(把 Hasse 圖當作整個關係)
圖中省略自環,也省略所有由傳遞性得到的相關對。在 的整除關係中, 成立,但 與 之間沒有邊;要恢復這個比較,須沿向上的邊經過中間元素。反過來,圖中的邊只記錄覆蓋關係,所以沒有直接的邊,並不表示兩個元素不可比較。
定理 12.5.9
(有限偏序都有線性擴張)
每個有限偏序集都有一個排列 ,使得 蘊含 。 時空排列滿足要求。
證明
(逐次刪去極小元素)
若非空有限偏序集沒有極小元素,不斷選擇嚴格更小的元素,最終必會重複。由傳遞性得到嚴格環,與反對稱性矛盾。選一個極小元素放在首位,刪去它,再對剩餘元素誘導的偏序重複此過程。被刪元素不可能有尚未列出的嚴格前驅,因此最終排列尊重所有嚴格比較。這就是安排有先後約束任務的原理。有限有向無環圖可反覆刪除入度為零的頂點來排序;可達關係(包括長度為零的路徑)是偏序。用鄰接表和維護的入度,每個頂點和邊只處理常數次,時間為 。
證明透視
有限性與反對稱用在哪裏
每個階段都需要一個極小元素,假設就在這裏被使用。在有限偏序集中,不斷選取嚴格更小的元素,必定會重複出現某個元素;傳遞性把重複變成 ,而反對稱性禁止這種情況。有限性不能刪去: 配上通常的順序就沒有極小元素。列表之所以正確,是因為每個被列出的元素在當時餘下的元素中都是極小的,所以它的每個嚴格前驅都已較早列出。對元素個數作歸納便完成論證。
例題 12.5.10
(極小不等於最小)
在 上按整除關係排序。 和 都是極小元素;二者不可比較,因此沒有最小元素。覆蓋關係為 、 和 。 與 都是線性擴張。雖然 Hasse 圖不畫 到 的邊, 仍屬於該關係。
尊重劃分的函數
商集適用於某個問題不關心同一類內部區別的情況。令 把 送到 ,又設 。我們希望透過 在類上計算 。這要求 在每個類上為常數:只要 ,就有 。不同類的輸出可以相同;條件並不要求它們不同。
定理 12.5.11
(因子分解的判據)
存在函數 使 ,當且僅當 蘊含 。存在時, 唯一。
證明
(在類上為常數,是必要且充分的)
若分解存在,相關元素屬於同一類,故 。反過來,若 在類上為常數,對每個類 選 並令 。類非空,而假設保證這個值與選擇無關。於是 。由於商集的每個元素都形如 ,等式決定了 的每個值,故其唯一。 時,商集為空,空定義域上的函數同樣滿足結論。
常見錯誤
(把因子分解判據讀反)
判據要求相關的輸入有相同的輸出,並不要求不相關的輸入有不同的輸出:常數函數在每個類上都是常數,所以對任何商集都可分解。通過 分解也不表示 決定了等價類;只有在類上的誘導映射為單射時才是這樣。
例題 12.5.12
(按長度歸類字串)
令 為所有有限二進制字串,包括空字串 ;令 表示 。長度相等構成等價關係,每個類含一種長度的全部字串,長度零的類為 。函數 在每類上為常數,因而可寫成 。但 若表示其中 的個數,就不能透過這個商集分解:,但 而 。商集丟掉的資訊可能恰好是另一個任務所需的。
定義 12.5.13
(核關係)
任何函數 自身也定義一個關係,稱為核關係 : 當且僅當 。
定理 12.5.14
(函數經由核關係雙射分解)
核關係是 上的等價關係,其類是所有非空纖維 。誘導映射 ,,是雙射。反過來, 上每個等價關係 都是商映射 的核關係。
證明
(纖維即等價類,每個關係都是核關係)
輸出相等具有自反、對稱和傳遞性, 的類就是纖維 。由因子分解判據,映射 是良定義的,因為相關的輸入有相同的輸出。按像的定義它是到 的滿射;又因為 恰好表示 ,即 ,所以它是單射。 未取到的陪域元素不會產生空類;定義域為空時,像和商集都為空,雙射仍然成立。反過來, 表示 ,由劃分定理,這恰好等價於 。
概念視角結構
把等價關係看作標籤
核關係的結論給出同一個對象的第二種描述。關係 是關於有序對的規則;商映射 則給每個元素貼上所屬類的標籤,而 恰是「標籤相同」這個關係。用這種語言,「 尊重 」就是 只通過標籤 依賴 ,這正是因子分解判據的直接讀法。
這也說明類上的運算為甚麼需要相容性證明。若 是 上的二元運算,要定義 ,恰需對所有代表元選擇, 且 蘊含 。只檢查幾個方便的代表元不夠。上面的模加法證明驗證了該條件,下面關於餘數類乘積的練習對乘法也作了驗證。
構造和讀取依賴偏序
以箭嘴列表給出的關係,可能沒有列出偏序傳遞性要求的全部後果。對有限有向無環圖,定義 表示存在從 到 的有向路徑,允許長度為零。零長路徑保證自反,連接兩條路徑保證傳遞;若不同的 互相可達,兩條路徑會包含有向環,與無環性矛盾,故也反對稱。原始邊不必列出該偏序的所有相關對,但每條原始邊在每個線性擴張中都必須向前。
定理 12.5.15
(拓撲序恰對無環圖存在)
設 是有限有向圖。若 沒有有向環,則可達關係是偏序,其線性擴張恰是使每條邊都向前的排列。若 有有向環,則不存在這樣的排列。反覆刪除入度為零的頂點,要麼列出全部頂點,要麼停在含有有向環的剩餘頂點上。
證明
(邊向前、有環不可能、卡住就有環)
可達偏序的每個線性擴張都是圖的拓撲序;拓撲序也尊重每條路徑,因為路徑上的每條邊都向前。因此兩種說法得到完全相同的排列。若圖有有向環,沿環會迫使起點嚴格排在自己之前,拓撲序不可能存在。對有限圖反覆刪除入度為零的頂點:若未刪完就停下,每個剩餘頂點都有來自剩餘頂點的入邊。沿入邊反向追蹤必然重複頂點,於是得到有向環。這不只是算法找不到答案,還給出了失敗的證據。
例題 12.5.16
(數出合法日程)
設任務 的直接約束只有 在 前、 在 前及 在 前。起初可選 。若先選 ,第二步必須選 ,隨後 任意排序,得到 。若先選 ,接下來可選 :先選 得 ;先選 則餘下次序被迫為 ,得 。因此恰有五個線性擴張。按下一個可選任務分支既不遺漏合法日程,也不會重複計數。孤立任務也是可選項,不是無法完成的任務。
一個線性擴張是與偏序相容的一個全序,並不表示不可比較的任務本來就有固有次序。上例中 的兩種次序都出現; 在每個擴張中都早於 ,因為這是原約束。依賴圖可能有大量合法日程:找一個可用線性時間,但列出所有結果本身可能需要指數大小的輸出。
反例模式
有向環與無向環不同
邊 、、 構成有向無環圖,儘管忽略方向後它是三角形。其唯一線性擴張是 。有向環要求沿箭嘴方向走回起點;單有無向環並不表示依賴約束矛盾。
練習
快速檢查
(在整數上令 表示 是偶數。求等價類,並說明 是等價關係。)
解答 · 答案
自反性成立,因為 是偶數。對稱性成立,因為 為偶數時 也是偶數。傳遞性成立,因為 是兩個偶數之和。等價類是偶整數集和奇整數集。
快速檢查
(在 上令 表示 。自反、對稱、傳遞性哪些成立?)
解答 · 答案
對稱性成立。每個元素都違反自反性。傳遞性不成立,因為 和 成立而 不成立。
快速檢查
(在 上按包含關係排序,求極小元素、最小元素及所有線性擴張。)
解答 · 答案
兩個單元素集合都是極小元素,但沒有最小元素。線性擴張恰有兩個:先以任意次序列出兩個單元素集合,最後列 。
快速檢查
(若 且 (模 ),證明 。)
解答 · 答案
利用 ,右邊兩項都被 整除,所以 。因此乘法在餘數類上也良定義。
快速檢查
(設 ,,且 、。求核類和像。由商集到整個陪域的誘導映射是滿射嗎?)
解答 · 答案
核類是 和 ,像是 。誘導映射到 時漏掉 ,因而不滿射;但它到像的映射是雙射。
快速檢查
(有向圖的邊為 、 和 。求全部拓撲序;若添加邊 會怎樣?)
解答 · 答案
都必須早於 , 必須晚於 ,故拓撲序為 。添加 後產生有向環 ,不存在拓撲序。
快速檢查
(在模 的整數類上, 是否定義了類到類的函數?解釋為何更換代表元不改變結果。)
解答 · 答案
是。若 整除 ,則也整除 。等價輸入得到等價輸出,由因子分解判據得到商集上的唯一函數。