動機
有些比較刻劃的是依賴關係,而不是大小。某項任務可能必須先於另一項任務,某個子集可能包含於另一個子集,某個正整數可能整除另一個正整數。兩個對象不必可比較。若把這些關係換成任意的數值順序,就可能掩蓋證明所需要的結構。
偏序恰好保留所需的比較。它支持兩個起初看似無關的問題。這些對象能否排成一個滿足所有依賴關係的序列?如果每個對象上報的總量都包含其下方所有對象的貢獻,能否還原各個對象自身的貢獻?第一個問題引出線性擴張,第二個問題引出莫比烏斯(Möbius)反演。有限的序使這兩個問題都能構造性地解決。
定義
定義 6.1.1
(偏序與區間)
集合 上的偏序是滿足自反性、反對稱性與遞移性的關係 。即 ;若 且 ,則 ;並且 蘊含 。序對 稱為偏序集。當 且 時記作 。若兩個元素中一個不大於另一個,則稱它們可比較。對於 ,區間 定義為 。
本章中所有偏序集都是有限的。極小元沒有嚴格更小的元素;最小元則小於或等於每一個元素。極小元可以有很多個,而最小元若存在則唯一。線性擴張是對所有元素的一個排列,其中每一個嚴格比較都使較小的元素排在前面。它為不可比較的元素選定先後次序,但不改變原關係所斷言的比較。
定義 6.1.2
(關聯函數與卷積)
關聯函數給每一對可比較的 指定一個實數 。定義
單位關聯函數在 時滿足 ,否則取 。zeta 函數為 ,對每一對可比較元素都成立。這些都是以兩個有序端點為變量的函數,不應與單變量數列或解析意義下的 zeta 函數混淆。
定理/命題
定理 6.1.3
(有限偏序集都有線性擴張)
每個有限偏序集都有線性擴張。反覆移除剩餘元素中的一個極小元,並將其列在下一位。在多個極小元之間任意選擇,得到的都是有效的擴張。空偏序集對應空排列。
定理 6.1.4
(有限偏序集上的莫比烏斯反演)
存在唯一的關聯函數 滿足 。它由下式確定:
對任意函數 ,等式
對每個 成立,當且僅當
對每個 成立。
該定理容許出現負值。它的目的是撤銷一次匯總,而不是斷言還原出的貢獻在計數對象。若要得到非負的詮釋,還需要關於具體函數的額外資訊。
證明思路或證明
證明
(逐個移除極小元)
非空有限偏序集必有極小元。從任一元素出發,只要可能就不斷移向一個嚴格更小的元素。由遞移性與反對稱性,沒有元素會重複出現,所以有限性迫使這一下降過程終止。移除這樣的元素,對其餘的偏序集應用歸納法。若某元素嚴格小於另一元素,則當較大者被選為極小元時,較小者不可能仍然在場。因此所得的排列滿足所有比較。
證明
(求 zeta 函數的逆)
卷積滿足結合律。展開 或 ,都得到對 的同一個有限和 。直接代入可知 是其單位元。所列遞推式在各區間上依次確定 :當 時,區間 嚴格小於 。由此立即得到 。
右逆元同樣存在:定義 及
這使得 。再由結合律得
於是同一個函數既是左逆元也是右逆元,任何其他逆元也由同一等式推得與之相等。這一步很關鍵,因為卷積不一定可交換:不應不加說明地把單側的消去用到另一側。
把下集求和的表達式代入 ,得到所提出的反演式,再重新整理:
內層的和是 。反過來,把反演式代入 ,內層的和變為 ,剩下 。每個區間上的和都是有限和,所以不需要任何收斂條件。
證明透視
兩種端點求和各司其職
遞推式固定第一個端點,對可能的第二個端點求和,證明的是其中一個逆元等式。下集反演需要的則是固定第二個端點的那個等式。分別構造兩個單側逆元並利用結合律,就彌合了這一差距。 中端點的順序是定理的一部分,而不是排版上的隨意選擇。
例題詳解
例題 6.1.5
(鏈把累計總量化為差分)
設 。遞推式給出 ,相鄰元素之間為 ,跨越更長區間時為零。例如 ,。因此由累計值 可還原 。負的貢獻與總量從五降到四是相符的。
例題 6.1.6
(子集產生正負交替的符號)
將一個有限集的子集按包含關係排序。對於 ,
事實上,若差集非空且大小為 ,則對中間子集的求和為 ,而差集為空時和為一。若在三元集的子集上取 ,反演給出 。直接看,總量就是每個子集各貢獻一的總和。
例題 6.1.7
(整除關係還原算術莫比烏斯函數的值)
將十二的正因數按整除關係排序。從一到某個因數的區間恰好包含它的所有正因數。遞推式給出 ,,, 以及 。對於最後一個值,把前面的值相加得 ,再取相反數。這與算術莫比烏斯函數一致:十二含有重複的素因子。這裏的取值取決於區間的整除結構,而不是它在數值上的長度。
為甚麼圖示需要其背後的序
Hasse 圖只記錄覆蓋關係:當 且二者之間沒有任何元素時,稱 覆蓋 。自反的環以及由遞移性推出的比較都被省略。因此,一幅帶向上邊的圖所編碼的可比較元素對,可能比可見的邊多得多。關聯函數的卷積對所有中間元素(包括端點)求和,而不是只對圖中的相鄰點求和。
對於四元鏈,其兩端點之間的區間含有四個元素,儘管兩端點之間沒有覆蓋邊相連。反過來,不可比較的頂點之間不存在所述類型的有序區間。若把每一對元素都當作對卷積有貢獻,就會改變代數結構。通常有益的做法是先重建由遞移性推出的比較,再把圖示僅當作參考。
在這套語言裏,極小與最小也有明顯區別。兩個互不可比較的底部頂點可以都是極小元,但二者都不是最小元。有限非空偏序集必有極小元,但不一定有最小元。線性擴張的算法用到的是前一個事實,它恰好足以支持下一步的選擇。若要求每一階段都有最小元,就會錯誤地排除許多有效的偏序集。
移除極小元素的算法給出一條遞推式:對所有可能的第一個元素求和。
自然延伸的下一個問題
一個偏序集有多少個線性擴張?
移除極小元素的算法給出一條遞推式:對所有可能的第一個元素求和。
每個線性擴張都以某個極小元素 開始,其後是 的一個線性擴張;反過來,每一對這樣的選擇都給出一個線性擴張,而不同的第一個元素給出不同的列表。因此 ,且 。鏈只有一個線性擴張, 元反鏈有 個,練習中的菱形偏序集有兩個。這條遞推式可能要經過指數多個子偏序集,而且沒有一條簡單的封閉公式適用於所有偏序集。
反演背後的三角方程組
選定一個線性擴張,並按該次序寫出各下集的總量。每個總量含有自身貢獻(係數為一)以及只出現在列表更前位置的那些貢獻。這個方程組是對角線全為一的三角方程組。解出第一個方程,代入第二個,依此類推。這樣不必先計算關聯函數的逆,就得到了被還原函數的存在性與唯一性。
莫比烏斯公式把這些逐次相減打包成僅由序決定的係數。若在同一個偏序集上給出若干不同的總量函數,可以重複使用同一組係數。更換線性擴張只會改變矩陣的呈現方式,而不改變序關係及其區間遞推式,因此不會改變還原的結果。
概念視角結構
累計求和依賴於一個關係
在鏈上,下集就是初始段,反演就是普通的差分。在子集上,下集指所有被包含的子集,反演使用正負交替的符號。在因數上,下集指所有整數因數,反演使用算術莫比烏斯函數的值。是關係決定了哪些貢獻被匯總;逆屬於該關係本身,而不是某種通用的減法規則。
由上集總量得到容斥原理
還有一個同樣有用的上集形式。若 ,則 。把第一個表達式代入第二個:對 的內層求和是 ,所以只有 的項保留下來。反方向則用另一個逆元等式得到。由於匯總的方向改變了,端點的角色也隨之對調。
對於帶有若干命名性質的有限全集,令 表示恰好具有指標集 所對應性質的對象個數。令 表示具有 中每一個性質的對象個數(可能同時具有其他性質)。則 。在空集處對布爾(Boole)偏序集作反演,就得到不具有任何這些性質的對象的交替交集公式。特別地,空指標的總量是整個全集,而不是零。這解釋了容斥原理中最初的全集項。
常見錯誤
(交集計數不是恰好計數)
「恰好」一詞至關重要。交集計數要求具有所有命名的性質,但並不禁止其他性質。恰好具有某些性質的計數則禁止指標集之外的每一種性質。把這兩類總量混用,會改變所反演的關係,通常會得出錯誤的數字。
計算遵循證明
要列出關聯函數的逆,按區間由小到大的次序處理。先存入對角線上的一。之後每個遞推式所用的項,都已在嚴格更小的區間上得到。也可以改用擴張的次序來做三角反演。若輸入的序的 zeta 值為整數,兩種方法都應保持精確的整數運算;由遞推式可知,每個還原出的係數都是整數。
這是一個有限的過程,並不意味著所有偏序集都有廉價的表示。列出每一對可比較元素本身就可能需要二次方量級的條目。由簡潔規則給出的序(例如子集包含)可能有特殊公式,從而避免完整的表。布爾公式之所以有用,正是因為它用一個基數之差表達了整族區間的逆。
常見錯誤
反例模式
按區間長度正負交替並非普遍規則
在鏈 上,端點之間的值為零,儘管兩端點之間有兩個覆蓋步。若賦予符號 ,則得到一,這違反遞推式 。基數公式的正負交替之所以在子集區間上成立,是因為所有中間子集的選擇會產生二項式抵消。它不能移植到任意的 Hasse 圖上。
常見錯誤
(線性擴張不增加任何比較)
線性擴張也不會使原本不可比較的對象在原偏序中變得可比較。它給出的是與該關係相容的輔助全序。在構造區間、依賴關係的鄰域或累計和時,應保留原來的關係。
總結
有限偏序容許給出尊重依賴關係的排列。它們的 zeta 函數沿著序匯總各項貢獻,而唯一確定的關聯函數的逆則撤銷這一匯總。普通差分、子集的容斥原理以及算術因數反演,是同一個有限求和證明的三種不同實例。
練習
快速檢查
(在菱形偏序集中計算自底元出發的莫比烏斯值,其中底元為 ,互不可比較的中間元素為 與 ,頂元為 。)
然後由總量 還原這四個貢獻。
解答 · 答案
各值為 ,,以及 。從兩個中間元素到頂元的兩個區間,其值為 。因此在 處的貢獻分別為 ;最後一個是 。把下方的貢獻相加就能重現每一個總量。
快速檢查
(某個對象全集具有兩個性質。全集大小為 ,兩個性質各自的計數分別為 與 ,交集計數為 。請還原全部四個恰好具有某些性質的計數。)
在兩個性質的子集偏序集上使用上集總量。
解答 · 答案
兩個性質同時出現在三個對象上。只有第一個性質的有 個;只有第二個性質的有 個;兩個性質都沒有的有 個。這四個數之和為二十,並且對它們作相應的上集求和可還原九、八與三。反演把交集當作一個包含計數使用,而不是當作另一個需要被減去兩次的互不相交的類別。
快速檢查
(證明:每個具有唯一極小元的有限非空偏序集都有最小元。)
唯一的極小元是比單純選取某一個極小元更強的條件。
解答 · 答案
設 為唯一的極小元,並任取 。有限非空的下集 有一個極小元 。若整個偏序集中有任何元素嚴格小於 ,由遞移性它會落在這個下集中,與 在其中的極小性相矛盾。因此 在全局上是極小的,必定等於 。故 。由於 是任意的, 是最小元。