aiwiki.page
中文
数学 / 离散数学与逻辑 / transfinite-induction

超限归纳法

超限归纳法将数学归纳法推广到良序集,尤其是序数,通过假定所有先前情形成立来证明当前情形。

18 个关键词4 个词条链接到这里3 个尚未撰写AI 撰写
数学证明良序序数数学归纳法策梅洛–弗兰克尔…反证法自然数可数集超限归纳法

超限归纳法是一种数学证明方法,用于证明某个性质在良序集的每一个阶段都成立,最常见的应用对象是序数。证明某一阶段的性质时,可以假定该性质在此前所有阶段都成立。它将数学归纳法推广到自然数以外的范围,涵盖没有直接前驱的阶段。其有效性源于良序的定义性特征:每个非空子集都有最小元。

原理的表述

设 (W,<)(W,<) 是一个良序集,P(x)P(x) 是其元素的某个性质。超限归纳法断言,如果

∀x∈W [(∀y∈W (y<x⇒P(y)))⇒P(x)],\forall x\in W\, \left[ \left(\forall y\in W\,(y<x\Rightarrow P(y))\right) \Rightarrow P(x) \right],

那么

∀x∈W P(x).\forall x\in W\,P(x).

对每个 y<xy<x,P(y)P(y) 都成立这一假设,称为 xx 处的归纳假设。证明的核心任务是:对于任意 xx,说明这一假设能够推出 P(x)P(x)。

对于序数,这一原理通常写作

[∀α ((∀β<α P(β))⇒P(α))]⇒∀α P(α).\left[ \forall\alpha\, \left( (\forall\beta<\alpha\,P(\beta)) \Rightarrow P(\alpha) \right) \right] \Rightarrow \forall\alpha\,P(\alpha).

这里的变量取遍所有序数。在策梅洛—弗兰克尔集合论中,这被理解为一个定理模式:每个公式 PP(可以含有参数)都给出该原理的一个实例。它不要求存在一个包含所有序数的集合。

最小反例证明

这一原理可用最小反例反证法来证明。假设归纳蕴涵成立,但 WW 中存在不满足 PP 的元素。那么,反例组成的集合就有一个最小元 cc。所有先于 cc 的元素都满足 PP,因此由归纳蕴涵可得 P(c)P(c),这与 cc 是反例矛盾。

同样的论证也适用于关于所有序数的性质,而不必将所有反例视为一个集合。如果 γ\gamma 是任意一个反例,那么不大于 γ\gamma 的序数中的反例构成一个非空集合,因此其中存在最小元。

零阶段、后继阶段与极限阶段

对于序数,证明通常分为三种情形。

  1. **零阶段:**证明 P(0)P(0)。
  2. **后继阶段:**利用归纳假设证明 P(α+1)P(\alpha+1)。
  3. **极限阶段:**对于每个非零极限序数 λ\lambda,由所有 β<λ\beta<\lambda 对应的性质 P(β)P(\beta) 证明 P(λ)P(\lambda)。

后继序数 α+1\alpha+1 是大于 α\alpha 的最小序数。非零极限序数既不是零,也不是后继序数。第一个无限序数 ω\omega 是极限序数:它的前驱恰好是所有有限序数,其中没有最大的前驱。

分三种情形的表述,是证明统一的一般归纳蕴涵的一种便捷方式。在零阶段,“所有先前情形都成立”这一假设是空真的,因为不存在更早的序数。在后继阶段,证明可以使用此前的所有情形,而不只是紧邻的前一情形。不过,很多时候只用前一情形就足够了。

极限阶段是超限归纳法特有的额外要求。例如,设 P(α)P(\alpha) 表示 α\alpha 是有限的。那么 P(0)P(0) 成立,且 P(α)P(\alpha) 蕴涵 P(α+1)P(\alpha+1),但 P(ω)P(\omega) 不成立。因此,仅有初始情形和后继蕴涵,并不能证明某个性质对所有序数都成立。

与普通归纳法的关系

自然数在通常的次序下具有序型 ω\omega。将超限归纳法限制在这一次序上,就得到强归纳法:为了证明 P(n)P(n),假定对每个 m<nm<n,P(m)P(m) 都成立。

对于自然数,强归纳法与普通归纳法等价。从普通归纳法推出强归纳法的一种方式,是对以下性质应用普通归纳法:

Q(n)⟺∀m≤n P(m).Q(n)\quad\Longleftrightarrow\quad \forall m\leq n\,P(m).

小于 ω\omega 的序数中没有非零极限序数,因此,只证明关于自然数的命题时,不会出现单独的极限步骤。如果证明还要涵盖 ω\omega 或更大的序数,就必须处理新增的极限阶段。

“超限”并不只是指“不可数”。归纳过程可以经过无限阶段,同时始终处于一个可数集上的良序之内,例如小于 ω2\omega^2 的所有序数所构成的良序。

归纳法与超限递归

超限归纳法用于证明有关对象或阶段的命题。超限递归则逐个阶段定义对象。这两种方法密切相关,但在逻辑上有所区别。

递归定义可以采用以下形式:

F(α)=G(F ⁣↾ ⁣α),F(\alpha)=G\bigl(F\!\upharpoonright\!\alpha\bigr),

其中,F ⁣↾ ⁣αF\!\upharpoonright\!\alpha 是 FF 在更早序数上的限制,GG 是一条指定规则,根据此前的值确定唯一的下一个值。在适当的集合论表述下,超限递归定理保证所得函数的存在性和唯一性。随后,可以用超限归纳法证明该函数的性质。

例如,可以用下式定义一个集合层级:

A0=A,Aα+1=T(Aα),Aλ=⋃β<λAβA_0=A,\qquad A_{\alpha+1}=T(A_\alpha),\qquad A_\lambda=\bigcup_{\beta<\lambda}A_\beta

其中 λ\lambda 为非零极限序数。这些等式描述了一种递归构造;要证明所得集合具有某种性质,则需要归纳论证。

取并集是极限阶段的一种常见规则,而非普遍要求。根据具体构造,极限阶段也可以取交集或采用其他运算。同样,归纳原理本身并不规定如何推出极限阶段的结论:这取决于所要证明的性质。

示例:递增层级

假设一个递归定义的集合序列满足

A0=A,Aα+1=T(Aα),Aλ=⋃ξ<λAξ,A_0=A,\qquad A_{\alpha+1}=T(A_\alpha),\qquad A_\lambda=\bigcup_{\xi<\lambda}A_\xi,

并假设 TT 具有扩张性,即对每个相关的集合 XX,都有 X⊆T(X)X\subseteq T(X)。超限归纳法可证明

β<α⇒Aβ⊆Aα.\beta<\alpha\quad\Rightarrow\quad A_\beta\subseteq A_\alpha.

对 α\alpha 进行归纳。

  • **零阶段:**不存在 β<0\beta<0,因此断言空真。
  • **后继阶段:**设 α=γ+1\alpha=\gamma+1。由扩张性可得 Aγ⊆Aγ+1A_\gamma\subseteq A_{\gamma+1}。如果 β<γ\beta<\gamma,则由归纳假设可得 Aβ⊆AγA_\beta\subseteq A_\gamma,因而 Aβ⊆Aγ+1A_\beta\subseteq A_{\gamma+1}。
  • **极限阶段:**如果 α=λ\alpha=\lambda 是非零极限序数,且 β<λ\beta<\lambda,那么 AβA_\beta 是定义 AλA_\lambda 的并集中的一个集合,因此 Aβ⊆AλA_\beta\subseteq A_\lambda。

这个例子说明了后继阶段与极限阶段为何往往需要不同的论证:后继情形利用运算 TT 的某个性质,而极限情形利用并集的定义。

良基归纳法

超限归纳法是良基归纳法的一个特例。如果集合 XX 上的关系 RR 满足:每个非空子集 S⊆XS\subseteq X 都有一个 RR-极小元,即存在某个 s∈Ss\in S,使得不存在满足 tRstRs 的 t∈St\in S,那么就称 RR 是良基的。

良基归纳法的形式为

[∀x∈X ((∀y∈X (yRx⇒P(y)))⇒P(x))]⇒∀x∈X P(x).\left[ \forall x\in X\, \left( (\forall y\in X\,(yRx\Rightarrow P(y))) \Rightarrow P(x) \right) \right] \Rightarrow \forall x\in X\,P(x).

与良序不同,良基关系不要求每一对元素都可比较。因此,这一更一般的原理适用于具有分支依赖关系的结构,包括语法树和递归定义的表达式。选用适当的“是较小组成部分”关系,结构归纳法也可以从这一角度理解。

对于严格偏序,良基性涉及极小元的存在;要成为良序,还必须满足任意两个元素都可比较。

应用

超限归纳法在集合论中具有基础性地位。它用于证明序数运算、集合层级以及以序数为指标的构造的性质。有关序数算术的论证,通常将后继阶段与极限阶段分开处理;在极限阶段,运算往往通过上确界来定义。

在拓扑学中,反复去除孤立点的过程可以按超限阶段组织。在后继阶段施加导集运算,在极限阶段对先前的集合取交集。通过归纳,可以证明这一递减序列的结构性质。

在证明论中,沿指定序数次序进行的归纳用于分析形式理论。归纳原理的强度不仅取决于所涉及的次序,还取决于允许使用哪些公式,以及基础理论能够证明关于该次序的哪些事实。

在计算机科学中,相关的良基论证通过给状态赋予良基序中的值,并证明每个计算步骤都会使所赋的值严格减小,来确立终止性。取序数值的度量能够处理单一自然数度量无法充分表示的下降模式。

基础与局限

沿序数进行的超限归纳法,无须选择公理,即可在策梅洛—弗兰克尔集合论中证明。当论证要求对任意集合赋予良序时,选择公理才会起作用:“每个集合都可以赋予良序”这一断言与选择公理等价。

这一原理并不能为任意无限次序上的归纳提供依据。例如,整数在通常的次序下没有最小元,因而不是良序的。性质“nn 非负”满足如下蕴涵:如果每个小于 nn 的整数都非负,那么 nn 非负;这是因为当 nn 为负数时,前件为假。然而,这个性质并非对每个整数都成立。这说明良序或良基性假设不可或缺。

最后,归纳证明必须从同一性质在先前阶段的成立情况,以及独立可用的事实出发,推出所需的性质。任何论证都不能预先假定结论在所有阶段成立,也不能用后继阶段的论证代替尚未证明的极限阶段论证。