递归集

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

设A是一自然数n元组集(AN)，如果A的特征函数

是递归函数，则称A为递归集；如果C(x，…，x)不是递归函数，则称A为非递归集。原始递归集都是递归集，但反之不然。由于配对函数J(x，…，x)及其反函数都是递归函数，于是n元组集A是递归集当且仅当A在J的像｛J(x，…，x)｜(x，…，x)∈A｝是递归集。因此在讨论集合的递归性问题时，常将A与

等同看待。

递归集的类对补、并、交运算封闭，但对投影运算不封闭。即：设A、B是n元组的递归集，则，A∪B，A∩B仍都是递归集，但

未必是递归集。