Enumeration
From Wikipedia, the free encyclopedia
In mathematics and theoretical computer science, an enumeration of a set is either a procedure for listing all members of the set in some definite sequence, or a count of objects of a specified kind. The two kinds of enumeration often, but not always, overlap.
Contents |
[edit] Enumeration as listing
Formally, an enumeration of a set S (in the sense of a listing) may be defined in either of two ways:
- As 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). This definition is especially suitable to questions of computability and set theory.
- As a mapping from S to an initial segment of the natural numbers. This definition is especially suitable to combinatorial questions and finite sets; then the initial segment is {1,2,...,n} for some n which is the cardinality of S.
In the first definition it varies whether the 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 some applications (especially those concerned with computability of the set S), these differences are of little importance, because one is 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.
Enumeration of finite sets obviously requires 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 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.
[edit] 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:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| f(x) | 0 | −1 | 1 | −2 | 2 | −3 | 3 | −4 | 4 |
- 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.
[edit] 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.
[edit] Enumeration as counting
There are flourishing subareas in many branches of mathematics concerned with enumerating (in the sense of counting) objects of special kinds. For instance, in permutation enumeration and graph enumeration the objective is to count permutations or graphs that meet certain structural conditions.
