Enumeration
From Free net encyclopedia
Template:Otheruses4 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 <math>\mathbb{N}</math> (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 <math>f: \mathbb{N} \to \mathbb{N}</math> is simply the identity function.
- <math>\mathbb{Z}</math>, the set of integers is enumerable by
- <math>f(x) := \begin{cases} -(x+1)/2, & \mbox{if x is odd} \\ x/2, & \mbox{if x is even}. \end{cases} </math>
<math>f: \mathbb{N} \to \mathbb{Z}</math> is a bijection since every natural number corresponds to exactly one integer. The following table demonstrates the first five values of this enumeration:
| x | f(x) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | -1 |
| 3 | 2 |
| 4 | -2 |
- 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 <math>f : \{1,2,...,n\} \to S</math>' is an enumeration of S.
- The real numbers, <math>\mathbb{R}</math> have no enumeration as proved by Cantor's diagonalization argument.
Properties
- There exists an enumeration for a set iff 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.de:Enumeration (Mathematik)
it:Enumerazione matematica nl:Enumeratie (stijlfiguur) ja:数え上げ