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, or, equivalently, a means of assigning a unique natural number to each element of the set.

Formally an enumeration of a set S is a subset K of $\backslash mathbb\{N\}$ (the natural numbers) and a function f : K -> S that is a bijection. That is, for every number k in K there is exactly one element s in S such that f(k) = s.

Examples

• The natural numbers are enumerable by the function f(x) = x. In this case $f:\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$ is simply the identity function.
• $\backslash mathbb\{Z\}$, the set of integers is enumerable by

$f:\; \backslash mathbb\{N\}\; \backslash to\; \backslash 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 $f\; :\; \backslash \{1,2,...,n\backslash \}\; \backslash to\; S$' is an enumeration of S.

• The real numbers, $\backslash mathbb\{R\}$ 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 can have many different enumerations. Consider that the set {a,b,c} can be enumerated by f(1) = a, f(2) = b, f(3) = c and also by f(1) = c, f(2) = a, f(3) = b.

• 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.

Combinatorics

Enumeration (Mathematik) | Enumerazione matematica | Enumeratie (stijlfiguur) | 数え上げ