超限归纳法 发表评论(0) 编辑词条

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

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

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

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

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

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

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

　　显然，极限序数可以通过极限序数b 是所有序数的上确界来处理；因为对于所有序数都有 a<b，所以假定在所有的 a<b 中 P(a) 成立，则证明了 P(b)。

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

　　假设只要对于所有的β<α，P(β)为真，则P(α)也为真。那么超限归纳告诉我们P对于所有序数为真。

　　就是说，如果P(α)为真只要P(β)对于所有β<α为真，则P(α)对于所有α为真。或者更实用的说:为了证明对于所有序数α的一个性质P，你可以假定它已经对于所有更小β<α是已知的。

　　通常证明被分为三种情况:

• 零情况:证明P(0)为真。

• 后继情况:证明对于任何后继序数β1，P(β1)得出自P(β) (如果必需的话，证明P(α)对于所有α<β)。

*极限情况:证明对于任何极限序数λ, P(λ)得出自[P(α)对于所有α<λ]。

　　注意第二和第三种情况是同一的，除了对于所考虑的序数类型不同之外。它们不是必须在形式上分开证明，但在实践中它们的证明典型的非常不同而需要分别表述。

　　超限递归是密切相关于超限归纳概念的构造或定义某种东西的方法。例如，集合序列A_a被定义于所有的序数α，通过指定三个事情:

• A₀是什么

• 如何确定A_a1自A_a (也可能从整个序列达到A_a)

• 对于极限序数λ，如何确定Aλ从A_a的对于α<λ的序列。

　　更形式的说，陈述超限递归定理如下。给定函数类G₁,G₂,G₃，存在一个唯一的超限序列F带有dom(F)=Ord(Ord是所有序数的真类)使得

• F(α+1) = G₂(F(a))，对于所有

• F(α) =)，对于所有极限

　　注意我们要求G₁,G₂,G₃的定义域足够广阔来使上述性质有意义。所以满足这些性质的序列的唯一性可以使用超限归纳证明。

　　更一般的说，你可以在任何良序关系R上通过超限递归定义东西。 (R甚至不需要是集合；它可以是真类，假定它是类似集合的关系；就是说，对于任何x，使得yRx的所有y的搜集必定是集合。)

　　有一个常见的误解是超限归纳或超限递归或二者要求选择公理。这是错误的，超限归纳可以应用于任何良序集合。但是常见的情况是使用超限归纳的这种证明或构造也使用选择公理来良序排序一个集合。

• 数学归纳法
• 结构归纳法
• epsilon-归纳