Enumerable set

A set arising as the result of performing some constructive generating process. Such a process can be thought of as a process of calculating the values of a certain algorithm with initial data in the form of natural numbers, and therefore, for example, the following exact form can be given to the definition of an enumerable set of natural numbers: A set of natural numbers is called enumerable if there exists a partial recursive function such that this set is its range of values.

Any decidable set of natural numbers is an enumerable set. The converse is false: One can construct an example of an undecidable enumerable set. This fact was established in 1936 by A. Church and is one of the fundamental results in the general theory of algorithms (cf. Algorithms, theory of); it may be (is) used in deriving all known negative results for algorithmic problems (cf. Algorithmic problem). If some set and its complement form an enumerable set, this set is decidable (Post's theorem). The study and classification of enumerable sets form the subject of research in algorithmic set theory.

References

[1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)