enumerate

1 specify individually; "She enumerated the many obstacles she had encountered"; "The doctor recited the list of possible side effects of the drug" [syn: recite, itemize, itemise]

2 determine the number or amount of; "Can you count the books on your shelf?"; "Count your change" [syn: count, number, numerate]

English

Verb

1. To specify each member of a sequence individually in incrementing order.
2. To determine the amount of.

Translations

In mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements (perhaps with repetition). The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working. In more specific settings, this notion of enumeration encompasses the two different types of listing: one where there is a natural ordering and one where the ordering is more nebulous. These two different kinds of enumerations correspond to a procedure for listing all members of the set in some definite sequence, or a count of objects of a specified kind, respectively. While the two kinds of enumeration often overlap in most natural situations, they can assume very different meanings in certain contexts.

Enumeration as counting

Formally, the most inclusive definition of an enumeration of a set S is any surjection from an arbitrary index set I onto S. In this broad context, every set S can be trivially enumerated by the identity function from S onto itself. If one does not assume the Axiom of Choice or one of its variants, S need not have any well-ordering. Even if one does assume Choice, S need not have any natural well-ordering.

This general definition therefore lends itself to a counting notion where we are interested in "how many" rather than "in what order." In practice, this broad meaning of enumerable is often used to compare the relative sizes or cardinalities of different sets. If one works in ZF (Zermelo-Fraenkel set theory without choice), one may want to impose the additional restriction that an enumeration must also be injective (without repetition) since in this theory, the existence of a surjection from I onto S need not imply the existence of an injection from S into I.

Enumeration as 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 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.

Enumeration in countable vs. uncountable context

The most common use of enumeration occurs in the context where infinite sets are separated into those that are countable and those that are not. In this case, an enumeration is merely an enumeration with domain ω. This definition can also be stated as follows:

• As a surjective mapping from \mathbb (the natural numbers) to S (i.e., every element of S is the image of at least one natural number). This definition is especially suitable to questions of computability and elementary set theory.

We may also define it differently when working with finite sets. In this case an enumeration may be defined as follows:

• As a bijective mapping from S to an initial segment of the natural numbers. This definition is especially suitable to combinatorial questions and finite sets; then the initial segment is for some n which is the cardinality of S.

In the first definition it varies whether the 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 be partial (i.e., the mapping is defined only for some natural numbers). In some applications (especially those concerned with computability of the set S), these differences are of little importance, because one is 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.

Enumeration of finite sets obviously requires that either non-injectivity or partiality is accepted, and in contexts where finite sets may appear one or both of these are inevitably present.

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:

block out, book, calendar, call off, call over, call the roll, catalog, census, count, detail, enroll, enter, file, foliate, identify, impanel, index, inventory, itemize, keep score, list, measure, mention, number, numerate, outline, page, paginate, parse, particularize, pigeonhole, poll, post, program, quantify, quantize, recite, recount, register, relate, resolve, run over, scan, schedule, schematize, score, specialize, specify, tabulate, tale, tally, tell, tell off, tick off