aiwiki.page
中文
数学 / 离散数学与逻辑 / well-ordering-theorem

良序定理

良序定理断言每个集合都可赋予良序;在策梅洛—弗兰克尔集合论中,它与选择公理等价。

27 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
集合(数学)集合论策梅洛–弗兰克尔…选择公理良序子集自然数整数良序定理

良序定理断言,每个集合都可以赋予一种次序,使其每个非空子集都有最小元。这是集合论的一项基本结果,将任意集合的排序与序数和基数理论联系起来。在不含选择公理的策梅洛—弗兰克尔集合论(通常简称 ZF)中,它与选择公理等价。该定理断言的是某种合适次序的存在性;它既不声称集合上通常使用的次序已经是良序,也不提供选取良序的典范方法。

陈述与定义

集合 XX 上的**良序**是一个严格全序 ≺\prec,使得每个非空子集 A⊆XA\subseteq X 都有最小元。严格全序具有反自反性和传递性,且任意两个不同元素都可比较。此外要求存在最小元,即

∀A⊆X,A≠∅ ⟹ ∃a∈A ∀b∈A (b=a ∨ a≺b).\forall A\subseteq X,\qquad A\ne\varnothing \ \Longrightarrow\ \exists a\in A\ \forall b\in A\, \bigl(b=a\ \lor\ a\prec b\bigr).

因此,良序定理可以写成

∀X ∃ ≺    (X,≺) is well-ordered.\forall X\ \exists\,\prec\;\; (X,\prec)\text{ is well-ordered}.

序关系本身也是需要给出的内容。定理并不要求这一关系与 XX 上已有的任何次序、代数结构或拓扑相容。

空集自然满足良序的条件。每个有限集都可以良序化,而且无需选择公理,就能在 ZF 中证明这一点。该定理的力量在于它对任意无限集作出的断言。

“良序原理”这一名称有时也用于一个范围小得多的命题:自然数的每个非空子集都有最小元。这一算术原理应与每个集合都可以良序化的断言区分开来。

例与反例

自然数上的通常次序

0<1<2<3<⋯0<1<2<3<\cdots

是良序。相比之下,整数上的通常次序不是良序,因为全体整数组成的集合没有最小元。不过,可以将整数排列为

0≺1≺−1≺2≺−2≺3≺−3≺⋯ .0\prec 1\prec -1\prec 2\prec -2\prec 3\prec -3\prec\cdots.

从而使其成为良序。在这一排列中,每个整数都处于某个有限的位置,因此每个非空子集都有一个最先出现的元素。

同样,有理数上的通常次序不是良序,但通过枚举有理数就能为其赋予良序。更一般地,任何给定了到自然数集的单射的集合,都可以通过该单射继承一个良序。因此,单个可数集的良序化并不需要完整的选择公理。

实数提供了一个更为实质性的例子。实数上的通常次序不是良序:例如,区间 (0,1)(0,1) 没有最小元。定理断言,存在某种其他次序,使实数集成为良序集。这种次序不一定与实数的通常次序或拓扑有任何有用的联系。

可良序化也不意味着可数。一个良序中的某些元素可以有无穷多个前驱,其各个位置也不一定能用自然数来编号。

与选择公理的等价性

选择公理断言,对于每个由非空集合组成的指标族 (Ai)i∈I(A_i)_{i\in I},都存在一个函数 ff,满足

f(i)∈Aifor every i∈I.f(i)\in A_i \qquad\text{for every }i\in I.

在 ZF 中,这一断言与良序定理可以相互推出。

从良序定理推出选择公理

设 (Ai)i∈I(A_i)_{i\in I} 是一族非空集合。由良序定理,并集

U=⋃i∈IAiU=\bigcup_{i\in I}A_i

具有一个良序 ≺\prec。定义

f(i)=the ≺-least element of Ai.f(i)=\text{the \(\prec\)-least element of }A_i.

每个 AiA_i 都非空,因此其最小元存在且唯一。这样得到的函数便从这族集合中的每个集合里选出了一个元素。

这一推导说明了良序的一项核心用途:一旦集合被赋予良序,就可以毫无歧义地从其任意非空子集中选出一个元素。

从选择公理推出良序定理

假设选择公理成立,并固定一个集合 XX。于是,在 XX 的所有非空子集所组成的集合上,存在一个选择函数 cc,满足

c(A)∈A.c(A)\in A.

构造的思路是反复选取此前尚未选过的元素。沿自然数进行的普通递归未必能穷尽 XX,因此这一构造要使用超限递归,沿序数阶段逐步进行。

哈托格斯定理为构造何时必须停止提供了严格的界限。该定理可在 ZF 中证明:对每个集合 XX,都存在一个序数 h(X)h(X),使得不存在从它到 XX 的单射。

在每个阶段 α<h(X)\alpha<h(X),只要还有未使用的元素,就令

xα=c ⁣(X∖{xβ:β<α}).x_\alpha = c\!\left( X\setminus\{x_\beta:\beta<\alpha\} \right).

如果这一过程在 h(X)h(X) 以下的每个阶段都选出了一个新元素,那么 α↦xα\alpha\mapsto x_\alpha 就会成为从 h(X)h(X) 到 XX 的单射函数,这与 h(X)h(X) 的定义矛盾。因此,这一过程必定在某个序数阶段 γ<h(X)\gamma<h(X) 穷尽 XX。

此时,映射 α↦xα\alpha\mapsto x_\alpha 是从 γ\gamma 到 XX 的双射函数。通过这个双射将序数上的次序转移到 XX,就得到 XX 上的良序。

这一停止性论证至关重要:仅凭“不断选取尚未使用的元素,直到没有剩余元素”为止这样的非形式化指示,既不足以证明超限构造的合理性,也不足以证明它会终止。

序数与基数

每个良序集都与唯一的序数序同构。这一事实可在 ZF 中证明,并不要求每个集合都可良序化。良序定理进一步断言,每个集合都可以纳入这一序数框架。

因此,每个集合都与某个序数具有相同的基数。在与给定可良序化集合存在双射的所有序数中,有一个最小的序数,称为该集合的初始序数。在 ZFC,即 ZF 加上选择公理的体系中,初始序数为所有基数提供了标准代表。

这里的唯一性指的是序型的唯一性,或给定大小的最小序数的唯一性,而不是原集合上的排序方式唯一。同一个无限集可以具有不同序型的良序。例如,自然数可以按其通常次序排列,得到序型 ω\omega;也可以先按通常次序排列正整数,再将 00 放在最后,得到序型 ω+1\omega+1。

该定理还意味着任意集合的大小都可比较:对于任意集合 AA 和 BB,或者存在从 AA 到 BB 的单射,或者存在从 BB 到 AA 的单射。将两个集合都良序化后,比较它们的序数序型即可得到这一结论。在 ZF 中,这一一般性的可比较原理本身也与选择公理等价。

在数学证明中的用途

即使无法给出可数枚举,良序仍能使构造逐个元素地进行。

超限归纳与递归

良序支持超限归纳法:要证明某个性质在每个位置都成立,只需证明,只要该性质在某位置之前的所有位置都成立,它就在该位置成立。这将数学归纳法的模式推广到了自然数之外。

类似地,超限递归允许利用此前构造的对象来定义每个位置上的对象。递归定理本身在 ZF 中即可成立;良序定理则使我们能够在为任意集合选定良序后,沿该集合运用这种方法。

代数中的存在性论证

对于一个向量空间,可以将其向量良序化,并按该次序逐个处理。当且仅当一个向量不属于此前保留向量的线性包时,才保留该向量。在极限阶段,将此前保留的所有向量汇集起来。

得到的向量族线性无关,并且张成整个空间,因此是一个基。这种构造可以证明基的存在,却未必能给出可用于实际计算的描述。

许多此类论证也常用佐恩引理来表述;在 ZF 中,佐恩引理同样与选择公理等价。良序将构造组织成相继的阶段,而佐恩引理则确立适当偏序集中极大对象的存在性。

历史与基础地位

格奥尔格·康托尔在发展超限集合论时,将任意集合都可良序化视为一项基本原则。恩斯特·策梅洛于 1904 年发表了一个明确使用选择原则的证明,并于 1908 年发表了另一个证明。围绕这些论证的讨论,推动了人们对选择公理和集合论公理化基础的关注。

该定理的地位取决于所采用的背景公理:

  • 在 ZFC 中,它是一个定理,因为该体系包含选择公理。
  • 仅在 ZF 中,它等价于添加选择公理。
  • 假设 ZF 是相容的,则在 ZF 中既无法证明该定理,也无法证明其否定。

选择公理的独立性结果由库尔特·哥德尔和保罗·科恩的工作确立。这些结果涉及的是相对于指定公理系统的形式可证明性,而不是良序定义本身存在歧义。

局限与常见误解

存在性不等于给出典范的指定方式。 该定理并未为给定集合指出某个首选的良序。某个特定的集合论模型可能具有可定义的实数良序,但 ZFC 并不保证在每个模型中都存在无需参数即可定义的实数良序。

良序化不等于可数列举。 不可数集可以由某个序数来索引,但无法用自然数枚举。

最小不只是极小。 最小元小于所有其他元素。而偏序中的极小元仅仅是指没有严格小于它的元素。良序要求序关系是全序,并且每个非空子集都有最小元。

该定理适用于集合,并不自动同时适用于整个集合论宇宙。 它断言每个集合都有某个良序。在类理论中,用单个类关系对整个宇宙进行良序化是一项全局选择断言,不应将其与通常的集合层面的定理等同起来。

将实数良序化并不能确立连续统假设。 连续统假设规定了实数集的基数在无限基数中的位置。可良序化将实数集的基数纳入序数框架,却不能确定它究竟是哪一个不可数基数。