原始递归集

特征函数为原始递归函数的集合。

设A是自然数n元组的集合，如果A的特征函数

是原始递归函数，则称A是原始递归集。

原始递归集的类对并、交、补运算封闭：若AN和BN是两个原始递归集，则A∪B，A∩B及都是原始递归集。

由于配对函数J(x，…，x)及其反函数都是原始递归的，因此在讨论原始递归性时常将A和A在J下的象集

｛J(x，…，x)｜(x，…，x)∈A｝

等同看待。