Namespaces
Variants
Actions

Difference between revisions of "Creative set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
A recursively enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270301.png" /> of natural numbers whose complement <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270302.png" /> (in the set of natural numbers) is a [[Productive set|productive set]]; in other words, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270303.png" /> is creative if it is recursively enumerable and if there exists a partial recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270304.png" /> such that, for any recursively enumerable subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270305.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270306.png" />, with Gödel number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270307.png" />,
+
A recursively enumerable set $A$ of natural numbers whose complement $\bar A$ (in the set of natural numbers) is a [[productive set]]; in other words, a set $A$ is creative if it is recursively enumerable and if there exists a partial recursive function $\phi(x)$ such that, for any recursively enumerable subset $W_x$ in $\bar A$, with Gödel number $x$,
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027030/c0270308.png" /></td> </tr></table>
+
\phi(x) \in \bar A \setminus W_x \ .
 +
$$
  
 
Creative sets are frequently encountered in various algorithmically unsolvable problems, and they therefore constitute the most important class of recursively enumerable sets which are not recursive. In many formal theories, the sets of (numbers of) provable and refutable formulas turn out to be creative (assuming a natural enumeration of all formulas of the theory); in particular, this is the case for Peano arithmetic and, in general, for all recursively inseparable theories (i.e. theories the sets of provable and refutable formulas of which are effectively inseparable). All creative sets are recursively isomorphic to one another (i.e. for any two creative sets there exists a recursive one-to-one mapping of the natural numbers which maps one set onto the other), and they all belong to the same Turing degree — the largest of the degrees of recursively enumerable sets. The concept of creativity generalizes to sequences of sets and other objects.
 
Creative sets are frequently encountered in various algorithmically unsolvable problems, and they therefore constitute the most important class of recursively enumerable sets which are not recursive. In many formal theories, the sets of (numbers of) provable and refutable formulas turn out to be creative (assuming a natural enumeration of all formulas of the theory); in particular, this is the case for Peano arithmetic and, in general, for all recursively inseparable theories (i.e. theories the sets of provable and refutable formulas of which are effectively inseparable). All creative sets are recursively isomorphic to one another (i.e. for any two creative sets there exists a recursive one-to-one mapping of the natural numbers which maps one set onto the other), and they all belong to the same Turing degree — the largest of the degrees of recursively enumerable sets. The concept of creativity generalizes to sequences of sets and other objects.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.R. Shoenfield,  "Mathematical logic" , Addison-Wesley  (1967)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  J.R. Shoenfield,  "Mathematical logic" , Addison-Wesley  (1967)</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
For definitions and discussions of the various concepts mentioned above, such as recursively enumerable set, recursive isomorphism, Turing degree, etc. cf. [[Recursive set theory|Recursive set theory]] and [[Degree of undecidability|Degree of undecidability]].
+
For definitions and discussions of the various concepts mentioned above, such as recursively enumerable set, recursive isomorphism, Turing degree, etc. cf. [[Recursive set theory]] and [[Degree of undecidability]].
 +
 
 +
{{TEX|done}}

Revision as of 17:22, 15 November 2014

A recursively enumerable set $A$ of natural numbers whose complement $\bar A$ (in the set of natural numbers) is a productive set; in other words, a set $A$ is creative if it is recursively enumerable and if there exists a partial recursive function $\phi(x)$ such that, for any recursively enumerable subset $W_x$ in $\bar A$, with Gödel number $x$, $$ \phi(x) \in \bar A \setminus W_x \ . $$

Creative sets are frequently encountered in various algorithmically unsolvable problems, and they therefore constitute the most important class of recursively enumerable sets which are not recursive. In many formal theories, the sets of (numbers of) provable and refutable formulas turn out to be creative (assuming a natural enumeration of all formulas of the theory); in particular, this is the case for Peano arithmetic and, in general, for all recursively inseparable theories (i.e. theories the sets of provable and refutable formulas of which are effectively inseparable). All creative sets are recursively isomorphic to one another (i.e. for any two creative sets there exists a recursive one-to-one mapping of the natural numbers which maps one set onto the other), and they all belong to the same Turing degree — the largest of the degrees of recursively enumerable sets. The concept of creativity generalizes to sequences of sets and other objects.

References

[1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)
[2] J.R. Shoenfield, "Mathematical logic" , Addison-Wesley (1967)


Comments

For definitions and discussions of the various concepts mentioned above, such as recursively enumerable set, recursive isomorphism, Turing degree, etc. cf. Recursive set theory and Degree of undecidability.

How to Cite This Entry:
Creative set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Creative_set&oldid=34511
This article was adapted from an original article by V.A. Dushskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article