Simple set

From Encyclopedia of Mathematics
Revision as of 17:27, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 .


[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:
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article