Enumeration

A basic concept in the branch of the theory of algorithms called enumeration theory, which investigates general properties of classes of objects numbered by arbitrary constructive objects (cf. Constructive object). Most often, natural numbers appear in the role of the constructive objects that serve as numbers of the elements of the classes in question.

The idea of an enumeration of objects of a non-numerical nature (for example, logical formulas) by natural numbers and the transfer of meaningful assertions about these objects into the domain of the formal arithmetic of natural numbers was first used by K. Gödel in the proof of the Gödel incompleteness theorem of Peano arithmetic. Subsequently these ideas were used for the enumeration of fundamental objects in the theory of algorithms such as Turing machines, partial recursive functions and recursively-enumerable sets (cf. Turing machine; Partial recursive function). The assignment of suitable enumerations to these classes of objects made it possible in many cases to clarify more distinctly the nature of these objects and to make manifest a number of important new properties of them. Thus arose the idea of a systematic use of enumeration of arbitrary sets. In the realization of this idea it was noticed that many known results in the theory of algorithms turn out to be consequences of general regularities in enumeration theory. (About the structure of enumeration theory, the creation of its specific concepts and methods, and the formation of guiding principles in enumeration theory, see [1]–[4].) In particular, it was fruitful to use the language of category theory, which permitted one to look at problems in enumeration theory from a new point of view (see [4]).

An enumerated set is a pair $ \mathfrak A = ( A, \nu ) $, where $ A $ is a countable set and $ \nu $ is a mapping of the set of natural numbers $ \mathbf N $ onto $ A $. The mapping $ \nu $ is called an enumeration of the set $ A $. If $ \nu ( n) = a $, then $ n $ is called the number of the object $ a $ in the enumeration $ \nu $. An enumeration $ \nu _ {1} $ of a set $ A $ reduces to an enumeration $ \nu _ {2} $ of $ A $( the relation of reducibility of enumerations is denoted by $ \leq $) if there is a one-place general recursive function $ f $ such that $ \nu _ {1} ( u) = \nu _ {2} ( f ( n)) $ for all $ n \in \mathbf N $. Two enumerations $ \nu _ {1} $ and $ \nu _ {2} $ of a set $ A $ are called equivalent if $ \nu _ {1} \leq \nu _ {2} $ and $ \nu _ {2} \leq \nu _ {1} $. From the point of view of enumeration theory equivalent enumerations of one and the same set are not distinguished. For this reason the object of study is usually the set $ L ( A) $ of equivalence classes of enumerations of a set $ A $, partially ordered by the relation $ \leq $ of reducibility of enumerations. Often one examines the set $ L ( A, \nu ) $ of equivalence classes of enumerations of $ A $ that can be reduced to $ \nu $. In many cases $ L ( A) $ and $ L ( A, \nu ) $ are a "measure of the complexity" of $ A $.

For the comparison of the enumerations of two sets $ A $ and $ B $ the basic concept is that of a morphism. A morphism of an enumerated set $ \mathfrak A = ( A, \nu _ {1} ) $ into an enumerated set $ \mathfrak B = ( B, \nu _ {2} ) $ is a mapping $ \mu $ from $ A $ into $ B $ for which there is a one-place general recursive function $ f $ such that $ \mu \nu _ {1} ( n) = \nu _ {2} ( f ( n)) $ for all $ n \in \mathbf N $. The set of all morphisms from $ \mathfrak A $ to $ \mathfrak B $ is denoted by $ \mathop{\rm Mor} ( \mathfrak A , \mathfrak B ) $. Many problems in the general theory of algorithms are closely connected with the study of the sets $ \mathop{\rm Mor} $, in particular, with clarifying whether it is possible to impose "good" enumerations on this set.

The category $ \mathfrak N $ of enumerated sets consists of enumerated sets and morphisms. The study of the properties of this category $ \mathfrak N $ is the basic task of enumeration theory. Frequently, the starting point of such a study is the examination of connections between enumerated sets and the most important specific enumerations: the Kleene enumeration $ \phi $ of all one-place partial recursive functions and the Post enumeration $ \pi $ of all recursively-enumerable sets. In the theory of algorithms it is shown that there exists a two-place partial recursive function $ U ( x, y) $ that is universal for the class of all one-place partial recursive functions, that is, is such that for any partial recursive function $ f $ there is a number $ a $ such that $ f ( x) = U ( x, a) $. The Kleene enumeration $ \phi $ is then defined as follows: $ \phi _ {x} ( y) = U ( x, y) $. If $ \pi _ {x} $ denotes the range of values of $ \phi _ {x} $, then one obtains the Post enumeration $ \pi $ of all recursively-enumerable sets.

A fundamental role in the study of $ \mathfrak N $ is played by the concept of a complete enumeration, which was introduced by A.I. Mal'tsev and which, in its most general form, is a synthesis of the main features of the enumerations of Kleene and Post. An enumeration $ \nu $ of a set $ A $ is called complete if among the elements of $ A $ there is a distinguished one, $ a $, such that for any one-place partial recursive function $ f $ there is a one-place general recursive function $ h $ such that

$$ \nu h ( x) = \ \left \{ \begin{array}{ll} \nu f ( x) & \textrm{ if the value of } f ( x) \textrm{ is defined }, \\ a & \textrm{ otherwise } . \\ \end{array} \right .$$

Complete enumerations play the role of "injective" objects in $ \mathfrak N $, and the possibility of having complete enumerations on $ A $ indicates a considerable universality and importance of the class of objects $ A $. In particular, both the Kleene enumeration $ \phi $ of partial recursive functions and the Post enumeration $ \pi $ of recursively-enumerable sets are complete. (In the first case the distinguished element $ a $ is a function that is nowhere defined, and in the second case it is the empty set.) An important trend in research on the category $ \mathfrak N $ is also the selection and study of various kinds of subobjects of enumerated sets (see [4]).

The part of enumeration theory concerned with the study of the Kleene and Post enumerations and their subobjects has been well worked out, so that in these cases the use of the methods and the theory of algorithms is most effective. Here, one first studied the so-called computable enumerations. If $ A $ is, e.g., a family of recursively-enumerable sets, then an enumeration $ \nu $ of this family is said to be computable if the relation $ x \in \nu ( y) $ itself is recursively enumerable. The set of equivalence classes of computable enumerations of a family $ A $ is denoted by $ L ^ {0} ( A) $. This set, like $ L ( A) $, is partially ordered by the reducibility relation $ \leq $. The maximal element of $ L ^ {0} ( A) $, if it exists, is called the principal computable enumeration of $ A $. In particular, the enumerations of Kleene and Post are principal computable for the families $ \phi $( of all one-place partial recursive functions) and $ P $( of all recursively-enumerable sets), respectively. A large amount of work in enumeration theory is devoted to the study of the sets $ L ^ {0} ( \phi ) $ and $ L ^ {0} ( P) $. Here it must be borne in mind that many properties of partial recursive functions and recursively-enumerable sets discovered in the theory of algorithms are in essence reflections of algebraic properties of $ L ^ {0} ( \phi ) $ and $ L ^ {0} ( P) $. For example, the so-called $ m $- step sets, which are studied in the theory of algorithms and play an important role there, fit easily into the scheme of enumeration theory. If one considers the family $ A $ consisting of the two sets $ \phi $ and $ \{ 0 \} $ only, then the $ m $- step sets are none other than $ L ( A) $, and the $ m $- step recursively-enumerable sets are $ L ^ {0} ( A) $. There is a complete algebraic description of the structure of $ L ( A) $ and $ L ^ {0} ( A) $( see [4]).

Let $ A $ be a family of recursively-enumerable sets (for partial recursive functions the concepts to be considered are introduced similarly). The indexing set (or enumerating set) of $ A $ is the set

$$ \theta A = \ \{ {x } : { \pi _ {x} \in A } \} $$

of numbers of recursively-enumerable sets of $ A $ in the Post enumeration. In enumeration theory one studies indexing sets $ \theta A $ for various families $ A $. For example, the Rice–Shapiro theorem gives a description of those families $ A $ for which the set $ \theta A $ is recursively enumerable. Such families are called, in enumeration theory, completely-enumerable classes. There are also descriptions of other forms of subobjects of the Post enumeration: special standard classes, factorizations and retracts. The so-called standard classes play an important role.

A family $ S $ of recursively-enumerable sets is called a standard class if there exists a general recursive function $ f $ such that $ S = \{ \pi ( f ( 0)), \pi ( f ( 1)) ,\dots \} $; if here $ \pi ( x) \in S $, then $ \pi ( x) = \pi ( f ( x)) $. Standard classes are closely connected with complete enumerations. At present (1982) there is no satisfactory description of standard classes. Such a description could throw light on many problems in the theory of algorithms. In enumeration theory, principal, effectively principal and other kinds of subobjects of the Post enumeration have also been considered.

The algorithmic analogue of the concept of an algebraic system, that is, a set with functions and predicates given on it, is that of an indexed, or constructive, algebraic system. The idea is the following. An enumeration is imposed on the set $ A $ in question. Instead of functions and predicates on the objects of $ A $ one considers "translations" of these functions and predicates, operating in the appropriate manner on natural numbers as on the numbers of the objects of $ A $. If one can achieve that these "translations" of functions and predicates are general recursive, then one says that the given algebraic system is constructive. The first systematic study of the theory of constructive algebraic systems was undertaken by Mal'tsev [3].

Two brilliant applications of enumeration theory to problems in the theory of algorithms should be mentioned: the completion of the construction of Myhill's theory about universal objects, and the construction of a theory of computable functionals of finite types (see [4]). The methods and results of enumeration theory can be used in areas close to mathematical logic and the theory of algorithms, in particular in programming. Thus, by means of enumeration theory certain problems of the semantics of programming languages can be solved.

References

[1]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[2]	A.I. Mal'tsev, "Constructive algebras I" Russian Math. Surveys , 16 : 3 (1961) pp. 77–129 ((Also in: A.I. Mal'cev, The metamathematics of algebraic systems, North-Holland, 1971, Chapt. 18)) Uspekhi Mat. Nauk , 16 : 3 (1962) pp. 3–60
[3]	V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[4]	Yu.L. Ershov, "Theorie der Numierungen" , I-II , Deutsch. Verlag Wissenschaft. (1973–1976) (Translated from Russian)

References

[a1]	Yu.I. Manin, "A course in mathematical logic" , Springer (1977) (Translated from Russian)