全序关系,也称为线性顺序(英語:Total order, linear order)即集合
上的反对称的、传递的和完全的二元关系(一般称其为
)。
若
满足全序关系,则下列陈述对于
中的所有
和
成立:
- 反对称性:若
且
则![{\displaystyle a=b}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1956b03d1314c7071ac1f45ed7b1e29422dcfcc4)
- 传递性:若
且
则![{\displaystyle a\leq c}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/fb1c962997d8a303e076777cd6d6bc732f360ac8)
- 完全性:
或![{\displaystyle b\leq a}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/d38bff9a811bdd9b92516d9c2694712555b99952)
满足全序关系的集合叫做全序集合、线性序集合、简单序集合或链。
链还常用来描述偏序集合的全序子集。
全序关系的完全性可以如下这样描述:集合中的任何一对元素都是可相互比较的。
注意完全性条件蕴涵了自反性:
,因此全序关系也是(满足“完全性”条件的)偏序关系。
对于每一(非严格)全序关系≤都有一关联的非对称的严格全序关系<,它可以用以下两种等价的方式定义:
当且仅当
且![{\displaystyle a\neq b}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3bf17ce351d08f2b7a3e54ba3aa2132f260c84f6)
当且仅当
(即
为
的逆补关系)
性质:
- 传递性:
且
蕴涵
。
- 三分性:
,
和
中有且仅有一个成立。
- 弱序性:其中关联的等价是相等的。
我们可以通过指定
为三分二元关系,用这两种等阶的方式来定义全序
:
当且仅当
或![{\displaystyle a=b}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/1956b03d1314c7071ac1f45ed7b1e29422dcfcc4)
当且仅当![{\displaystyle \neg (b<a)}](https://backend.710302.xyz/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