产生集

可以用一个递归函数对其非递归可枚举性举证的自然数集。

如果A是一个非递归可枚举集，则A与序列

W，W，W，…，W，…

中的每一个都不等。要确认这一点，只要确认对每个x，若WA则AW就行了。而这等价于

对每个x，若WA则存在y使y∈A－W。

这些y(作为x的函数)构成了A不是递归可枚举集的全部证据。所谓产生集就是要求全部证据可以由一个递归函数统一给出：

设AN，如果存在一个递归全函数g，使对每个WA有g(x)∈A一W，则称A为产生集，g称为A的产生函数(g产生了A不是递归可枚举集的全部证据)。

由定义易见，产生集都不是递归可枚举集(因而都是无穷集)。每个产生集都有无穷的递归可枚举的子集。如果A是产生集并且A≤B(参见多一归约)，则B是产生集。

常见的产生集有：

　｛x｜φ(x)无定义｝

　｛x｜φ不是零函数｝

　｛x｜cW｝(c是一个固定的数)

　｛x｜φ不是全函数｝，等等。