超限归纳法是一种数学证明方法,用于证明某个性质在良序集的每一个阶段都成立,最常见的应用对象是序数。证明某一阶段的性质时,可以假定该性质在此前所有阶段都成立。它将数学归纳法推广到自然数以外的范围,涵盖没有直接前驱的阶段。其有效性源于良序的定义性特征:每个非空子集都有最小元。
原理的表述
设 是一个良序集, 是其元素的某个性质。超限归纳法断言,如果
那么
对每个 , 都成立这一假设,称为 处的归纳假设。证明的核心任务是:对于任意 ,说明这一假设能够推出 。
对于序数,这一原理通常写作
这里的变量取遍所有序数。在策梅洛—弗兰克尔集合论中,这被理解为一个定理模式:每个公式 (可以含有参数)都给出该原理的一个实例。它不要求存在一个包含所有序数的集合。
最小反例证明
这一原理可用最小反例反证法来证明。假设归纳蕴涵成立,但 中存在不满足 的元素。那么,反例组成的集合就有一个最小元 。所有先于 的元素都满足 ,因此由归纳蕴涵可得 ,这与 是反例矛盾。
同样的论证也适用于关于所有序数的性质,而不必将所有反例视为一个集合。如果 是任意一个反例,那么不大于 的序数中的反例构成一个非空集合,因此其中存在最小元。
零阶段、后继阶段与极限阶段
对于序数,证明通常分为三种情形。
- **零阶段:**证明 。
- **后继阶段:**利用归纳假设证明 。
- **极限阶段:**对于每个非零极限序数 ,由所有 对应的性质 证明 。
后继序数 是大于 的最小序数。非零极限序数既不是零,也不是后继序数。第一个无限序数 是极限序数:它的前驱恰好是所有有限序数,其中没有最大的前驱。
分三种情形的表述,是证明统一的一般归纳蕴涵的一种便捷方式。在零阶段,“所有先前情形都成立”这一假设是空真的,因为不存在更早的序数。在后继阶段,证明可以使用此前的所有情形,而不只是紧邻的前一情形。不过,很多时候只用前一情形就足够了。
极限阶段是超限归纳法特有的额外要求。例如,设 表示 是有限的。那么 成立,且 蕴涵 ,但 不成立。因此,仅有初始情形和后继蕴涵,并不能证明某个性质对所有序数都成立。
与普通归纳法的关系
自然数在通常的次序下具有序型 。将超限归纳法限制在这一次序上,就得到强归纳法:为了证明 ,假定对每个 , 都成立。
对于自然数,强归纳法与普通归纳法等价。从普通归纳法推出强归纳法的一种方式,是对以下性质应用普通归纳法:
小于 的序数中没有非零极限序数,因此,只证明关于自然数的命题时,不会出现单独的极限步骤。如果证明还要涵盖 或更大的序数,就必须处理新增的极限阶段。
“超限”并不只是指“不可数”。归纳过程可以经过无限阶段,同时始终处于一个可数集上的良序之内,例如小于 的所有序数所构成的良序。
归纳法与超限递归
超限归纳法用于证明有关对象或阶段的命题。超限递归则逐个阶段定义对象。这两种方法密切相关,但在逻辑上有所区别。
递归定义可以采用以下形式:
其中, 是 在更早序数上的限制, 是一条指定规则,根据此前的值确定唯一的下一个值。在适当的集合论表述下,超限递归定理保证所得函数的存在性和唯一性。随后,可以用超限归纳法证明该函数的性质。
例如,可以用下式定义一个集合层级:
其中 为非零极限序数。这些等式描述了一种递归构造;要证明所得集合具有某种性质,则需要归纳论证。
取并集是极限阶段的一种常见规则,而非普遍要求。根据具体构造,极限阶段也可以取交集或采用其他运算。同样,归纳原理本身并不规定如何推出极限阶段的结论:这取决于所要证明的性质。
示例:递增层级
假设一个递归定义的集合序列满足
并假设 具有扩张性,即对每个相关的集合 ,都有 。超限归纳法可证明
对 进行归纳。
- **零阶段:**不存在 ,因此断言空真。
- **后继阶段:**设 。由扩张性可得 。如果 ,则由归纳假设可得 ,因而 。
- **极限阶段:**如果 是非零极限序数,且 ,那么 是定义 的并集中的一个集合,因此 。
这个例子说明了后继阶段与极限阶段为何往往需要不同的论证:后继情形利用运算 的某个性质,而极限情形利用并集的定义。
良基归纳法
超限归纳法是良基归纳法的一个特例。如果集合 上的关系 满足:每个非空子集 都有一个 -极小元,即存在某个 ,使得不存在满足 的 ,那么就称 是良基的。
良基归纳法的形式为
与良序不同,良基关系不要求每一对元素都可比较。因此,这一更一般的原理适用于具有分支依赖关系的结构,包括语法树和递归定义的表达式。选用适当的“是较小组成部分”关系,结构归纳法也可以从这一角度理解。
对于严格偏序,良基性涉及极小元的存在;要成为良序,还必须满足任意两个元素都可比较。
应用
超限归纳法在集合论中具有基础性地位。它用于证明序数运算、集合层级以及以序数为指标的构造的性质。有关序数算术的论证,通常将后继阶段与极限阶段分开处理;在极限阶段,运算往往通过上确界来定义。
在拓扑学中,反复去除孤立点的过程可以按超限阶段组织。在后继阶段施加导集运算,在极限阶段对先前的集合取交集。通过归纳,可以证明这一递减序列的结构性质。
在证明论中,沿指定序数次序进行的归纳用于分析形式理论。归纳原理的强度不仅取决于所涉及的次序,还取决于允许使用哪些公式,以及基础理论能够证明关于该次序的哪些事实。
在计算机科学中,相关的良基论证通过给状态赋予良基序中的值,并证明每个计算步骤都会使所赋的值严格减小,来确立终止性。取序数值的度量能够处理单一自然数度量无法充分表示的下降模式。
基础与局限
沿序数进行的超限归纳法,无须选择公理,即可在策梅洛—弗兰克尔集合论中证明。当论证要求对任意集合赋予良序时,选择公理才会起作用:“每个集合都可以赋予良序”这一断言与选择公理等价。
这一原理并不能为任意无限次序上的归纳提供依据。例如,整数在通常的次序下没有最小元,因而不是良序的。性质“ 非负”满足如下蕴涵:如果每个小于 的整数都非负,那么 非负;这是因为当 为负数时,前件为假。然而,这个性质并非对每个整数都成立。这说明良序或良基性假设不可或缺。
最后,归纳证明必须从同一性质在先前阶段的成立情况,以及独立可用的事实出发,推出所需的性质。任何论证都不能预先假定结论在所有阶段成立,也不能用后继阶段的论证代替尚未证明的极限阶段论证。