Enumeration

From Wikipedia, the free encyclopedia

You have new messages (last change).
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. Formally, an enumeration of a set S is a mapping from \mathbb{N} (the natural numbers) to S which is surjective (i.e., every element of S is the image of at least one natural number).

It varies between authors and subdisciplines whether this 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 he partial (i.e., the mapping is defined only for some natural numbers). In many applications, these differences are of little importance, because one is often 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.

Enumerations of finite sets obviously require 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 \mathbb{N} to the enumerated set must be computable. The set being enumerated is then called recursively enumberable, referring to the use of recursion theory in formalizations of what it means for the map to be computable. Being recursively enumberable is a weaker condition than being a decidable set.

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

[edit] 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 f(n) is defined then f(m) must be defined for all m < n, then a finite set witt 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.
Retrieved from "http://en.wikipedia.org../../../e/n/u/Enumeration.html"
In other languages