# Enumeration

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

*enumeration*is used more in the sense of

*counting*

## Combinatorics

In combinatorics, enumeration means counting, i.e., determining the exact number of elements of finite sets, usually grouped into infinite families, such as the family of sets each consisting of all permutations of some finite set. There are flourishing subareas in many branches of mathematics concerned with enumerating in this sense objects of special kinds. For instance, in *partition enumeration* and *graph enumeration* the objective is to count partitions or graphs that meet certain conditions.

## Set theory

In set theory, the notion of enumeration has a broader sense, and does not require the set being enumerated to be finite.

### Listing

When an enumeration is used in an

### Countable vs. uncountable

Unless otherwise specified, an enumeration is done by means of

*n*} of the natural numbers to S.

A set is

A set is finite if it can be enumerated by means of a proper initial segment {1, ..., *n*} of the natural numbers, in which case, its cardinality is n. The empty set is finite, as it can be enumerated by means of the empty initial segment of the natural numbers.

The term **enumerable 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 S is countable if and only if there exists an injective function from it into the natural numbers.

#### Examples

- The natural numbers are enumerable by the function
*f*(*x*) =*x*. In this case is simply the identity function. - , the set of integersis enumerable by 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 (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 − denotesset 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 is an enumeration of*S*. - The Cantor's first uncountability proof.

#### Properties

- There exists an enumeration for a set (in this sense) if and only if the set is countable.
- If a set is enumerable it will have an uncountableinfinity 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 of*N*elements has exactly*N*! enumerations. - An enumeration
*e*of a set*S*with domain induces a well-order ≤ on that set defined by*s*≤*t*if and only if . Although the order may have little to do with the underlying set, it is useful when some order of the set is necessary.

### Ordinals

In

*S*. The more restrictive version of enumeration mentioned before is the special case where α is a finite ordinal or the first limit ordinal ω. This more generalized version extends the aforementioned definition to encompass transfinite

Under this definition, the first uncountable ordinal can be enumerated by the identity function on so that these two notions do **not** coincide. More generally, it is a theorem of ZF that any

Since

### Comparison of cardinalities

Formally, the most inclusive definition of an enumeration of a set *S* is any

*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 enumeration is often used to compare the relative sizes or

*S*into

*I*.

## Computability and complexity theory

In computability theory one often considers countable enumerations with the added requirement that the mapping from (set of all natural numbers) to the enumerated set must be

In this sense, a subset of the natural numbers is

Furthermore, this characterization illustrates a place where the ordering of the listing is important. There exists a computable enumeration of the halting set, but **not** one that lists the elements in an increasing ordering. If there were one, then the halting set would be

The notion of enumeration has also been studied from the point of view of computational complexity theory for various tasks in the context of enumeration algorithms.

## See also

## References

- ISBN 3-540-44085-2.

## External links

- The dictionary definition of
*enumeration*at Wiktionary