良序是集合上的一种全序,其中每个非空子集都有最小元。配备这种序的集合称为良序集。自然数上的通常序是最基本的例子:每个非空的自然数集合都有最小的成员。良序在集合论中具有基础地位,是序数、超限归纳法以及超越有限阶段的递归构造的基础。
定义
设 是一个集合, 是 上的全序。因此, 具有自反性、反对称性和传递性,且 中任意两个元素都可比较。如果满足以下条件,这个序就是良序:
元素 称为 的最小元。由反对称性可知,最小元是唯一的。
等价地,也可以用对应的严格关系 来描述良序;其定义是:当 且 时,。记号 或 同时指明了底集及其上的序。
空集是良序集,因为它没有非空子集,因而不可能违反上述条件。每个有限全序集也都是良序集。
最小元条件针对的是每个非空子集,而不仅仅是 本身。因此,对于非空良序集而言,存在首元素是必要条件,但不是充分条件。
例子与反例
自然数与整数
自然数在通常序
下构成良序集。它的序型记作 。
整数在通常序下不是良序集,因为全体整数构成的集合没有最小元。不过,同一个底集可以通过以下排列赋予良序:
每个非空子集都有一个在此排列中最先出现的元素。因此,良序是集合连同指定的序所具有的性质,而不是仅由集合中的元素决定的性质。
有理数与实数
有理数和实数在各自的通常序下都不是良序集。例如,正有理数集没有最小元,因为对于任意正有理数 , 都比它小。
即使区间 有最小元,它也不是良序集,因为其子集 没有最小元。这也说明,有下确界并不等同于有最小元。 的下确界是 ,但 不属于这个子集。
排列方式不同的无限序
良序不一定像按自然数编号的普通序列。令
并规定每个自然数都排在 之前。那么
就是一个序型为 的良序。末尾的元素有无穷多个前驱,却没有直接前驱。
另一种良序将所有偶自然数排在所有奇自然数之前,同时在每一组内保留通常序:
它的序型是 ,也写作 。尽管底集相同,它与 上的通常序并不同构。
结构性质
限制与初始段
将良序限制在任意子集上,所得的序仍然是良序。
对于 ,集合
称为由 确定的初始段。更一般地,初始段是向下封闭的子集:只要它包含 ,就包含所有满足 的 。
良序集的每个真初始段都可以写成 的形式,且这样的 唯一。事实上, 就是该初始段之外的最小元。
后继与极限位置
如果元素 不是最大元,那么所有大于 的元素构成的非空集合必有最小元。这个最小元称为 的直接后继。
对于前驱,相应的结论并不成立。在序型为 的序中,末尾的元素没有直接前驱。这类位置引出了后继序数与极限序数的区分。
因此,良序可以有最大元,也可以没有;一个元素可以有前驱,却没有最大的前驱。
比较与刚性
序同构是保持序且其逆映射也保持序的双射函数。任意两个良序集都可以比较:它们要么序同构,要么其中一个与另一个的某个真初始段序同构。
良序还具有刚性。良序集到自身的序同构只有恒等映射。更一般地,若两个良序集序同构,则它们之间的序同构是唯一的。这是因为最小元必须相互对应,接下来剩余元素中的最小元也必须相互对应,如此贯穿整个序。
序数与序型
序数表示良序集的序型。在标准的冯·诺伊曼构造中,序数是一个以属于关系为良序的传递集。每个良序集都与唯一一个序数序同构。
有限序数描述有限良序,而
描述的是彼此不同的无限良序。
序型包含的信息比基数更多。上述三个序的底集都是可数无限集,但其排列方式不同。例如, 有最大元,而 和 没有。
序数算术描述良序上的运算:
- 序数加法将一个良序接在另一个良序之后。
- 序数乘法以另一个良序为指标,将一个良序的各个副本依次排列。
这些运算通常不满足交换律。例如,
在一个无限序列之前放入一个元素,不会改变其序型;在整个序列之后放入一个元素,则会改变序型。
归纳与递归
超限归纳法
良序支持超限归纳法,它推广了通常的数学归纳法。要证明每个 都具有性质 ,只需证明对每个 ,都有
成立。
如果存在反例,那么反例中必有最小元。所有排在它之前的元素都满足 ,因此根据归纳假设,这个最小反例也必须满足 ,从而产生矛盾。
对于序数,证明往往分为初始阶段、后继阶段和极限阶段。这些只是同一个最小反例原理在实际运用中的便利划分。
超限递归
超限递归利用较早位置上已定义的对象,来定义每个位置上的对象。其示意形式为
其中, 是 在 之前各位置上的限制。
在通常的集合论假设下,如果一条规则能为每种可能的先前取值情况指定唯一的值,那么它就能沿着良序确定唯一的函数。这为序数算术的定义,以及沿任意长的良序阶段序列进行的构造提供了依据。
与良基序的关系
良基关系是指其定义域的每个非空子集都有极小元的关系。良序恰好就是良基的严格全序。
对于偏序,最小元与极小元的区别十分重要。最小元小于或等于子集中的每个元素。极小元则只要求该子集中没有严格小于它的元素;它可能与其他元素不可比较。在全序中,这两个概念是一致的。
每个良序都不存在无限严格递降序列
在包含选择公理的标准集合论中,对全序而言,逆命题也成立。如果没有适当的选择原则,不存在这种序列这一条件一般不能与最小元定义互换。采用非空子集来定义良序,可以避免这一基础层面的附加限制。
良序定理与选择公理
良序定理断言,每个集合都可以赋予某种良序。在策梅洛—弗兰克尔集合论中,它与选择公理等价。
其中一个方向是直接的:如果每个集合都可以良序化,那么任何由非空集组成的集合族,其并集也可以良序化;随后便可用一个选择函数,选取该族中每个集合的最小元。
反方向则利用选择公理来证明每个集合都可以良序化。这是一个存在性定理,通常并不给出所得良序的具体描述。
特别地,在假定选择公理成立的情况下,实数可以良序化,尽管人们熟悉的数值大小顺序不是良序。该定理断言的是另一种关系的存在,而不是通常关系 具有某种新的性质。
该定理针对的是每个单独的集合。它本身并不声称存在一个统一的良序,能够将整个集合宇宙良序化。
历史发展与用途
格奥尔格·康托尔于十九世纪后期发展了良序集和超限序数理论。恩斯特·策梅洛在1904年利用一条选择原则证明了良序定理,推动选择公理成为数学基础研究的核心课题之一。
良序为选取最小反例、组织超限构造以及比较序数位置提供了通用框架。它们也用于计算机科学中的终止性论证:如果计算的每一步都使某个取值于良序集的量严格减小,那么计算步骤就不可能无限持续。在不需要任意元素都可比较时,更一般的良基关系也能发挥同样的作用。