Difference between revisions of "Simple set"
m (gather refs) |
|||
(4 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
− | A recursively-enumerable set of natural numbers (cf. [[ | + | 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 \ . | x \in K \Leftrightarrow f(x) \in P \ . | ||
Line 5: | Line 5: | ||
Reducibility of $P$ to $K$ always takes place, but not one solvable set is reducible to $K$. | 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==== | ====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></table> | + | <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}} | {{TEX|done}} | ||
+ | |||
+ | [[Category:Computability and recursion theory]] |
Latest revision as of 20:46, 23 November 2023
A recursively-enumerable set of natural numbers (cf. Enumerable set) whose complement is an immune set. Simple sets are intermediate in the sense of $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$.
Comments
A set is hypersimple if it is recursively enumerable and its complement is a hyperimmune set.
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 |
[a1] | Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press (2009). ISBN 978-0-19-923076-1 Zbl 1169.03034 |
Simple set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Simple_set&oldid=34506