超限归纳法(transfinite induction)是
数学归纳法向(大)良序集合比如
基数或
序数的集合的扩展。
就是说,如果 P(α) 为真只要 P(β) 对于所有 β < α 为真,则 P(α) 对于所有 α 为真。或者更实用的说:若要证明所有序数 α 都符合性质 P,你可以假定它对于所有更小的 β < α 已经是成立的。
留意,以上三种情况(证明方法)都是相同的,只是所考虑的序数类型不同。正式来说不用分开考虑它们,但在实践时,因为它们的证明过程通常相差很大,所以需要分别表述。在一些情况下,“零情况”会被视为一种“极限情况”,因此可以使用极限序数来证明。
更形式的说,我们陈述
超限递归定理如下。给定函数类G1,G2,G3,存在一个唯一的超限序列F带有 ( 是所有序数的真类),使得
更一般的说,你可以在任何
良基关系R上通过超限递归定义对象。(R甚至不需要是集合;它可以是
真类,只要它是类似
集合的关系便可,也就是说:对于任何x,使得yRx的所有y的搜集必定是集合。)
有一个常见的误解是超限归纳法或超限递归法要求
选择公理。其实超限归纳可以应用于任何良序集合。但是常见的情况是使用
选择公理来良序排序一个集合,使其适用超限归纳法。
超限归纳法是
数学归纳法的形式之一,可以应用于(大的)良序集,比如说应用到序数或基数,甚至于所有有序的集。
归纳:证明对于任何一个序数b,如果P(a)在所有序数a
后面一步常常分解为两种情况:
能应用和一般的归纳法相似的方法的
后继序数(有直接前驱的序数),(P(a)蕴涵P(a+1)),
没有前驱的极限序数,因此不能用这种方法。
显然,极限序数可以通过将极限序数b看成所有小于b的序数的极限来处理:假定在所有的a并集公理实现),则证明了P(b)。