Enumeration

Look up Enumeration in
Wiktionary, the free dictionary.

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.

Enumeration as listing

Formally, an enumeration of a set S (in the sense of a listing) may be defined in either of two the ways:

• As a surjective mapping from Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{N}

(the natural numbers) to S  (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 bijective 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{N}

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.

Examples

• The natural numbers are enumerable by the function f(x) = x. In this case Failed to parse (Missing texvc executable; please see math/README to configure.): f: \mathbb{N} \to \mathbb{N}

is simply the identity function.

• Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{Z}

, the set of integers is enumerable by

Failed to parse (Missing texvc executable; please see math/README to configure.): f(x):= \begin{cases} -(x+1)/2, & \mbox{if } x \mbox{ is odd} \\ x/2, & \mbox{if } x \mbox{ is even}. \end{cases}

Failed to parse (Missing texvc executable; please see math/README to configure.): f: \mathbb{N} \to \mathbb{Z}

is a bijection since every natural number corresponds to exactly one integer.  The following table gives the first few values of this enumeration:

• 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 Failed to parse (Missing texvc executable; please see math/README to configure.): f: \{1,2,...,n\} \to S

is an enumeration of S.

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

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 Failed to parse (Missing texvc executable; please see math/README to configure.): f(n)

is defined then Failed to parse (Missing texvc executable; please see math/README to configure.): f(m)
must be defined for all Failed to parse (Missing texvc executable; please see math/README to configure.): 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.

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.

See also

• Ordinal numberde:Enumeration (Mathematik)

it:Enumerazione (matematica) ja:数え上げ pt:Enumeração