This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Enumeration" – news ·newspapers ·books ·scholar ·JSTOR(August 2025)

Anenumeration is a complete, orderedlisting of all the items in a collection. The term is commonly used inmathematics andcomputer science to refer to a listing of all of theelements of aset. The precise requirements for an enumeration (for example, whether the set must befinite, 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 anatural ordering (such as 1, 2, 3, 4, ... for the set ofpositive integers), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering. In some contexts, such asenumerative combinatorics, the termenumeration is used more in the sense ofcounting – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements.

In combinatorics, enumeration meanscounting, 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 allpermutations of some finite set. There are flourishing subareas in many branches of mathematics concerned with enumerating in this sense. For instance, inpartition enumeration andgraph enumeration the objective is to count partitions or graphs that meet certain conditions.

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

When an enumeration is used in anordered list context, we impose some sort of ordering structure requirement on theindex 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 (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.

Unless otherwise specified, an enumeration is done by means ofnatural numbers. That is, anenumeration of asetS is abijective function from thenatural numbers${\displaystyle \mathbb{N}}$ or aninitial segment{1, ...,n} of the natural numbers toS.

A set iscountable if it can be enumerated, that is, if there exists an enumeration of it. Otherwise, it isuncountable. For example, the set of the real numbers is uncountable.

A set isfinite if it can be enumerated by means of a proper initial segment{1, ...,n} of the natural numbers, in which case, itscardinality isn. Theempty set is finite, as it can be enumerated by means of the empty initial segment of the natural numbers.

The termenumerable set is sometimes used for countable sets. However it is also often used forcomputably 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 setS is countable if and only if there exists aninjective function from it into the natural numbers.

• Thenatural numbers are enumerable by the functionf(x) =x. In this case${\displaystyle f:\mathbb{N}\to \mathbb{N}}$ is simply theidentity function.
• ${\displaystyle \mathbb{Z}}$, the set ofintegers is enumerable by

$${\displaystyle f(x):=\frac{1-(-1{)}^x(2x+1)}{4}}$$

$${\displaystyle f:{\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. LetS be a finite set withn > 0 elements and letK = {1,2,...,n}. Select any elements inS and assignf(n) =s. Now setS' =S − {s} (where − denotesset difference). Select any elements' ∈ S' and assignf(n − 1) =s'. Continue this process until all elements of the set have been assigned a natural number. Then${\displaystyle f:K\to S}$ is an enumeration ofS.
• Thereal numbers have no countable enumeration as proved byCantor's diagonal argument andCantor's first uncountability proof.

• There exists an enumeration for a set (in this sense) if and only if the set iscountable.
• If a set is enumerable it will have anuncountable 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 injectiveand allows only a limited form of partiality such that iff(n) is defined thenf(m) must be defined for allm < n, then a finite set ofN elements has exactlyN! enumerations.
• An enumeratione of a setS with domain${\displaystyle \mathbb{N}}$ induces awell-order ≤ on that set defined bys ≤t if and only if${\displaystyle min{e}^{-1}(s)\le 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.

Inset 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 setS is anysurjection from an ordinal α ontoS. 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, thefirst uncountable ordinal${\displaystyle {\omega }_1}$ can be enumerated by the identity function on${\displaystyle {\omega }_1}$ so that these two notions donot 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.

Sinceset theorists work with infinite sets of arbitrarily largecardinalities, 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 ordenumerable to denote one of the corresponding types of distinguished countable enumerations.

Formally, the most inclusive definition of an enumeration of a setS is anysurjection from an arbitraryindex setI ontoS. In this broad context, every setS can be trivially enumerated by theidentity function fromS onto itself. If one doesnot assume theaxiom of choice or one of its variants,S need not have anywell-ordering. Even if one does assume the axiom of 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 enumeration is often used to compare the relative sizes orcardinalities of different sets. If one works inZermelo–Fraenkel set theory without the axiom of 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 fromI ontoS need not imply the existence of aninjection fromS intoI.

Incomputability theory one often considers countable enumerations with the added requirement that the mapping from${\displaystyle \mathbb{N}}$ (set of all natural numbers) to the enumerated set must becomputable. 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 the natural numbers iscomputably 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 the 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 thehalting set.

Furthermore, this characterization illustrates a place where the ordering of the listing is important. There exists a computable enumeration of the halting set, butnot 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.

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

• Ordinal number
• Enumerative definition
• Sequence

• Jech, Thomas (2002).Set theory, third millennium edition (revised and expanded). Springer.ISBN 3-540-44085-2.

• The dictionary definition ofenumeration at Wiktionary

• Enumerative combinatorics
• Mathematical logic
• Ordering

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from August 2025
• All articles needing additional references