# Enumeration

In

mathematics and theoreticalcomputer science , the broadest and most abstract definition of an**enumeration**of a set is an exact listing of all of itselements (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 anatural 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 definitesequence , 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 arbitraryindex set "I" onto "S". In this broad context, every set "S" can be trivially enumerated by theidentity function from "S" onto itself. If one does**not**assume theAxiom of Choice or one of its variants, "S" need not have anywell-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 beinjective (without repetition) since in this theory, the existence of a surjection from "I" onto "S" need not imply the existence of aninjection 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 bewell-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\{N\}$ (thenatural number s) to "S" (i.e., every element of "S" is the image of at least one natural number). This definition is especially suitable to questions ofcomputability and elementaryset 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 {1,2,...,"n"} for some "n" which is thecardinality 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\{N\}\; o\; mathbb\{N\}$ is simply the

identity function .

* $mathbb\{Z\}$, the set ofintegers is enumerable by:: $f(x):=\; egin\{cases\}\; -(x+1)/2,\; mbox\{if\; \}\; x\; mbox\{\; is\; odd\}\; \backslash \; x/2,\; mbox\{if\; \}\; x\; mbox\{\; is\; even\}.\; end\{cases\}$

$f:\; mathbb\{N\}\; o\; 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:

{| cellpadding="8"! "x"

0

1

2

3

4

5

6

7

8

-! "ƒ"("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 "ƒ"("n") = "s". Now set "S

' " = "S" − {"s"} (where − denotesset difference ). Select any element "s' " ∈ "S' " and assign "ƒ"("n" − 1) = "s". Continue this process until all elements of the set have been assigned a natural number. Then $f:\; \{1,2,dots,n\}\; o\; S$ is an enumeration of "S".* The

real number s have no countable enumeration as proved byCantor's diagonalization argument .**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

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 "ƒ"("n") is defined then "ƒ"("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 $mathbb\{N\}$ induces a

well-order ≤ on that set defined by "s" ≤ "t" if and only if min "e"^{−1}("s") ≤ min "e"^{−1}("t"). Although the order may have little to do with the underlying set, it is useful when some order of the set is necessary.**Computable enumeration**In

computability theory one often considers countable enumerations with the added requirement that the mapping from $mathbb\{N\}$ to the enumerated set must be computable. The set being enumerated is then calledrecursively enumerable (or computably enumerable in more contemporary language), referring to the use ofrecursion theory in formalizations of what it means for the map to be computable.In this sense, a subset of Natural numbers is

computably enumerable if it is the range of a computable function. In this context, enumerable may be used to mean computably enumerable. However, these definitions characterize distinct classes since there are uncountably many subsets of Natural numbers that can be enumerated by an arbitrary function with domain ω and only countably many computable functions. A specific example of a set with an enumeration but not a computable enumeration is the complement of the halting set.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 bedecidable , which is provably false. In general, being recursively enumerable is a weaker condition than being adecidable set .**Ordinal enumeration**In

set theory , there is a more general notion of an enumeration than the characterization requiring the domain of the listing function to be aninitial segment of the Natural numbers where the domain of the enumerating function can assume anyordinal . Under this definition, an enumeration of a set "S" is anysurjection from anordinal α onto "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 encompasstransfinite listings.Under this definition, the first uncountable ordinal $omega\_1$ can be enumerated by the identity function on $omega\_1$ so that these two notions do

**not**coincide. More generally, it is a theorem of ZF that anywell-ordered set can be enumerated under this characterization so that it coincides up to relabeling with the generalized listing enumeration. If one also assumes theAxiom of Choice , then all sets can be enumerated so that it coincides up to relabeling with the most general form of enumerations.Since set theorists work with infinite sets of arbitrarily large cardinalities, the default definition among this group of mathematicians of an enumeration of a set tends to be any arbitrary α-sequence exactly listing all of its elements. Indeed, in Jech's book, which is a common reference for set theorists, an enumeration is defined to be exactly this. Therefore, in order to avoid ambiguity, one may use the term finitely enumerable or

denumerable to denote one of the corresponding types of distinguished countable enumerations.**Enumeration as combinatorial counting**There are flourishing subareas in many branches of mathematics concerned with enumerating (in the sense of finite

counting ) objects of special kinds. For instance, in "permutation enumeration" and "graph enumeration " the objective is to count permutations or graphs that meet certain structural conditions.**References***

**ee also***

Ordinal number

*Wikimedia Foundation.
2010.*

**Synonyms**:

### Look at other dictionaries:

**énumération**— [ enymerasjɔ̃ ] n. f. • 1488; lat. enumeratio 1 ♦ Action d énumérer. ⇒ compte , dénombrement, recensement. Énumération interminable, ennuyeuse. ⇒ kyrielle, litanie. Faire une longue énumération. Rhét. Figure consistant à énoncer successivement… … Encyclopédie Universelle**Enumeration**— Énumération L énumération (substantif féminin), du latin enumeratio du verbe enumerare ( compter en entier, dénombrer ) est une figure de style qui consiste à dénombrer des divers éléments dont se composent un concept générique ou une idée d… … Wikipédia en Français**énumération**— ÉNUMÉRATION. sub. f. Dénombrement. Ample énumération. Simple énumération. La simple énumération de ses conquêtes fait son éloge. Il m a fait une ample et exacte énumération. L énumération des parties est un des lieux communs de la Rhétorique … Dictionnaire de l'Académie Française 1798**enumeration**— Enumeration. s. f. Denombrement. Ample enumeration. simple enumeration. vous le condamnerez sur la simple enumeration de ses crimes. il m a fait une ample & exacte enumeration. l enumeration des parties est un des lieux communs de la Rhetorique … Dictionnaire de l'Académie française**Enumeration**— E*nu mer*a tion, n. [L. enumeratio: cf. F. [ e]num[ e]ration.] 1. The act of enumerating, making separate mention, or recounting. [1913 Webster] 2. A detailed account, in which each thing is specially noticed. [1913 Webster] Because almost every… … The Collaborative International Dictionary of English**enumeration**— 1550s, from M.Fr. énumération, from L. enumerationem (nom. enumeratio) a counting up, noun of action from pp. stem of enumerare to reckon up, count over, enumerate, from ex from (see EX (Cf. ex )) + numerare to count, number, from numerus number… … Etymology dictionary**Enumeration**— (lat.: enumeratio = ‚Aufzählung‘) steht für: Aufzählungstyp, ein Datentyp mit endlichem Wertebereich Enumeratio, eine rhetorische Figur Enumerationsalgorithmus, ein generisches Verfahren der Algorithmik Siehe auch: Enumerationsprinzip… … Deutsch Wikipedia**Enumeration**— (lat.), Auf , Herzählung; enumerieren, auf , herzählen, berechnen … Kleines Konversations-Lexikon**Enumeration**— Enumeration, lat. deutsch, Aufzählung; enumeriren, aufzählen … Herders Conversations-Lexikon**enumeration**— index account (evaluation), census, computation, disclosure (act of disclosing), docket, index (catalog) … Law dictionary**Enumeration**— (latin), optælling, opregning. Det tilsvarende verbum er enumerére … Danske encyklopædi