超限递归定理

数学术语

超限递归定理(transfinite recursive theorem)是递归定理的推广，该定理断言：对任意函数F：V→V，存在惟一的函数G：ord→V，使得对任意α∈ord有G(α)=F(G|α)，这里V表示一切集合构成的类，G|α表示函数G在α上的限制。当在上述定理限于考虑函数G：ω→V这一特殊情形时，定理就变成平常的递归定理。超限递归定理是冯·诺伊曼(J.von Neumann)于1923年提出的，该定理的意义是，由已给的函数F，以集合{G(β)|β<α}为F的自变量，所确定的函数值作为被定义函数G在α上的值，所定义出的函数G是惟一确定的，这种定义函数的方法不同于一般的定义方法，因为在定义G(α)时要用到已给的F，而且要用到各个G(β)，β<α。

基本介绍

超限递归定理对于每一个公式γ(x，y)有下述定理：设(A，<)为良序集，且对任何f有唯一的y使γ(f，y)成立，则存在唯一以A为定义域的函数F，使得对于A中的所有t，有：

γ(F↾Seg t，F(t))，

其中 Seg t={x|x

这是个定理模式，表明有无限多个定理，对于每一个γ(x，y)，它都是一个定理。

相关说明

有了良序集，便可在其上建立两个重要的定理，即超限归纳定理和超限递归定理，它们是研究超限无穷集合的主要基础。所谓超限无穷集合是指超过自然数集合ω的任何无穷集合，由于ω是第一非有限的、最小的无穷集合，是第一个遇到的极限序数，超过这个极限序数的无穷集合论证问题都属于超限问题，归纳定理的主要功能是克服了无穷元都要论证的困难。而递归定理的主要功能是确立运算函数的存在，给出计数的特性，以及其它论证中的作用。

在定义序数运算（加、乘、幂）时，需要用超限递归定理：若G是一运算，则有一运算F，使得对每一序数α，都有F(α)=G(F↾α)。而这一定理的证明要用到代换公理。有了代换公理还可以得到极限序数ω+ω的存在性。如果先将正整数从小排到大，再把非正整数从大排到小而成一序列：1，2，3，…，0，-1，-2，…。从而全体整数就良序了，其序型即为ω+ω。

事实上，任一良序集<ω，<>，都有唯一的序数α使得<ω，<>序同构于<α，∈>。因此，就可以把良序集按序同构来分类，并将同属于一类的称为具有同一序型的良序集。而序数就可定义作为同构的良序集的代表。依此，可以定义序数的运算。例如，序数的加法可以定义如下：若α,β为序数，γ为极限序数。

即用关于α的超限归纳原理来定义β+α。同样地可以定义序数的积和幂，以及相应的运算性质，如结合律等。

超限递归定理的证明需要应用下面的代换公理。

代换公理对于任何集合A和一个具有函数性质且不含B的公式φ(x，y)有：

(y∈B⇆)，

或完全形式地表示为：

(∀A)((∀x)(∃!y)(x∈A^φ(x，y)→(∃B)(∀y)(y∈B⇆(∃x)(x∈∧φ(x，y))))。

如果把φ(x，y)理解为“x被代换成y”，代换公理可表述成：若A的每个元至多被代换一个对象，则所有被代换的对象就构成了一个集合B。

全国各地天气预报查询

上海市

市辖区

云南省