Enumeration

From Encyclopedia Jr, free information reference for Kids

This article is about mathematical enumerations . For enumeration types in programming languages, see enumerated type.

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

[edit] Examples

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

$f(x):= \begin{cases} -(x+1)/2, & \mbox{if } x \mbox{ is odd} \\ x/2, & \mbox{if } x \mbox{ is even}. \end{cases}$

$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:

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

The real numbers, $\mathbb{R}$ 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 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. In fact, a finite set of n elements has n! distinct 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.

Category: Combinatorics