超限归纳法

(重定向自超窮遞歸)

跳转到: 导航, 搜索

超限归纳法是数学归纳法向(大)良序集合比如基数或序数的集合的扩展。

[编辑] 超限归纳

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

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

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

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

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

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

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

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

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