Namespaces
Variants
Actions

Productive set

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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
How to Cite This Entry:
Productive set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Productive_set&oldid=11570
This article was adapted from an original article by V.A. Dushskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article