集合上的全序是一种满足自反性、反对称性和传递性,且任意两个元素都可比较的二元关系。它将对象沿一条直线排列的直观想法形式化:任意两个对象,要么一个排在另一个之前,要么两者相等。配备全序的集合称为全序集或线性序集。全序是偏序的特殊情形,其特点是不存在不可比较的元素对。
定义
设 为集合, 为 上的关系。如果对所有 ,以下条件均成立,则称 为全序集:
- 自反性:。
- **反对称性:**若 且 ,则 。
- **传递性:**若 且 ,则 。
- 完全性,也称可比性或连通性: 或 。
前三个条件定义了偏序。完全性进一步要求任意两个元素都可比较。如果完全性的陈述涵盖所有元素对,包括 的情形,那么它本身就蕴含自反性;不过,列出这四个条件可以明确体现全序与偏序之间的关系。
序是结构的一部分,而不只是底层集合本身的性质。同一个集合上可以定义许多不同的全序。
严格序形式
全序也可以等价地用严格关系 表示,其定义为
这一严格关系具有传递性,并满足三歧性:下列三个关系中恰有一个成立:
特别地,它具有非自反性,即 永不成立。
反过来,满足三歧性的传递严格关系可以通过下式确定一个非严格全序:
定义时必须区分这两种约定:反对称性是非严格关系的性质,而非对称性——即 蕴含 不成立——则是严格关系的性质。
例与反例
自然数、整数、有理数和实数上通常使用的数值大小关系都是全序。将关系限制在任一子集的元素上,该子集就继承了一个全序。
其他构造表明,全序不一定与数值有关:
- **有限列表。**将互不相同的元素排列为 ,便可定义一个序,使 当且仅当 。
- **逆序。**给定全序 ,规定当 时 ,即可得到另一个全序。
- **字典序。**比较有序对时,可以先比较第一坐标;如果第一坐标相同,再比较第二坐标。这就是字典序。
- **空集与单元素集。**两者都可以配备全序。在空集上,各条公理均为空真。
许多自然出现的关系并不是全序。集合 的幂集上的包含关系是偏序,但 与 均不成立。正整数上的整除关系也只是偏序,而不是全序: 不能整除 , 也不能整除 。
复数作为集合可以配备全序,例如,按实部和虚部的字典序排列即可。然而,不存在与复数通常的加法和乘法相容、使其成为有序域的全序。在有序域中,每个非零元素的平方都为正,这与 相矛盾。
序的结构与比较
最小元、最大元、极小元与极大元
若元素 满足 ,且对每个 都有 ,则称 为子集 的最小元。最大元的定义与之对偶。
在偏序中,极小元只需满足子集中没有严格小于它的元素,而不必与其他所有元素都可比较。在全序中,可比性消除了这一区别:每个极小元都是最小元,每个极大元都是最大元。
每个非空有限全序集都有唯一的最小元和唯一的最大元。无限全序集则可能两者都没有。整数集既没有最小元,也没有最大元;自然数集有最小元,但没有最大元。
全序集中任意两个元素的最小值和最大值都存在。但这并不意味着任意无限子集都有最小值、最大值或最小上界。
序同构与序型
若存在双射函数 ,使得
则称两个全序集 和 序同构。
这是它们的序结构之间的同构。元素具体叫什么并不重要,重要的只是它们的相对位置。由此得到的结构模式称为序型。
元素个数相同的有限全序集都彼此序同构。无限集的情形则不同。自然数集与整数集的基数相等,但在通常的序下并不序同构,因为前者有最小元,而后者没有。
链与线性扩张
偏序集中的链是一个子集,其继承的序为全序。整个偏序集本身不一定是链。
偏序的线性扩张是同一集合上的一个全序,它保留原有的所有比较关系。序扩张定理,也称施皮尔莱因扩张定理,断言每个偏序都有线性扩张。该定理在通常采用的、包含选择公理的策梅洛—弗兰克尔集合论框架中成立;其不加限制的一般形式无法仅在策梅洛—弗兰克尔集合论中证明。
对于有限偏序,可以反复选取剩余元素中的一个极小元,从而得到线性扩张。用图论的语言来说,这相当于将有限有向无环图的顶点排列成一个与其边的方向一致的次序。
良序、稠密性与完备性
完全性决定元素之间是否可比较,但对于间隙、端点或无限子集,它所提供的信息很少。
良序
良序是每个非空子集都有最小元的全序。自然数上通常的序是良序,整数上通常的序则不是。
每个良序的序型都对应唯一的序数。通过格奥尔格·康托尔在十九世纪后期的工作,这些思想成为无限集研究的核心内容。
良序定理断言每个集合都可以赋予良序,这一定理与选择公理等价。一个集合可以赋予某种良序,并不意味着它上面某个熟悉的序就是良序。例如,实数集在通常的序下并不是良序集。
稠密序
如果每当 时,都存在元素 使得
则称一个全序是稠密的。
有理数和实数上通常的序都是稠密的;整数上通常的序则不是,因为 与 之间不存在严格介于两者之间的整数。
一个经典的分类定理指出,每个既无最小元也无最大元的可数无限稠密全序集,都与通常序下的有理数集序同构。仅凭稠密性并不能刻画实数。
戴德金完备性
从最小上界的意义来说,如果一个全序集中每个有上界的非空子集都在该全序集中有最小上界,就称该全序是戴德金完备的。
实数具有这一性质。有理数则不具有:集合
在 中非空且有上界,但没有有理数最小上界。
序完备性与度量完备性不同。前者涉及界与序,后者涉及柯西序列相对于某个度量的收敛性。在通常的实数系中,两者密切相关,但对于任意结构,不能将它们当作可互换的定义。
序拓扑
全序决定了一种自然的拓扑,称为序拓扑。它由如下形式的开射线生成:
这些开射线的有限交包括开区间
实数上的序拓扑就是其通常的拓扑。整数上的序拓扑是离散的:每个单元素集都是开集,因为
每个配备序拓扑的线性序集都是豪斯多夫空间。不过,序结构与拓扑结构所保留的信息并不相同。例如,彼此不同构的序可以诱导出同胚的拓扑空间。
应用及相关的比较关系
全序是排序、有序索引、范围查询和搜索过程的基础。一致的比较规则使算法能够将数据排列成线性序列。字典序将这一原理推广到包含多个字段的记录。
只依据一种属性进行比较,可能使不同对象并列。例如,仅按身高比较人时,两个不同的人可能处于同一位置。由此得到的非严格关系可能是全预序:它具有自反性、传递性和完全性,但不一定具有反对称性。
对于全预序 ,定义
这是一个等价关系,由此得到的等价类上带有一个诱导的全序。另一种做法是加入一个唯一的、用于打破并列的排序键,从而在原有对象上得到全序。
编程中的比较规则需要格外谨慎。排序程序要求的可能是严格弱序而非全序,允许不同对象在排序意义下等价。当包含 NaN 时,浮点运算中的标准数值比较也无法为所有浮点值提供全序:涉及 NaN 的比较不满足三歧性。可以另行规定一种全序约定来处理这类值。
在排名和偏好模型中,完全性是一项实质性假设,而不是一致性的必然结果。它要求任意两个对象都可比较,即使现有信息只能支持偏序。