超穷归纳法

论证过程中依据序数或良序关系以证明某种类型命题的重要方法，是研究无穷对象的一种重要方法。又称超限归纳法。设(X，≤)是一个良序集，对任意α∈X，X=｛β∈X｜β＜α｝称为在X中由α所确定的截段或α的前节。EX称为归纳子集，如果对于任何α∈X，只要截段XX，就有α∈E。

超穷归纳定理断言：设E为良序集(X，≤)的归纳子集，则E=X。因为若α为X的最小元，则由X=E，可得α∈E；如果α为X中不属于E的最小元，但由归纳子集的定义就得α∈E，由这一矛盾就得E=X的结论。

容易看出，X的良序性是定理的依据。倘若把X改为全序集，则X的非空子集可以没有最小元，命题就不成立了。当X为自然数集合N时，就得到上述定理的一个常用的特殊情形，称为数学归纳法，表述为：若EN，并满足①0∈E；②对任何n∈N，由一切小于n的自然数k∈E，可以推出n∈E；则E=N。其中一切小于n的自然数k∈E，相当于NE，而0∈E则是N0=E的结果。

在引进类概念的前提下，对于序数类的超穷归纳定理可以陈述为：设C是一个序数类，如果①0∈C，②若α∈C，则α=α+1∈C，③若λ为极限序数，并且从一切β＜λ，β∈C可得到λ∈C，则C是所有序数的类，即C=0n。对于一般良序类C而言，可以概述为：如果C的任一子集E，满足条件①C的首元在E中，②对于C中的任一元e而言，若e的前节在E中，则e也在E中，那么就E=C。

在实际应用超穷归纳方法时，还有许多灵活方便的形式。一种推广的形式是在良基关系或良偏序(见偏序关系)上作超穷归纳。设关系R为集合X上的良基关系，若EX，对任意a∈X，令X=｛y｜y∈X∧yRa｝，并称X为a的一前节。超穷归纳法对良基关系来说，就是：如果对于任意a，XE，就有a∈E，那么对于这一E而言，有E=X。