Productive set

From Encyclopedia of Mathematics
Revision as of 17:33, 15 November 2014 by Richard Pinch (talk | contribs) (Category:Computability and recursion theory)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.


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



[a1] P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. 306ff
How to Cite This Entry:
Productive set. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.A. Dushskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article