Enumerated set

The enumeration set ( effectively enumerable , recursively enumerable , semi-resolvable set ^[1] ) is the set of constructive objects (for example, natural numbers ), all elements of which can be obtained with the help of some algorithm . The addition of an enumerable set is called a corcursively enumerable ^[2] . Every enumerable set is arithmetic . A corcursively enumerable set may not be enumerable, but it is always arithmetic. Enumerated sets correspond to level $\Sigma _{1}^{0}$ ${\ displaystyle \ Sigma _ {1} ^ {0}}$ $\ Sigma _ {1} ^ {0}$ arithmetic hierarchy , and korekursively enumerable hierarchy - level $\Pi _{1}^{0}.$ ${\ displaystyle \ Pi _ {1} ^ {0}.}$ $\ Pi _ {1} ^ {0}.$

Every soluble set is enumerable. An enumerable set is soluble if and only if its complement is also enumerated. In other words, a set is soluble if and only if it is both enumerated and corjectively enumerable. A subset of the enumeration set may not be enumerable (and may even not be arithmetic).

The collection of all enumerable subsets $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ is a countable set , and the collection of all non-enumerable subsets $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ - uncountable .

Content

Variants of definition

Different formal definitions of the notion of an enumerable set that turn out to be equivalent correspond to different formalizations of the idea of the algorithm . Thus, based on the concept of a recursive function, enumerable sets of natural numbers can be defined as images of partially recursive functions of one variable (therefore, enumerable sets of natural numbers are sometimes called “recursively enumerable sets”). Similarly, enumerable sets of words in some alphabet A can be entered as sets of results of Turing machines with external alphabet A , or as sets of results of normal algorithms on alphabet A being words in alphabet A.

In the theory of algorithms, it is proved that the enumeration sets can serve as the ranges of values of the algorithms, and only they. This allows us to introduce another equivalent way to define the concept of an enumerable set. Thus, the enumerable sets of natural numbers can be considered the range of values of recursive functions, the sets of words - the areas of applicability of Turing machines or normal algorithms with the corresponding alphabets.

Examples

An empty set is enumerable.
Any soluble set (in particular, any finite set ) is enumerable.
The many Turing machine numbers that stop at the empty entrance are also enumerable (although not solvable , since its addition is not enumerable).
The projection of the enumeration is enumerable.
The union and intersection of a finite number of enumerable sets are also enumerable.
The set of natural numbers whose decimal notation appears as a substring in the decimal notation of the number π is enumerable, and in the case of the normality of the number π, it is even soluble in a trivial way (the whole set of natural numbers).
The set of rational numbers less than the Haitin constant Ω is enumerable but not solvable.
But the set of rational numbers greater than the Haitin constant Ω is not enumerable (although arithmetically and corjectively enumerable).
The set of provable assertions in first-order arithmetic is enumerable.
But the set of true assertions in first-order arithmetic is neither enumerable nor korekursively enumerable (and is not even arithmetic, which constitutes the assertion of Tarski's theorem on the inexpressible truth in arithmetic).

Diophantine

Any enumerable set of integers (or tuples of integers) has a Diophantine representation , that is, it is a projection of the set of all solutions of some algebraic Diophantine equation.

This means, in particular, that any enumerable set coincides with the set of positive values that are taken for integer parameters by some polynomial with integer coefficients. This result was established by Yuri Matiyasevich .

Notes

↑ A. E. Pentus, M. R. Pentus, Mathematical Theory of Formal Languages, Lecture 14: Algorithmic Problems // Intuit.ru, 09.07.2007
↑ Barways, Kenneth John. Reference book on mathematical logic. Part 3: recursion theory. - M .: Science, 1982.

Literature

Rogers H. Theory of recursive functions and effective computability . - M .: Mir, 1972.

[1] A. E. Pentus, M. R. Pentus, Mathematical Theory of Formal Languages, Lecture 14: Algorithmic Problems // Intuit.ru, 09.07.2007

[2] Barways, Kenneth John. Reference book on mathematical logic. Part 3: recursion theory. - M .: Science, 1982.