遞迴集

如果存在一個 完全 遞迴函式 使得對於 ，，並且對於 ，，則稱整數集合 是遞迴的。任何遞迴集也是 遞迴可列舉的。

有限集、具有有限補集的集合、奇數和素數都是遞迴集的例子。兩個遞迴集的並集和交集本身也是遞迴的，遞迴集的補集也是如此。