Namespaces
Variants
Actions

Difference between revisions of "Simple set"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
Line 1: Line 1:
A recursively-enumerable set of natural numbers (cf. [[Enumerable set|Enumerable set]]) whose complement is an [[Immune set|immune set]]. Simple sets are intermediate in the sense of so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853101.png" />-reducibility (cf. [[Recursive set theory|Recursive set theory]]) between solvable sets and creative sets. The latter are the largest among the enumerable sets in the sense of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853102.png" />-reducibility. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853103.png" /> be an arbitrary simple set, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853104.png" /> 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|general recursive function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853105.png" /> reducing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853106.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853107.png" />, i.e. such that
+
A recursively-enumerable set of natural numbers (cf. [[Enumerable set|Enumerable set]]) whose complement is an [[Immune set|immune set]]. Simple sets are intermediate in the sense of so-called $m$-reducibility (cf. [[Recursive set theory|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 \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853108.png" /></td> </tr></table>
+
Reducibility of $P$ to $K$ always takes place, but not one solvable set is reducible to $K$.
 
 
Reducibility of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s0853109.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s08531010.png" /> always takes place, but not one solvable set is reducible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085310/s08531011.png" />.
 
  
 
====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></table>
 +
 +
{{TEX|done}}

Revision as of 07:56, 15 November 2014

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 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
How to Cite This Entry:
Simple set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Simple_set&oldid=18731
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article