全序關係,也稱為線性順序(英語:Total order, linear order)即集合
上的反對稱的、遞移的和完全的二元關係(一般稱其為
)。
若
滿足全序關係,則下列陳述對於
中的所有
和
成立:
- 反對稱性:若
且
則![{\displaystyle a=b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1956b03d1314c7071ac1f45ed7b1e29422dcfcc4)
- 遞移性:若
且
則![{\displaystyle a\leq c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb1c962997d8a303e076777cd6d6bc732f360ac8)
- 完全性:
或![{\displaystyle b\leq a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d38bff9a811bdd9b92516d9c2694712555b99952)
滿足全序關係的集合叫做全序集合、線性序集合、簡單序集合或鏈。
鏈還常用來描述偏序集合的全序子集。
全序關係的完全性可以如下這樣描述:集合中的任何一對元素都是可相互比較的。
注意完全性條件蘊涵了自反性:
,因此全序關係也是(滿足「完全性」條件的)偏序關係。
對於每一(非嚴格)全序關係≤都有一關聯的非對稱的嚴格全序關係<,它可以用以下兩種等價的方式定義:
當且僅當
且![{\displaystyle a\neq b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bf17ce351d08f2b7a3e54ba3aa2132f260c84f6)
當且僅當
(即
為
的逆補關係)
性質:
- 遞移性:
且
蘊涵
。
- 三一性:
,
和
中有且僅有一個成立。
- 弱序性:其中關聯的等價是相等的。
我們可以通過指定
為三分二元關係,用這兩種等階的方式來定義全序
:
當且僅當
或![{\displaystyle a=b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1956b03d1314c7071ac1f45ed7b1e29422dcfcc4)
當且僅當![{\displaystyle \neg (b<a)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61ab509e62d2925b923514db8addb55592bddac4)
另兩個關聯的關係是補關係
和
,它們構成了四元組
。
我們可以用這四個關係中的任何一個來定義全序集,符號指明了全序集的嚴格性。
- 字典序的字母表,比如
等等。
- 全序集的任何保持原次序不變的子集。
- 滿足完全性的偏序集。
- 基數或序數集(嚴格地說,它們都是良序集)。
- 若
為任何集合,
為
到一全序集的單射,則
誘導
為
當且僅當
的全序集。
- 有序數的全序集的直積的字典序是全序的,例如按字典序排序的任何單詞表——長為
的單詞可視為字母表集合的直積自乘
次所得結果集合中的元素。
- 擁有小於(
)和大於關係(
)的實數集是全序的,因此其子集(自然數集、整數集、有理數集等)均為全序集。
- 自然數集是最小的無上界全序集。
- 整數集是最小的無界全序集。
- 有理數集是最小的無界稠密全序集。
- 實數集是最小的無界連通全序集。
- 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