# Difference between revisions of "Simple set"

(Category:Computability and recursion theory) |
|||

Line 10: | Line 10: | ||

{{TEX|done}} | {{TEX|done}} | ||

+ | |||

+ | [[Category:Computability and recursion theory]] |

## Revision as of 07:57, 15 November 2014

A recursively-enumerable set of natural numbers (cf. Enumerable set) whose complement is an immune set. Simple sets are intermediate in the sense of so-called $m$-reducibility (cf. Recursive set theory) between solvable sets and creative sets. The latter are the largest among the enumerable sets in the sense of $m$-reducibility. Let $P$ be an arbitrary simple set, and let $K$ be an arbitrary creative set of natural numbers (e.g. the set of Gödel numbers of theorems of formal arithmetic); then there does not exist a general recursive function $f$ reducing $K$ to $P$, i.e. such that $$ x \in K \Leftrightarrow f(x) \in P \ . $$

Reducibility of $P$ to $K$ always takes place, but not one solvable set is reducible to $K$.

#### References

[1] | V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian) |

[2] | A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian) |

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

**How to Cite This Entry:**

Simple set.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Simple_set&oldid=34507