Enumerable set

2020 Mathematics Subject Classification: Primary: 03D [MSN][ZBL]

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. If some set and its complement each form an enumerable set, then each set is decidable (Post's theorem). The study and classification of enumerable sets form the subject of research in the algorithmic theory of sets.

References

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