最大與最小元

偏序集中,大(小)於或等於全體元素的特別元素

數學分支序理論中,最大元是某集合中,大於或等於其全體元素的特殊元素。最小元與之對偶英語duality (order theory),小於等於該集合的任何元素。例如,實數集中,最大元是,而最小元是,但是區間並無最大元或最小元。

60的因數,按整除偏序畫成哈斯圖。紅色子集有兩個極大元3、4,和一個極小元1,同時也是最小元。但是,沒有最大元。

此處「大小」關係除一般實數的大小關係外,也可以是定義在任意集合上的偏序預序

嚴格定義

編輯

 偏序集(或預序集亦可), 為其子集。若 的元素 滿足:

 的任意元素 ,皆有 

 稱為 最大元(英語:greatest element)。對偶地,若 的元素 滿足:

 的任意元素 ,皆有 

 稱為 最小元least element)。

由定義, 的最大(小)元必定是 上(下)界。且若 為偏序集,則集合 至多得一個最大元:若  皆為最大,則由定義有 ,又有 ,由反對稱性 。所以若有最大元,則必定唯一。[1]若改為預序集則不一定。

整個偏序集 的最大最小元又稱為top)和bottom)。頂常以符號記作  ,底則是  ,在有補格布爾代數等結構中尤為常見。有頂和底的偏序集稱為有界偏序集合

與極大極小元、上下界之別

編輯

集合不一定有最大元,也不一定有上界。即使集合有上界和上確界,也不一定有最大元。舉例,實數系 中,任何正數皆是負數子集 的上界,且 為其上確界,但是沒有最大元:不存在「最大的負數」。最小元與下界、下確界的關係也類似。最大元又與極大元maximal element)不同:有極大元的集合不一定有最大元,但偏序集若有最大元,則同時亦是唯一的極大元。最小元與極小元minimal element)亦不同。[1]

性質

編輯

 偏序集 為其子集。

  • 有限全序集非空子集必有最大最小元。
  •  若有最大元 ,則 必定是極大元。此時, 衹有這一個極大元:對任意極大元 ,由於 是最大元,必有 ,從而由 極大知 。所以若 有多於一個極大元,則不能有最大元。
  •  滿足升鏈條件,則其子集 有最大元若且唯若其恰有一個極大元。
    • 「僅當」:最大元必然是極大元。
    • 「當」:假設 有唯一極大元 但沒有最大元。因為 不是最大,有  不可比,又 不是極大,所以有某個 滿足   也不可比:若 ,則與 極大矛盾;反之 又推出 ,與  不可比又矛盾。重複以上步驟,可得無窮遞升鏈 (其中每個 皆與 不可比,又非極大),與升鏈條件矛盾。

全序集的最大最小元

編輯

假如 限制到子集 上為全序(如首段附圖的 ),則在 中,最大元與極大元等價:若 為極大,則對任意其他 ,必有  將與 極大矛盾),故 是最大元。

所以,全序集中,最大元與極大元兩個概念重合,有時也稱為最大值maximum),同理最小元與極小元也稱為最小值minimum)。但上述用法與實值函數日語実数値関数論的用法略有出入。[2]研究實值函數時,所謂最大值是函數的值域的最大元,又稱全域最大值、絕對最大值、最大值。[3]而限制到某點鄰域時,對應值域的最大元(等同於極大元)則稱為局域最大值、相對最大值、極大值。[4]最大最小值又合稱最值極值亦同。

集合 的最大最小值分別記作 。在格理論概率論中,為方便運算,會將兩數 之最大最小值(即其組成二元集的最大最小元)簡記作  。換言之:

 [5]
 
例2之哈斯圖
  • 實數集 中,全體整數組成的子集 沒有上界,從而沒有最大元。
  • 如圖所示,在集合 上,定義自反關係 使       。則 皆是集合 的上界,但因為不可比較,沒有最小上界。又 不可比, 沒有最大元。
  • 有理數集 中,平方小於2的數所組成的子集 有上界(如 ),但沒有最大元,也沒有上確界。
  •  中,區間 有上確界 而沒有最大元。但區間 有最大元 ,同時也是上確界。
  •  配備積偏序英語product order[註 1],滿足 (而 任意)的二元組 的集合 沒有上界,也沒有最大元。
  • 但當 配備字典序[註 2] 有上界 ,但仍沒有上確界和最大元。

參見

編輯
  1. ^  定義成  
  2. ^  定義成 或(  )。

參考文獻

編輯
  1. ^ 1.0 1.1 松坂 1968,第90-97頁.
  2. ^ nLabextremum: 1. Idea.條目
  3. ^ Weisstein, Eric W. (編). Global Maximum. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  4. ^ Weisstein, Eric W. (編). Local Maximum. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  5. ^ Billingsley, P. Probability and Measure [概率與測度] Anniversary. Wiley. 2012: 572. ISBN 978-1-118-12237-2 (英語).