全序關係,也稱為線性順序(英語: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