超限归纳法
(重定向自超窮遞歸)
超限归纳法(英語:Transfinite Induction)是数学归纳法向(大)良序集合比如基數或序数的集合的扩展。
超限归纳
假设只要对于所有的,为真,则也为真。那么超限归纳告诉我们对于所有序数为真。
就是说,如果为真只要对于所有为真,则对于所有为真。或者更实用的说:若要证明所有序数都符合性质,你可以假定它对于所有更小的已经是成立的。
通常证明被分为三种情况:
- 零情况: 证明为真。
- 后继情况: 证明对于任何后继序数, 得出自(如果需要的话,也假定对于所有 有)。
- 极限情况: 证明对于任何极限序数,得出自 [对于所有]。
留意,以上三種情況(證明方法)都是相同的,只是所考虑的序数类型不同。正式來說不用分开考慮它们,但在实践時,因為它们的证明過程通常相差很大,所以需要分别表述。在一些情況下,「零情況」會被視為一種「極限情況」,因此可以使用極限序數來證明。
超限递归
超限递归是一種构造或定义某种對象的方法,它與超限归纳的概念密切相關。例如,可以定義以序數為下標的集合序列 Aα ,只要指定三个事項:
- 是什么
- 如何确定自(又或者是從到的部分)
- 对于极限序数,如何确定自的对于的序列。
更形式的说,我们陈述超限递归定理如下。给定函数类, , ,存在一个唯一的超限序列带有( 是所有序数的真类),使得
- ,对于所有
- ,对于所有极限序數 。這裡的是指在 上的限制。
注意我们要求, , 的定义域足够广阔来使上述性质有意义。所以满足这些性质的序列的唯一性可以使用超限归纳证明。
更一般的说,你可以在任何良基关系上通过超限递归定义對象。(甚至不需要是集合;它可以是真类,只要它是类似集合的关系便可,也就是说:对于任何 ,使得的所有的搜集必定是集合。)
同选择公理的联系
有一个常见的误解是超限归纳法或超限递归法要求选择公理。其實超限归纳可以应用于任何良序集合。但是常见的情况是使用选择公理来良序排序一个集合,使其適用超限归纳法。