全序關係

全序關係,也稱為線性順序(英語:Total order, linear order)即集合上的反對稱的、傳遞的和完全二元關係(一般稱其為)。

滿足全序關係,則下列陳述對於中的所有成立:

  • 反對稱性:若
  • 傳遞性:若
  • 完全性:

滿足全序關係的集合叫做全序集合線性序集合簡單序集合還常用來描述偏序集合的全序子集。

全序關係的完全性可以如下這樣描述:集合中的任何一對元素都是可相互比較的。

注意完全性條件蘊涵了自反性,因此全序關係也是(滿足「完全性」條件的)偏序關係。

嚴格全序

對於每一(非嚴格)全序關係≤都有一關聯的非對稱的嚴格全序關係<,它可以用以下兩種等價的方式定義:

  •  當且僅當  
  •  當且僅當 (即  補關係)

性質:

  • 傳遞性  蘊涵 
  • 三一性 ,   中有且僅有一個成立。
  • 弱序性:其中關聯的等價是相等的。

我們可以通過指定 為三分二元關係,用這兩種等階的方式來定義全序 

  •  當且僅當  
  •  當且僅當 

另兩個關聯的關係是補關係  ,它們構成了四元組 

我們可以用這四個關係中的任何一個來定義全序集,符號指明了全序集的嚴格性。

例子

  • 字典序的字母表,比如 等等。
  • 全序集的任何保持原次序不變的子集。
  • 滿足完全性的偏序集。
  • 基數序數集(嚴格地說,它們都是良序集)。
  •  為任何集合,  到一全序集的單射,則 誘導  當且僅當 的全序集。
  • 有序數的全序集的直積的字典序是全序的,例如按字典序排序的任何單詞表——長為 的單詞可視為字母表集合的直積自乘 次所得結果集合中的元素。
  • 擁有小於( )和大於關係( )的實數集是全序的,因此其子集(自然數集、整數集、有理數集等)均為全序集。
    • 自然數集是最小的無上界全序集。
    • 整數集是最小的無界全序集。
    • 有理數集是最小的無界稠密全序集。
    • 實數集是最小的無界連通全序集。

參見

引用

  • George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
  • John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4