View source for Recursive set theory

A branch of the theory of recursive functions (cf. [[Recursive function|Recursive function]]) that examines and classifies subsets of natural numbers from the point of view of algorithms, and also studies the structures arising as a result of such a classification. For each subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803401.png" /> of the set of all natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803402.png" />, the following decision problem can be formulated: Is there an algorithm that permits one to decide, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803403.png" />, whether or not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803404.png" /> is a member of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803405.png" />?

The mathematical posing of problems of this kind, and the development of recursive set theory, only became possible in the 1940's after the successful formalization of the intuitive concept of an (algorithmically) [[computable function]]. The range of values of such functions forms the family of recursively-enumerable sets (cf. also [[Enumerable set]]). Sets for which the problem formulated above is solvable are called recursive. In fact, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803406.png" /> is recursive if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803407.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803408.png" /> are both recursively enumerable. The first examples of non-recursive recursively-enumerable sets turned out to be the so-called ''[[creative set]]s'': a recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803409.png" /> is called creative if there is a computable function, defined on the numbers in recursively-enumerable sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034010.png" /> not intersecting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034011.png" /> and giving a number belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034012.png" />. At the same time as creative sets, other non-recursive recursively-enumerable sets were also discovered, in particular the simple ones. A recursively-enumerable set is called simple if it has an infinite complement not containing an infinite recursively-enumerable set. In this way arises the specific problem of classifying decision problems of recursively-enumerable sets. One instrument for such a classification is the concept of reducibility. On an intuitive level, a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034013.png" /> is reducible to a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034014.png" /> if there is an algorithm that would solve the problem of membership of numbers for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034015.png" /> if there is information about membership of certain natural numbers for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034016.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034017.png" /> is in the specific sense  "recursive"  relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034018.png" />, and the ordinary recursive sets are  "recursive"  relative to any set. In its widest sense this reducibility (the detailed formulation of which is quite complex) is called [[Turing reducibility|Turing]] or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034020.png" />-reducibility. By imposing one or more restrictions on the algorithm involved in the concept of reducibility, the definition of other reducibilities may be arrived at: for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034021.png" />-, [[Many-one reducibility|many-one]], <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034022.png" />-, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034023.png" />-reducibilities. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034024.png" /> is [[Many-one reducibility|many-one reducible]] to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034025.png" /> if there is a total computable function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034026.png" /> such that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034027.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034028.png" />,

<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/r/r080/r080340/r08034029.png" /></td> </tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034030.png" /> can be selected injectively, then it is said that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034031.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034033.png" />-reducible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034034.png" />.

A generalization of many-one reducibility is [[truth-table reducibility]] (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034036.png" />-reducibility). A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034037.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034038.png" />-reducible to a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034039.png" /> if there is an algorithm that gives, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034040.png" />, a collection of numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034041.png" /> and a Boolean function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034042.png" /> such that

<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/r/r080/r080340/r08034043.png" /></td> </tr></table>

and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034044.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034046.png" /> in the opposite case. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034047.png" /> is truth-table reducible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034048.png" /> in such a way that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034049.png" /> will be bounded by a certain constant, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034050.png" /> is said to be bounded truth-table reducible (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034052.png" />-reducible) to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034053.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034054.png" /> be a certain reducibility. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034055.png" /> denote that the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034056.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034057.png" />-reducible to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034058.png" />. The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034059.png" /> is a [[Pre-order|pre-order]]. If it is assumed that

<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/r/r080/r080340/r08034060.png" /></td> </tr></table>

then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034061.png" /> will be an equivalence relation, whose individual classes are called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034063.png" />-degrees (and recursively-enumerable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034064.png" />-degrees if the class contains a recursively-enumerable set). Turing degrees are well known in the literature as degrees of undecidability (cf. [[Degree of undecidability|Degree of undecidability]]). The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034065.png" /> generates a partial order of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034066.png" />-degrees. A reducibility <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034067.png" /> is weaker than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034068.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034069.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034070.png" />. Partially ordered sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034071.png" />-degrees for many-one and weaker reducibilities form upper semi-lattices (which is false for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034072.png" />-degrees), having a smallest element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034073.png" />, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034074.png" />-degree of recursive sets. If one restricts to the study of recursively-enumerable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034075.png" />-degrees, they have also a largest element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034076.png" />, called a complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034078.png" />-degree. Recursively-enumerable sets contained in a complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034079.png" />-degree are called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034081.png" />-complete. Minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034083.png" />-degrees are those having only one strictly smaller <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034084.png" />-degree, in fact <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034085.png" />.

The study of reducibilities has been developed in two directions. The first question involved the description of the upper semi-lattices of the degrees relative to the defined reducibility. The famous example of this type of problem is Post's problem [[#References|[1]]]: Is it true that all non-recursive recursively-enumerable sets have the same degree of undecidability? Or, in other words, is it true that the semi-lattice of recursively-enumerable degrees of undecidability consists of only two elements? A negative solution to this problem has been found [[#References|[2]]]. Solutions to such problems on the structure of the upper semi-lattices of recursively-enumerable many-one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034086.png" />-, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034087.png" />-degrees were definite landmarks in the study of reducibilities. At the beginning of the 1960s it was proved that the semi-lattice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034088.png" />-degrees (below semi-lattices of recursively-enumerable degrees are meant) is not a lattice and does not have minimal elements. At that time the existence of minimal many-one degrees was noted, and it was shown that a complete many-one degree is not the least upper bound of two incomparable many-one degrees. Later it became clear that this fact did not hold for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034089.png" />- and weaker reducibilities. Yu.L. Ershov [[#References|[4]]] proved that the upper semi-lattice of many-one degrees is not a lattice and that among some of its elements there are no minimal ones. Similar results, as well as the existence of minimal elements, were obtained for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034090.png" />- and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034091.png" />-degrees [[#References|[5]]]. It was established that the elementary theories of semi-lattices of many-one, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034092.png" />-, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034093.png" />-, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034094.png" />- and several other degrees are mutually different.

The second direction was connected with questions about what are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034095.png" />-degrees, how many of them are there, and how are they distributed in degrees of a relatively weaker reducibility than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034096.png" />? In particular, a complete <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034097.png" />- (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034098.png" />-, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r08034099.png" />-) degree contains a countable number of recursively-enumerable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340100.png" />- (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340101.png" />-, many-one, respectively) degrees. On the other hand, there are non-recursive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340102.png" />- (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340103.png" />-) degrees consisting of one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340104.png" />- (many-one) degree, but each non-recursive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340105.png" />-degree contains at least two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340106.png" />-degrees.

There are other approaches to the study of recursively-enumerable sets, not related to the concept of reducibility. One of them is contained in the following: All recursively-enumerable sets, together with the operations of union and intersection, form a [[Lattice|lattice]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340107.png" />. A property of recursively-enumerable sets is called lattice-theoretic if it is preserved under all automorphisms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340108.png" />. Such, for example, are the properties of  "being recursive" ,  "simple"  or  "maximal" . A recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340109.png" /> is called maximal (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340111.png" />-maximal) if its complement is infinite and cannot be partitioned by a recursively-enumerable set (a recursive set, respectively) into two infinite parts. Examples of classical results connected with the study of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340112.png" /> are the theorems on the existence of maximal sets and on the possibility of partitioning any non-recursive recursively-enumerable set into two non-recursive recursively-enumerable sets (see [[#References|[2]]]), as well as the theorem on the existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340113.png" />-maximal sets without maximal supersets (see [[#References|[3]]]).

The concept of a maximal set arose from the hope that such sets would be not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340114.png" />-complete. This could have been a natural solution to Post's problem. E. Post himself, by imposing increasingly severe restrictions on the complements of recursively-enumerable sets, defined classes of hyper-simple and hyper-hyper-simple sets, and proved that hyper-simple sets cannot be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340115.png" />-complete. Thus, a recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340116.png" /> with an infinite complement is called hyper-simple (hyper-hyper-simple) if there is no computable sequence of mutually non-intersecting finite (recursively-enumerable) sets, each of which also has non-empty intersection with the complement of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340117.png" />. The definition of these classes of sets is not given in lattice-theoretic terms; in fact it has been shown that  "being hyper-simple"  is not a lattice-theoretic property. It has been proved, however, that a recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340118.png" /> with an infinite complement is hyper-hyper-simple if and only if for any recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340119.png" /> there is a recursive set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340120.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340121.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340122.png" />, i.e. the property of  "being hyper-hyper-simple"  proved to be lattice-theoretic. A hyper-hyper-simple set without maximal supersets has been constructed [[#References|[3]]] and it was also proved that for any non-recursive recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340123.png" /> there is an automorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340124.png" /> of the lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340125.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340126.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340127.png" />-complete set [[#References|[6]]]. Thus, the hope of finding a lattice-theoretic property that would not contain recursive and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340128.png" />-complete sets proved to be in vain.

There is also the view (in line with [[#References|[7]]]) according to which recursive set theory must examine properties of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340129.png" /> that are preserved under recursive permutations. In accordance with this, two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340131.png" /> can thus be said to have the same [[Recursive equivalence type|recursive equivalence type]] if there is an injective computable function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340132.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340133.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340134.png" />. Those types of recursive equivalences that do not contain sets with infinite recursively-enumerable subsets are called isols. Once convenient operations of addition and multiplication had been defined for isols, the  "arithmetic"  of isols began to develop.

The study of properties of recursively-enumerable sets and reducibilities is not only linked with other directions in the theory of recursive functions, but it also finds application in logic, model theory and algebra. Recursive set theory has its own methods of research. The most well-known is the so-called [[Priority method|priority method]], by which profound results have been obtained.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  E.L. Post,   "Recursively enumerable sets of positive integers and their decision problems"  ''Bull. Amer. Math. Soc.'' , '''50'''  (1944)  pp. 284–316</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  R.M. Friedberg,   "Three theorems on recursive enumeration: I. Decomposition, II. Maximal set, III. Enumeration without duplication"  ''J. Symbolic Logic'' , '''23'''  (1958)  pp. 309–316</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.H. Lachlan,   "On the lattice of recursively enumerable sets"  ''Trans. Amer. Math. Soc.'' , '''130''' :  1  (1968)  pp. 1–37</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.L. Ershov,   "Hyperhypersimple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340135.png" />-degrees"  ''Algebra and Logic'' , '''8''' :  5  (1969)  pp. 298–315  ''Algebra i Logika'' , '''8''' :  5  (1969)  pp. 523–552</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.N. Degtev,   "Reducibilities of tabular type in the theory of algorithms"  ''Russian Math. Surveys'' , '''34''' :  3  (1979)  pp. 155–192  ''Uspekhi Mat. Nauk'' , '''34''' :  3  (1979)  pp. 137–168</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  R.J. Soare,   "Recursively enumerable sets and degrees"  ''Bull Amer. Math. Soc.'' , '''84''' :  6  (1978)  pp. 1149–1181</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  J.C.E. Dekker,   J. Myhill,   "Recursive equivalence types"  ''Publ. Math. Univ. Calif.'' , '''3''' :  3  (1960)  pp. 67–213</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>



====Comments====
Since algorithms are describable in one language or the other, one can systematically assign natural numbers to descriptions of algorithms simply by enumerating the expressions of the language under consideration according to (first) length and (next) lexicographically (cf. [[Recursion|Recursion]]). Therefore, the classes of computable functions and of recursively-enumerable sets can also be so enumerated: the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340136.png" />-th computable function simply is the function computed by the algorithm to which the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340137.png" /> is assigned, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340138.png" />-th recursively-enumerable set is the range of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340139.png" />-th computable function. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r080340140.png" /> is called the number of the recursively-enumerable set (cf. also [[Recursive function|Recursive function]]).

The (negative) solution of Post's problem mentioned above is usually known as the Muchnik–Friedberg theorem (cf. [[#References|[2]]], [[#References|[a1]]], [[#References|[a4]]]). This is the result that specifically gave rise to the priority methods. They, A.A. Muchnik and R.M. Friedberg, arrived at a solution independently, cf. also [[Degree of undecidability|Degree of undecidability]].

See also [[Algorithmic reducibility|Algorithmic reducibility]]; [[Productive set|Productive set]]; [[Turing machine|Turing machine]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.A. Muchnik,   "On the unsolvability of the reducibility problem in the theory of algorithms"  ''Dokl. Akad. Nauk SSSR'' , '''108''' :  2  (1956)  pp. 194–197  (In Russian)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.I. Soare,   "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer  (1987)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1978)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.M. Friedberg,   "Two recursively enumerable sets of incomparible degrees of unsolvability (solution of Post's problem)"  ''Proc. Nat. Acad. Sci. USA'' , '''43'''  (1957)  pp. 236–238</TD></TR></table>