Namespaces
Variants
Actions

Difference between revisions of "Enumeration"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
e0358001.png
 +
$#A+1 = 116 n = 0
 +
$#C+1 = 116 : ~/encyclopedia/old_files/data/E035/E.0305800 Enumeration
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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|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.
 
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|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|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|Turing machine]]; [[Partial recursive function|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 [[#References|[1]]]–[[#References|[4]]].) In particular, it was fruitful to use the language of [[Category|category]] theory, which permitted one to look at problems in enumeration theory from a new point of view (see [[#References|[4]]]).
 
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|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|Turing machine]]; [[Partial recursive function|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 [[#References|[1]]]–[[#References|[4]]].) In particular, it was fruitful to use the language of [[Category|category]] theory, which permitted one to look at problems in enumeration theory from a new point of view (see [[#References|[4]]]).
  
An enumerated set is a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358001.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358002.png" /> is a countable set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358003.png" /> is a mapping of the set of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358004.png" /> onto <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358005.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358006.png" /> is called an enumeration of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358007.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358008.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e0358009.png" /> is called the number of the object <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580010.png" /> in the enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580011.png" />. An enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580012.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580013.png" /> reduces to an enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580014.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580015.png" /> (the relation of reducibility of enumerations is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580016.png" />) if there is a one-place general recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580017.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580018.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580019.png" />. Two enumerations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580021.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580022.png" /> are called equivalent if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580024.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580025.png" /> of equivalence classes of enumerations of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580026.png" />, partially ordered by the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580027.png" /> of reducibility of enumerations. Often one examines the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580028.png" /> of equivalence classes of enumerations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580029.png" /> that can be reduced to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580030.png" />. In many cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580032.png" /> are a  "measure of the complexity"  of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580033.png" />.
+
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.
  
For the comparison of the enumerations of two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580035.png" /> the basic concept is that of a morphism. A morphism of an enumerated set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580036.png" /> into an enumerated set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580037.png" /> is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580038.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580039.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580040.png" /> for which there is a one-place general recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580041.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580042.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580043.png" />. The set of all morphisms from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580044.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580045.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580046.png" />. Many problems in the general theory of algorithms are closely connected with the study of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580047.png" />, 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.
  
The category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580048.png" /> of enumerated sets consists of enumerated sets and morphisms. The study of the properties of this category <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580049.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580050.png" /> of all one-place partial recursive functions and the Post enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580051.png" /> of all recursively-enumerable sets. In the theory of algorithms it is shown that there exists a two-place partial recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580052.png" /> that is universal for the class of all one-place partial recursive functions, that is, is such that for any partial recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580053.png" /> there is a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580054.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580055.png" />. The Kleene enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580056.png" /> is then defined as follows: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580057.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580058.png" /> denotes the range of values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580059.png" />, then one obtains the Post enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580060.png" /> 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
  
A fundamental role in the study of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580061.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580062.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580063.png" /> is called complete if among the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580064.png" /> there is a distinguished one, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580065.png" />, such that for any one-place partial recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580066.png" /> there is a one-place general recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580067.png" /> such that
+
$$
 +
\nu h ( x)  = \
 +
\left \{
  
<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/e/e035/e035800/e03580068.png" /></td> </tr></table>
+
\begin{array}{ll}
 +
\nu f ( x)  & \textrm{ if  the  value 
 +
of  }  f ( x)  \textrm{ is  defined  },  \\
 +
a  & \textrm{ otherwise } . \\
 +
\end{array}
  
Complete enumerations play the role of "injective"  objects in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580069.png" />, and the possibility of having complete enumerations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580070.png" /> indicates a considerable universality and importance of the class of objects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580071.png" />. In particular, both the Kleene enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580072.png" /> of partial recursive functions and the Post enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580073.png" /> of recursively-enumerable sets are complete. (In the first case the distinguished element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580074.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580075.png" /> is also the selection and study of various kinds of subobjects of enumerated sets (see [[#References|[4]]]).
+
  \right .$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580076.png" /> is, e.g., a family of recursively-enumerable sets, then an enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580077.png" /> of this family is said to be computable if the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580078.png" /> itself is recursively enumerable. The set of equivalence classes of computable enumerations of a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580079.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580080.png" />. This set, like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580081.png" />, is partially ordered by the reducibility relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580082.png" />. The maximal element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580083.png" />, if it exists, is called the principal computable enumeration of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580084.png" />. In particular, the enumerations of Kleene and Post are principal computable for the families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580085.png" /> (of all one-place partial recursive functions) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580086.png" /> (of all recursively-enumerable sets), respectively. A large amount of work in enumeration theory is devoted to the study of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580087.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580088.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580090.png" />. For example, the so-called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580091.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580092.png" /> consisting of the two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580093.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580094.png" /> only, then the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580096.png" />-step sets are none other than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580097.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e03580099.png" />-step recursively-enumerable sets are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800100.png" />. There is a complete algebraic description of the structure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800101.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800102.png" /> (see [[#References|[4]]]).
+
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 [[#References|[4]]]).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800103.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800104.png" /> is the set
+
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 [[#References|[4]]]).
  
<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/e/e035/e035800/e035800105.png" /></td> </tr></table>
+
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
  
of numbers of recursively-enumerable sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800106.png" /> in the Post enumeration. In enumeration theory one studies indexing sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800107.png" /> for various families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800108.png" />. For example, the Rice–Shapiro theorem gives a description of those families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800109.png" /> for which the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800110.png" /> 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.
+
$$
 +
\theta A  = \
 +
\{ {x } : {
 +
\pi _ {x} \in A } \}
 +
$$
  
A family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800111.png" /> of recursively-enumerable sets is called a standard class if there exists a general recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800112.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800113.png" />; if here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800114.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800115.png" />. 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.
+
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.
  
The algorithmic analogue of the concept of an [[Algebraic system|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800116.png" /> in question. Instead of functions and predicates on the objects of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800117.png" /> one considers  "translations"  of these functions and predicates, operating in the appropriate manner on natural numbers as on the numbers of the objects of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035800/e035800118.png" />. 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 [[#References|[3]]].
+
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|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 [[#References|[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 [[#References|[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.
 
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 [[#References|[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.
Line 31: Line 170:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.L. Ershov,  "Theorie der Numierungen" , '''I-II''' , Deutsch. Verlag Wissenschaft.  (1973–1976)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  Yu.L. Ershov,  "Theorie der Numierungen" , '''I-II''' , Deutsch. Verlag Wissenschaft.  (1973–1976)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  Yu.I. Manin,  "A course in mathematical logic" , Springer  (1977)  (Translated from Russian)</TD></TR></table>

Revision as of 19:37, 5 June 2020


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)

Comments

References

[a1] Yu.I. Manin, "A course in mathematical logic" , Springer (1977) (Translated from Russian)
How to Cite This Entry:
Enumeration. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumeration&oldid=46830
This article was adapted from an original article by I.A. Lavrov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article