Everything about Enumeration totally explained
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's 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're 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:
