Productive set

A set $A$ of natural numbers for which there exists a partial recursive function $\phi(x)$ such that $\phi(x) \in A \setminus W_x$ for every recursively-enumerable set (cf. Enumerable set) $W_x$ with Gödel number $x$ contained in $A$. It is known that for every productive set $A$ there is a general recursive function $\psi$ such that for any $x$, depending on the mutual disposition of the sets $A$ and $W_x$, one has either $\psi(x) \in A \setminus W_x$ or $\psi(x) \in W_x \setminus A$. Hence a productive set can be "effectively" distinguished from any given recursively-enumerable set. On the other hand, every productive set contains infinite recursively-enumerable subsets, so that productive sets are opposite to immune sets (cf. Immune set), although the productive and the immune sets do not exhaust the family of sets that are not recursively enumerable. Many sets playing an important role in recursive set theory and its applications are productive (e.g. the set of all Gödel numbers of general recursive functions in some Gödel enumeration of all partial recursive functions, as are the sets of all numbers of true or false formulas in elementary arithmetic in a natural enumeration of all formulas in it). Recursively-enumerable sets whose complements (in the number series) are productive are called creative sets; they form an important class of recursively-enumerable sets.

References

[1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165

References

[a1]	P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. 306ff