enumeration

Uses your system voice; voice and rate in settings.

Q3589010Snapshot

≈ 5 min read

Names in other languages

  • sqEnumeracioni
  • Englishenumeration
  • Françaisénumération
  • slenumeracija
  • العربيةتعديد

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (for example, whether the set must be finite, or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem. Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, ... for the set of positive integers), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering. In some contexts, such as enumerative combinatorics, the term enumeration is used more in the sense of counting – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements.

An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (for example, whether the set must be finite, or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem.

Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, ... for the set of positive integers), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering.

In some contexts, such as enumerative combinatorics, the term enumeration is used more in the sense of counting – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements. enum Level { LOW, MEDIUM, HIGH } C++ enum Color { RED, GREEN, BLUE }; // RED=0, GREEN=1, BLUE=2 Color myColor = RED;

Listing

When an enumeration is used in an ordered list context, we impose some sort of ordering structure requirement on the index set. While we can make the requirements on the ordering quite lax in order to allow for great generality, the most natural and common prerequisite is that the index set be well-ordered. According to this characterization, an ordered enumeration is defined to be a surjection (an onto relationship) with a well-ordered domain. This definition is natural in the sense that a given well-ordering on the index set provides a unique way to list the next element given a partial enumeration.

Countable vs. uncountable

Unless otherwise specified, an enumeration is done by means of natural numbers. That is, an enumeration of a set is a bijective function from the natural numbers \mathbb{N} or an initial segment of the natural numbers to . A set is countable if it can be enumerated, that is, if there exists an enumeration of it. Otherwise, it is uncountable. For example, the set of the real numbers is uncountable. A set is finite if it can be enumerated by means of a proper initial segment of the natural numbers, in which case, its cardinality is .

The empty set is finite, as it can be enumerated by means of the empty initial segment of the natural numbers. The term set is sometimes used for countable sets. However it is also often used for computably enumerable sets, which are the countable sets for which an enumeration function can be computed with an algorithm. For avoiding to distinguish between finite and countably infinite set, it is often useful to use another definition that is equivalent: A set is countable if and only if there exists an injective function from it into the natural numbers.

The natural numbers are enumerable by the function f(x) = x. In this case f\colon\mathbb{N} \to \mathbb{N} is simply the identity function. \mathbb{Z} , the set of integers is enumerable by f(x):=\frac {1-(-1)^x\,(2\,x+1)} 4 f\colon\mathbb{N}_0 \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: All (non empty) finite sets are enumerable. Let S be a finite set with n > 0 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'  ∈ S' and assign f(n − 1) = s' . Continue this process until all elements of the set have been assigned a natural number. Then f: K \to S is an enumeration of S. The real numbers have no countable enumeration as proved by Cantor's diagonal argument and Cantor's first uncountability proof.

See also

Ordinal number Enumerative definition Sequence

References

External links

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369012885 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enumeration-414167-4573caa5da077d7f · hash 4573caa5da077d7f6bb840dcc315637bbd341a38d8871533525fc2a15ca061b4 · captured 1786522081.0 · version history

Cite this page as: encyclopegia.org, “enumeration”, snapshot enumeration-414167-4573caa5da077d7f. https://encyclopegia.org/a/enumeration

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.