Namespaces
Variants
Actions

Difference between revisions of "Productive set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Category:Computability and recursion theory)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750401.png" /> of natural numbers for which there exists a [[Partial recursive function|partial recursive function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750402.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750403.png" /> for every recursively-enumerable set (cf. [[Enumerable set|Enumerable set]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750404.png" /> with Gödel number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750405.png" /> contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750406.png" />. It is known that for every productive set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750407.png" /> there is a [[General recursive function|general recursive function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750408.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p0750409.png" />, depending on the mutual disposition of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p07504010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p07504011.png" />, one has either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p07504012.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075040/p07504013.png" />. 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|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.
+
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 set]]s; they form an important class of recursively-enumerable sets.
  
 
====References====
 
====References====
Line 10: Line 10:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. 306ff</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. 306ff</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}
 +
 
 +
[[Category:Computability and recursion theory]]

Latest revision as of 17:33, 15 November 2014

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


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