超限归纳法

超限归纳法(英语:Transfinite Induction)是数学归纳法向(大)良序集合比如基数序数的集合的扩展。

超限归纳

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

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

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

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

留意,以上三种情况(证明方法)都是相同的,只是所考虑的序数类型不同。正式来说不用分开考虑它们,但在实践时,因为它们的证明过程通常相差很大,所以需要分别表述。在一些情况下,“零情况”会被视为一种“极限情况”,因此可以使用极限序数来证明。

超限递归

超限递归是一种构造或定义某种对象的方法,它与超限归纳的概念密切相关。例如,可以定义以序数为下标的集合序列 Aα ,只要指定三个事项:

  •  是什么
  • 如何确定  (又或者是从  的部分)
  • 对于极限序数 ,如何确定  的对于 的序列。

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

  •  
  •  ,对于所有  
  •  ,对于所有极限序数  。这里的 是指  上的限制。

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

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

同选择公理的联系

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

参见