Difference between revisions of "Recursive set theory"
m (links) |
m (link) |
||
Line 1: | Line 1: | ||
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" />? | 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|computable function]]. The range of values of such functions forms the family of recursively-enumerable sets (cf. also [[Enumerable set|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 sets: a recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803409.png" /> is called creative (cf. also [[Creative set|Creative set]]) 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 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" />, | + | 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|computable function]]. The range of values of such functions forms the family of recursively-enumerable sets (cf. also [[Enumerable set|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 sets: a recursively-enumerable set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080340/r0803409.png" /> is called creative (cf. also [[Creative set|Creative set]]) 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> | <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> |
Revision as of 06:46, 28 September 2016
A branch of the theory of recursive functions (cf. 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 of the set of all natural numbers
, the following decision problem can be formulated: Is there an algorithm that permits one to decide, for any
, whether or not
is a member of
?
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, is recursive if and only if
and
are both recursively enumerable. The first examples of non-recursive recursively-enumerable sets turned out to be the so-called creative sets: a recursively-enumerable set
is called creative (cf. also Creative set) if there is a computable function, defined on the numbers in recursively-enumerable sets
not intersecting
and giving a number belonging to
. 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
is reducible to a set
if there is an algorithm that would solve the problem of membership of numbers for
if there is information about membership of certain natural numbers for
. In this case
is in the specific sense "recursive" relative to
, 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 or
-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,
-, many-one,
-, or
-reducibilities. In particular,
is many-one reducible to
if there is a total computable function
such that for all
in
,
![]() |
If can be selected injectively, then it is said that
is
-reducible to
.
A generalization of many-one reducibility is truth-table reducibility (-reducibility). A set
is
-reducible to a set
if there is an algorithm that gives, for each
, a collection of numbers
and a Boolean function
such that
![]() |
and if
and
in the opposite case. If
is truth-table reducible to
in such a way that
will be bounded by a certain constant, then
is said to be bounded truth-table reducible (
-reducible) to
. Let
be a certain reducibility. Let
denote that the set
is
-reducible to
. The relation
is a pre-order. If it is assumed that
![]() |
then will be an equivalence relation, whose individual classes are called
-degrees (and recursively-enumerable
-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). The relation
generates a partial order of all
-degrees. A reducibility
is weaker than
if
implies
. Partially ordered sets of
-degrees for many-one and weaker reducibilities form upper semi-lattices (which is false for
-degrees), having a smallest element
, the
-degree of recursive sets. If one restricts to the study of recursively-enumerable
-degrees, they have also a largest element
, called a complete
-degree. Recursively-enumerable sets contained in a complete
-degree are called
-complete. Minimal
-degrees are those having only one strictly smaller
-degree, in fact
.
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 [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 [2]. Solutions to such problems on the structure of the upper semi-lattices of recursively-enumerable many-one -, and
-degrees were definite landmarks in the study of reducibilities. At the beginning of the 1960s it was proved that the semi-lattice of
-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
- and weaker reducibilities. Yu.L. Ershov [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
- and
-degrees [5]. It was established that the elementary theories of semi-lattices of many-one,
-,
-,
- and several other degrees are mutually different.
The second direction was connected with questions about what are -degrees, how many of them are there, and how are they distributed in degrees of a relatively weaker reducibility than
? In particular, a complete
- (
-,
-) degree contains a countable number of recursively-enumerable
- (
-, many-one, respectively) degrees. On the other hand, there are non-recursive
- (
-) degrees consisting of one
- (many-one) degree, but each non-recursive
-degree contains at least two
-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 . A property of recursively-enumerable sets is called lattice-theoretic if it is preserved under all automorphisms of
. Such, for example, are the properties of "being recursive" , "simple" or "maximal" . A recursively-enumerable set
is called maximal (
-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
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 [2]), as well as the theorem on the existence of
-maximal sets without maximal supersets (see [3]).
The concept of a maximal set arose from the hope that such sets would be not -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
-complete. Thus, a recursively-enumerable set
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
. 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
with an infinite complement is hyper-hyper-simple if and only if for any recursively-enumerable set
there is a recursive set
such that
and
, 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 [3] and it was also proved that for any non-recursive recursively-enumerable set
there is an automorphism
of the lattice
such that
is a
-complete set [6]. Thus, the hope of finding a lattice-theoretic property that would not contain recursive and
-complete sets proved to be in vain.
There is also the view (in line with [7]) according to which recursive set theory must examine properties of subsets of that are preserved under recursive permutations. In accordance with this, two sets
and
can thus be said to have the same recursive equivalence type if there is an injective computable function
such that
and
. 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, by which profound results have been obtained.
References
[1] | E.L. Post, "Recursively enumerable sets of positive integers and their decision problems" Bull. Amer. Math. Soc. , 50 (1944) pp. 284–316 |
[2] | 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 |
[3] | A.H. Lachlan, "On the lattice of recursively enumerable sets" Trans. Amer. Math. Soc. , 130 : 1 (1968) pp. 1–37 |
[4] | Yu.L. Ershov, "Hyperhypersimple ![]() |
[5] | 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 |
[6] | R.J. Soare, "Recursively enumerable sets and degrees" Bull Amer. Math. Soc. , 84 : 6 (1978) pp. 1149–1181 |
[7] | J.C.E. Dekker, J. Myhill, "Recursive equivalence types" Publ. Math. Univ. Calif. , 3 : 3 (1960) pp. 67–213 |
[8] | A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian) |
[9] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165 |
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). Therefore, the classes of computable functions and of recursively-enumerable sets can also be so enumerated: the -th computable function simply is the function computed by the algorithm to which the number
is assigned, and the
-th recursively-enumerable set is the range of the
-th computable function. Here
is called the number of the recursively-enumerable set (cf. also Recursive function).
The (negative) solution of Post's problem mentioned above is usually known as the Muchnik–Friedberg theorem (cf. [2], [a1], [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.
See also Algorithmic reducibility; Productive set; Turing machine.
References
[a1] | 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) |
[a2] | R.I. Soare, "Recursively enumerable sets and degrees, a study of computable functions and generated sets" , Springer (1987) |
[a3] | J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1978) |
[a4] | 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 |
Recursive set theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recursive_set_theory&oldid=39334