Productive set
A set of natural numbers for which there exists a partial recursive function
such that
for every recursively-enumerable set (cf. Enumerable set)
with Gödel number
contained in
. It is known that for every productive set
there is a general recursive function
such that for any
, depending on the mutual disposition of the sets
and
, one has either
or
. 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 |
Comments
References
[a1] | P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. 306ff |
Productive set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Productive_set&oldid=11570