超限归纳法

超限归纳法
术语名称	超限归纳法
英语名称	transfinite induction

超限归纳法(transfinite induction)，指通过起始条件和递推步骤来证明任意序数都满足谓词的一种方法，是数学归纳法的扩展。

全体序数的结构与 Peano 公理定义的自然数结构相似：序数存在 0 ，然后后继序数是自然数的后继的扩展，又增加了一个极限序数。因此形式上，超限归纳法与数学归纳法相似。

由于使用超限归纳法的场景都涉及将需要讨论的对象排序，如果对象本身没有顺序，可能需要使用选择公理或良序定理。

描述

对谓词 [math]\displaystyle{ p }[/math] ，若满足：

• 起始条件/归纳基础(base case / initial case/zero case)： [math]\displaystyle{ p(0) }[/math] ；
• 递推步骤/归纳步骤(induction step / inductive step / step case)：
  • 后继情况(successor case)：证明对任意后继序数 [math]\displaystyle{ \beta' }[/math] 及对应的序数 [math]\displaystyle{ \beta }[/math] ， [math]\displaystyle{ p(\beta) \rightarrow p(\beta') }[/math] ，（若必要，也可以使用全部更小的序数， [math]\displaystyle{ \forall\alpha(\alpha\lt \beta' \rightarrow p(\alpha))\rightarrow p(\beta') }[/math] ；
• 极限情况(limit case)：证明对任意极限序数 [math]\displaystyle{ \lambda }[/math] ，有 [math]\displaystyle{ \forall\alpha(\alpha\lt \lambda \rightarrow p(\alpha))\rightarrow p(\lambda) }[/math] ；

则可证明 [math]\displaystyle{ p(n) }[/math] 对全体序数成立。