良序定理断言,每个集合都可以赋予一种次序,使其每个非空子集都有最小元。这是集合论的一项基本结果,将任意集合的排序与序数和基数理论联系起来。在不含选择公理的策梅洛—弗兰克尔集合论(通常简称 ZF)中,它与选择公理等价。该定理断言的是某种合适次序的存在性;它既不声称集合上通常使用的次序已经是良序,也不提供选取良序的典范方法。
陈述与定义
集合 上的**良序**是一个严格全序 ,使得每个非空子集 都有最小元。严格全序具有反自反性和传递性,且任意两个不同元素都可比较。此外要求存在最小元,即
因此,良序定理可以写成
序关系本身也是需要给出的内容。定理并不要求这一关系与 上已有的任何次序、代数结构或拓扑相容。
空集自然满足良序的条件。每个有限集都可以良序化,而且无需选择公理,就能在 ZF 中证明这一点。该定理的力量在于它对任意无限集作出的断言。
“良序原理”这一名称有时也用于一个范围小得多的命题:自然数的每个非空子集都有最小元。这一算术原理应与每个集合都可以良序化的断言区分开来。
例与反例
自然数上的通常次序
是良序。相比之下,整数上的通常次序不是良序,因为全体整数组成的集合没有最小元。不过,可以将整数排列为
从而使其成为良序。在这一排列中,每个整数都处于某个有限的位置,因此每个非空子集都有一个最先出现的元素。
同样,有理数上的通常次序不是良序,但通过枚举有理数就能为其赋予良序。更一般地,任何给定了到自然数集的单射的集合,都可以通过该单射继承一个良序。因此,单个可数集的良序化并不需要完整的选择公理。
实数提供了一个更为实质性的例子。实数上的通常次序不是良序:例如,区间 没有最小元。定理断言,存在某种其他次序,使实数集成为良序集。这种次序不一定与实数的通常次序或拓扑有任何有用的联系。
可良序化也不意味着可数。一个良序中的某些元素可以有无穷多个前驱,其各个位置也不一定能用自然数来编号。
与选择公理的等价性
选择公理断言,对于每个由非空集合组成的指标族 ,都存在一个函数 ,满足
在 ZF 中,这一断言与良序定理可以相互推出。
从良序定理推出选择公理
设 是一族非空集合。由良序定理,并集
具有一个良序 。定义
每个 都非空,因此其最小元存在且唯一。这样得到的函数便从这族集合中的每个集合里选出了一个元素。
这一推导说明了良序的一项核心用途:一旦集合被赋予良序,就可以毫无歧义地从其任意非空子集中选出一个元素。
从选择公理推出良序定理
假设选择公理成立,并固定一个集合 。于是,在 的所有非空子集所组成的集合上,存在一个选择函数 ,满足
构造的思路是反复选取此前尚未选过的元素。沿自然数进行的普通递归未必能穷尽 ,因此这一构造要使用超限递归,沿序数阶段逐步进行。
哈托格斯定理为构造何时必须停止提供了严格的界限。该定理可在 ZF 中证明:对每个集合 ,都存在一个序数 ,使得不存在从它到 的单射。
在每个阶段 ,只要还有未使用的元素,就令
如果这一过程在 以下的每个阶段都选出了一个新元素,那么 就会成为从 到 的单射函数,这与 的定义矛盾。因此,这一过程必定在某个序数阶段 穷尽 。
此时,映射 是从 到 的双射函数。通过这个双射将序数上的次序转移到 ,就得到 上的良序。
这一停止性论证至关重要:仅凭“不断选取尚未使用的元素,直到没有剩余元素”为止这样的非形式化指示,既不足以证明超限构造的合理性,也不足以证明它会终止。
序数与基数
每个良序集都与唯一的序数序同构。这一事实可在 ZF 中证明,并不要求每个集合都可良序化。良序定理进一步断言,每个集合都可以纳入这一序数框架。
因此,每个集合都与某个序数具有相同的基数。在与给定可良序化集合存在双射的所有序数中,有一个最小的序数,称为该集合的初始序数。在 ZFC,即 ZF 加上选择公理的体系中,初始序数为所有基数提供了标准代表。
这里的唯一性指的是序型的唯一性,或给定大小的最小序数的唯一性,而不是原集合上的排序方式唯一。同一个无限集可以具有不同序型的良序。例如,自然数可以按其通常次序排列,得到序型 ;也可以先按通常次序排列正整数,再将 放在最后,得到序型 。
该定理还意味着任意集合的大小都可比较:对于任意集合 和 ,或者存在从 到 的单射,或者存在从 到 的单射。将两个集合都良序化后,比较它们的序数序型即可得到这一结论。在 ZF 中,这一一般性的可比较原理本身也与选择公理等价。
在数学证明中的用途
即使无法给出可数枚举,良序仍能使构造逐个元素地进行。
超限归纳与递归
良序支持超限归纳法:要证明某个性质在每个位置都成立,只需证明,只要该性质在某位置之前的所有位置都成立,它就在该位置成立。这将数学归纳法的模式推广到了自然数之外。
类似地,超限递归允许利用此前构造的对象来定义每个位置上的对象。递归定理本身在 ZF 中即可成立;良序定理则使我们能够在为任意集合选定良序后,沿该集合运用这种方法。
代数中的存在性论证
对于一个向量空间,可以将其向量良序化,并按该次序逐个处理。当且仅当一个向量不属于此前保留向量的线性包时,才保留该向量。在极限阶段,将此前保留的所有向量汇集起来。
得到的向量族线性无关,并且张成整个空间,因此是一个基。这种构造可以证明基的存在,却未必能给出可用于实际计算的描述。
许多此类论证也常用佐恩引理来表述;在 ZF 中,佐恩引理同样与选择公理等价。良序将构造组织成相继的阶段,而佐恩引理则确立适当偏序集中极大对象的存在性。
历史与基础地位
格奥尔格·康托尔在发展超限集合论时,将任意集合都可良序化视为一项基本原则。恩斯特·策梅洛于 1904 年发表了一个明确使用选择原则的证明,并于 1908 年发表了另一个证明。围绕这些论证的讨论,推动了人们对选择公理和集合论公理化基础的关注。
该定理的地位取决于所采用的背景公理:
- 在 ZFC 中,它是一个定理,因为该体系包含选择公理。
- 仅在 ZF 中,它等价于添加选择公理。
- 假设 ZF 是相容的,则在 ZF 中既无法证明该定理,也无法证明其否定。
选择公理的独立性结果由库尔特·哥德尔和保罗·科恩的工作确立。这些结果涉及的是相对于指定公理系统的形式可证明性,而不是良序定义本身存在歧义。
局限与常见误解
存在性不等于给出典范的指定方式。 该定理并未为给定集合指出某个首选的良序。某个特定的集合论模型可能具有可定义的实数良序,但 ZFC 并不保证在每个模型中都存在无需参数即可定义的实数良序。
良序化不等于可数列举。 不可数集可以由某个序数来索引,但无法用自然数枚举。
最小不只是极小。 最小元小于所有其他元素。而偏序中的极小元仅仅是指没有严格小于它的元素。良序要求序关系是全序,并且每个非空子集都有最小元。
该定理适用于集合,并不自动同时适用于整个集合论宇宙。 它断言每个集合都有某个良序。在类理论中,用单个类关系对整个宇宙进行良序化是一项全局选择断言,不应将其与通常的集合层面的定理等同起来。
将实数良序化并不能确立连续统假设。 连续统假设规定了实数集的基数在无限基数中的位置。可良序化将实数集的基数纳入序数框架,却不能确定它究竟是哪一个不可数基数。