View source for Simple set

A recursively-enumerable set of natural numbers (cf. [[Enumerable set]]) whose complement is an [[immune set]]. Simple sets are intermediate in the sense of [[Many-one reducibility|$m$-reducibility]] (cf. [[Recursive set theory]]) between [[solvable set]]s and [[creative set]]s. 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$.

====Comments====
A set is ''hypersimple'' if it is recursively enumerable and its complement is a [[hyperimmune set]].

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,   "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR>
<TR><TD valign="top">[a1]</TD> <TD valign="top"> Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press (2009). {{ISBN|978-0-19-923076-1}} {{ZBL|1169.03034}}</TD></TR>
</table>

{{TEX|done}}

[[Category:Computability and recursion theory]]