極小不等於最小
定義 2.3.1
(偏序、極小元素與最小元素)
集合上的偏序 滿足自反性、反對稱性及傳遞性;兩個元素不一定可以比較。對偏序集的子集 ,元素 稱為
- 的極小元素,若不存在與 不同的 滿足 ;
- 的最小元素,若對每個 都有 。
把比較方向反轉,便得到極大元素和最大元素的定義。
定理 2.3.2
(最小元素必為極小,且唯一)
若 有最小元素 ,則 是 的極小元素,而且 是 唯一的最小元素。
證明
(反對稱性迫使兩者相等)
設 滿足 。由於 是最小元素,也有 ,反對稱性便給出 。所以沒有與 不同的元素在它之下, 是極小元素。若 也是最小元素,則 且 ,故 。
極小元素卻未必最小,因為它可能與另一元素不可比較。
定理 2.3.3
(非空有限偏序集必有極小元素)
每個非空有限偏序集都有極小元素。
證明
(嚴格下降的路徑必須停止)
任取一個元素 。若它不是極小,就選 且 ,並照此繼續。由傳遞性, 時 ;反對稱性加上 使任何元素都不會重複出現:若 時 ,則 會迫使 。有限集合中這條路徑必然停止,而它停下的地方就是極小元素。
這並不保證有最小元素。對無限集合,上述結論也可能失效:整數配上通常次序便沒有極小元素。
常見錯誤
(把看似唯一的底部當成最小元素)
有限偏序集可以有多個極小元素,此時它們都不是最小元素。「每個非空有限偏序集都有極小元素」不可加強為「有最小元素」。在 上以整除定序,極小元素是 和 ,而兩者互不整除。
在不違反原有比較下排成全序
定義 2.3.4
(線性延拓)
集合 上偏序 的線性延拓,是 上的一個全序 ,使得對所有 , 蘊含 。
定理 2.3.5
(反覆移除極小元素得到線性延拓)
設 為有限偏序集。反覆從餘下的元素中移除一個極小元素,並按移除次序排列,所得列表就是 的一個線性延拓。反過來,任何線性延拓的首項都是極小元素。
證明
(較大的元素不會比較小的先被移除)
設 且 。當 仍在集合中時, 有一個與它不同而較小的元素 ,所以 不是極小,不能先被移除。因此 先被移除,在列表中排在前面。每一步都可行,因為非空有限偏序集必有極小元素。反過來,設 是某線性延拓的首項。若有 滿足 ,則 必須排在 之前,這不可能,所以 是極小元素。
證明透視
為何以極小性決定下一個元素
證明只依賴一個比較:對 ,「在餘下元素中極小」這個檢驗之所以擋住 ,正是因為 仍然在場。除此之外不需要別的資料,所以程序無需預先觀察,也無需回頭修正。有限性用了兩次:保證每一階段都有極小元素,並保證程序在 步後結束。反對稱性用在極小元素的存在性上,因為沒有它, 這樣的循環可能令極小元素完全消失。逆向敍述說明這個選擇並非方法的產物:每個線性延拓都從一個極小元素開始,移除它之後餘下的部分仍是線性延拓。不同的極小元素選擇會產生不同的延拓,所以結論只是存在性,不是唯一性。
下面的例子把兩個結果用於整除序,其中 表示 。
例題
例題 2.3.6
(整除序中的極小與最小)
在 上,找出所有極小及極大元素,並判斷是否存在最小及最大元素。
只有 和 在 中沒有另一個不同的因數;其餘每個元素均可被 或 整除。因此極小元素是 。由於 且 ,兩者均不是最小元素。每個元素都整除 ,所以 是最大元素,因而也是極大元素。其他元素均為 的不同因數,故不是極大元素。因此唯一極大元素是 ,而最小元素不存在。
例題 2.3.7
(列出所有線性延拓)
在 上以整除定序。列出所有線性延拓並解釋為何沒有遺漏。
整除所有元素,故必排第一;所有元素都整除 ,故 必排最後。中間的 和 不可比較,因此任一個都可以先排。 及 都保留所有整除比較。首尾位置已確定,中間只有兩種排列,所以沒有其他可能。
例題 2.3.8
(反鏈沒有比較需要遵守)
設 ,只有 時才有 。每個元素都既是極小又是極大,沒有最小或最大元素。移除程序可以從三個元素中任一個開始,再從餘下兩個中任選一個,最後是剩下的一個,所以 的 種排列全都是線性延拓。這是偏序完全不施加限制的邊界情形。
反例模式
極小元素可以不唯一,因此未必有最小元素
命題:非空有限偏序集必有最小元素。以整除序檢驗 。 是極小元素,因為 和 都不整除 ; 同理也是極小元素。若 是最小元素,它應整除 ,但並非如此;若 是最小元素,它應整除 ,也並非如此;而 不是最小元素,因為 。所以 沒有最小元素,儘管它有限且非空。補救是改用上面證明的較弱而正確的敍述:必有極小元素;只有當所有元素都在某個共同元素之上時,才有最小元素。
練習
快速檢查
(最小元素是否必為極小?極小元素是否必為最小?)
一個方向用反對稱性;另一個方向用整除序下的 。
解答 · 答案
由反對稱性,最小元素必為極小。反過來不成立:在整除序下, 是 的極小元素,但它不整除 ,所以不是最小元素。
快速檢查
(以整除定序排列 。共有多少個線性延拓?)
先選一個極小元素,再對餘下的元素重複。關係為 、、。
解答 · 答案
共有 個。極小元素是 和 。先取 時,餘下的 須保持 在 之前,得 、、。先取 時,因為 和 都要求 在先,下一個必是 ,之後 可任意排:、。合共 。
快速檢查
(為甚麼配上通常次序的 的每個非空子集都有極小元素,而 沒有?)
比較 本身與 的非空子集。
解答 · 答案
由良序原理, 的每個非空子集都有最小元素,它同時也是極小元素。 本身沒有極小元素,因為對每個整數 , 都嚴格較小。本單元的有限性論證不適用於這兩個集合。