Namespaces
Variants
Actions

Creative set

From Encyclopedia of Mathematics
Revision as of 17:24, 15 November 2014 by Richard Pinch (talk | contribs) (Category:Computability and recursion theory)
Jump to: navigation, search

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=34512
This article was adapted from an original article by V.A. Dushskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article