Namespaces
Variants
Actions

Enumerable set

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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)
How to Cite This Entry:
Enumerable set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumerable_set&oldid=35234
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article