介绍

定理

推论和推广

应用

介绍

超限归纳法又称超穷归纳法、超限归纳证法，数学中用来证明某种类型命题的重要方法。

定理

设 (Χ,≤)是一个良序集，对任意α∈Χ，Χα={b∈Χ│b<α}称为在Χ中由α所确定的截段。Χ的子集E称为归纳子集，如果对于任何α∈Χ，只要截段Χα为E的子集，就有α∈E。

超限归纳定理断言：设E为良序集(Χ,≤)的归纳子集，则E=Χ。因为若α为Χ的最小元素，则可得α∈E；如果α'为Bα={b∈Χ│b>α}的最小元素，那么Χα'={x∈Χ│x<α'}={α}是E的子集，遂有α'∈E；同理可得α″=(α')'∈E等等。容易看出，Χ的良序性是定理成立的重要依据，倘若把它改为Χ是全序集，则Χ的非空子集可以没有最小元素，命题就不成立了。

推论和推广

当Χ为自然数集N时，就得到上述定理的一个常用的特殊情况，称为数学归纳法，表述为：若N的子集E，满足①0∈E；②对于任何n∈N，如果由一切小于n的自然数k∈E，可以推出n∈E，则E=N。其中一切小于n的自然数k∈E相当于Nn为E的子集，而0∈E则可以由空集必然为E的子集推出。

在引进“类”概念的前提下，超限归纳定理可以叙述为：设C是一个序数类,如果①0∈C；②若α∈C，可得α'=α+1∈C；③若α为极限序数，并且对一切β<α，β∈C，就必然有α∈C，则C是所有序数的类。

应用

超限归纳法是数学归纳法的形式之一，可以应用于（大的）良序集，比如说应用到序数或基数，甚至于所有有序的集。

超限归纳法可用于证明一个命题P在所有序数中成立：

基础：证明P(0)成立；

归纳：证明对于任何一个序数b，如果P(a)在所有序数a<b中成立，那么P(b)也将成立。

后面一步常常分解为两种情况：

能应用和一般的归纳法相似的方法的后继序数（有直接前驱的序数），（P(a)蕴涵P(a+1)），

没有前驱的极限序数，因此不能用这种方法。

显然，极限序数可以通过将极限序数b看成所有小于b的序数的极限来处理：假定在所有的a<b中P(a)成立，取所有这些情况的极限（通常通过并集公理实现），则证明了P(b)。

上面的基础步骤实际上是多余的。如果在所有的a<b中，P(a)为真可以推出P(b)为真，那么P(0)成立就是一个简单的特殊情况，因为在所有a<0中P(a)成立。