关于带函数指标的相对递归定理的注记

对于递归的部分泛函,指标为数变元f的递归定理已有叙述。在进一步讨论递归于有限序列Φ的部分泛函时,也有了所谓来自Φ的指标f的递归定理。本文的目的是要讨论:对于递归于全函数和全谓词的一个集合Φ的部分泛函,是否可以建立一个指标为函数变元α的相对递归定理呢?这个结论是肯定的。在本文中经常引用下述两个引理的一般形式。传递引理设Φ递归于Ψ,那末递归于Φ的每个函数F也是递归于Ψ的。有限引理设一个函数F递归于Φ,那末它必是递归于Φ的某个有限序列。