超限归纳法

维基百科,自由的百科全书
跳转至: 导航搜索

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

超限归纳[编辑]

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

就是说,如果 P(α) 为真只要 P(β) 对于所有 β < α 为真,则 P(α) 对于所有 α 为真。或者更实用的说:若要证明所有序数 α 都符合性质 P,你可以假定它对于所有更小的 β < α 已经是成立的。

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

  • 零情况: 证明 P(0) 为真。
  • 后继情况: 证明对于任何后继序数 β+1, P(β+1) 得出自 P(β)(如果需要的话,也假定对于所有 α < β 有 P(α))。
  • 极限情况: 证明对于任何极限序数 λ, P(λ) 得出自 [P(α) 对于所有 α < λ]。

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

超限递归[编辑]

超限递归是一種构造或定义某种對象的方法,它與超限归纳的概念密切相關。例如,可以定義以序數為下標的集合序列 Aα ,只要指定三个事項:

  • A0 是什么
  • 如何确定 Aα+1Aα(又或者是從A0Aα的部分)
  • 对于极限序数 λ,如何确定 AλAα 的对于 α < λ 的序列。

更形式的说,我们陈述超限递归定理如下。给定函数类 G1, G2, G3,存在一个唯一的超限序列 F 带有 dom(F) = OrdOrd 是所有序数的真类),使得

  • F(0) = G1(\emptyset)
  • F(\alpha + 1) = G2(F(\alpha)),对于所有 \alpha \in Ord
  • F(\alpha) = G3(F \upharpoonright \alpha),对于所有极限序數 \alpha \neq 0。這裡的F \upharpoonright \alpha是指F\{\beta\in Ord: \beta<\alpha\}上的限制。

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

更一般的说,你可以在任何良基关系 R 上通过超限递归定义對象。(R 甚至不需要是集合;它可以是真类,只要它是类似集合的关系便可,也就是说:对于任何 x,使得 yRx 的所有 y 的搜集必定是集合。)

同选择公理的联系[编辑]

有一个常见的误解是超限归纳法或超限递归法要求选择公理。其實超限归纳可以应用于任何良序集合。但是常见的情况是使用选择公理来良序排序一个集合,使其適用超限归纳法。

参见[编辑]