Namespaces
Variants
Actions

Difference between revisions of "Simple set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(define hypersimple, cite Nies (2009))
m (links)
Line 1: Line 1:
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 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
+
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 14: Line 14:
  
 
====Comments====
 
====Comments====
A set is ''hypersimple'' if it is recursively enumerable and its complement is hyperimmune.
+
A set is ''hypersimple'' if it is recursively enumerable and its complement is a [[hyperimmune set]].
  
 
====References====
 
====References====

Revision as of 12:32, 17 January 2016

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$.

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

Comments

A set is hypersimple if it is recursively enumerable and its complement is a hyperimmune set.

References

[a1] Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press (2009). ISBN 978-0-19-923076-1. Zbl 1169.03034
How to Cite This Entry:
Simple set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Simple_set&oldid=34515
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article