Enumeration

Encyclopedia : E : EN : ENU : Enumeration

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 [\mathbb] (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: \mathbb \to \mathbb] is simply the identity function.
[\mathbb], the set of integers is enumerable by

[f(x) := \begin -(x+1)/2, & \mbox x \mbox \\ x/2, & \mbox x \mbox. \end ]

[f: \mathbb \to \mathbb] 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

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 = . Select any element s in S and assign f(n) = s. Now set 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 : \ \to S]' is an enumeration of S.

The real numbers, [\mathbb] 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 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.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.