Simple set
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 -reducibility (cf. Recursive set theory) between solvable sets and creative sets. The latter are the largest among the enumerable sets in the sense of -reducibility. Let be an arbitrary simple set, and let 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 reducing to , i.e. such that
Reducibility of to always takes place, but not one solvable set is reducible to .
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=34506
Simple set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Simple_set&oldid=34506
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article