In mathematics and theoretical computer science, an enumeration of a set is a procedure for listing all members of the set in some definite sequence. Formally, an enumeration of a set S is a mapping from (the natural numbers) to S which is surjective (i.e., every element of S is the image of at least one natural number). Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ...

It varies between authors and subdisciplines whether this mapping is also required to be injective (i.e., every element of S is the image of exactly one natural number), and/or allowed to be partial (i.e., the mapping is defined only for some natural numbers). In many applications, these differences are of little importance, because one is often concerned only with the mere existence of some enumeration, and an enumeration according to a liberal definition will generally imply that enumerations satisfying stricter requirements also exist. In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ... In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ...

Enumerations of finite sets obviously require that either non-injectivity or partiality is accepted, and in contexts where finite sets may appear one or both of these are inevitably present. In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...

In computer science one often considers enumerations with the added requirement that the mapping from to the enumerated set must be computable. The set being enumerated is then called recursively enumerable, referring to the use of recursion theory in formalizations of what it means for the map to be computable. Being recursively enumerable is a weaker condition than being a decidable set. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... It has been suggested that recursive function be merged into this article or section. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. ...

Examples

• The natural numbers are enumerable by the function f(x) = x. In this case is simply the identity function.
• , the set of integers is enumerable by

is a bijection since every natural number corresponds to exactly one integer. The following table gives the first few values of this enumeration: An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ... The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ...

• All finite sets are enumerable. Let S be a finite set with n elements and let K = {1,2,...,n}. Select any element s in S and assign f(n) = s. Now set S' = S - {s} (where - denotes set difference). Select any element s' in S' and assign f(n-1) = s'. Continue this process until all elements of the set have been assigned a natural number. Then is an enumeration of S.

• The real numbers, have no enumeration as proved by Cantor's diagonalization argument.

In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... Cantors diagonal argument, also called the diagonalization argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. ...

Properties

• There exists an enumeration for a set if and only if the set is countable.

• If a set is enumerable it will have an uncountable infinity of different enumerations, except in the degenerate cases of the empty set or (depending on the precise definition) sets with one element. However, if one requires enumerations to be injective and allows only a limited form of partiality such that if f(n) is defined then f(m) must be defined for all m < n, then a finite set of N elements has exactly N! enumerations.

• An enumeration of a set gives a total order of that set. Although the order may have little to do with the underlying set it is useful when some order of the set is necessary.