{"history":[],"article":{"id":"797caffc-e320-4af2-b15e-0342796325f8","title":"Enumeration","slug":"enumeration","content":":::summary\n:::\n\n# \nAn **enumeration** is a complete, ordered [listing](https://bliptext.com/articles/list) of all the items in a collection.\nThe term is commonly used in [mathematics](https://bliptext.com/articles/mathematics) and [computer science](https://bliptext.com/articles/computer-science) to refer to a listing of all of the [elements](https://bliptext.com/articles/element-mathematics) of a [set](https://bliptext.com/articles/set-mathematics).\nThe precise requirements for an enumeration (for example, whether the set must be [finite](https://bliptext.com/articles/finite-set), or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem.\nSome sets can be enumerated by means of a **natural ordering** (such as 1, 2, 3, 4, ... for the set of [positive integers](https://bliptext.com/articles/positive-integer)), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering.\nIn some contexts, such as [enumerative combinatorics](https://bliptext.com/articles/enumerative-combinatorics), the term enumeration is used more in the sense of [counting](https://bliptext.com/articles/counting) – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements.\n\n# Combinatorics\nIn combinatorics, enumeration means [counting](https://bliptext.com/articles/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](https://bliptext.com/articles/permutation) of some finite set.\nThere are flourishing subareas in many branches of mathematics concerned with enumerating in this sense objects of special kinds.\nFor instance, in [partition](https://bliptext.com/articles/integer-partition) enumeration and [graph enumeration](https://bliptext.com/articles/graph-enumeration) the objective is to count [partition](https://bliptext.com/articles/integer-partition)s or graphs that meet certain conditions.\n\n# Set theory\nIn [set theory](https://bliptext.com/articles/set-theory), the notion of enumeration has a broader sense, and does not require the set being enumerated to be finite.\n\n## Listing\nWhen an enumeration is used in an [ordered list](https://bliptext.com/articles/sequence) context, we impose some sort of ordering structure requirement on the [index set](https://bliptext.com/articles/index-set-recursion-theory).\nWhile 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](https://bliptext.com/articles/well-ordered).\nAccording to this characterization, an ordered enumeration is defined to be a surjection (an onto relationship) with a well-ordered domain.\nThis 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.\n\n## Countable vs. uncountable\nUnless otherwise specified, an enumeration is done by means of [natural numbers](https://bliptext.com/articles/natural-number).\nThat is, an enumeration of a [set](https://bliptext.com/articles/set-mathematics) S is a [bijective function](https://bliptext.com/articles/bijective-function) from the [natural numbers](https://bliptext.com/articles/natural-number) \\mathbb{N} or an [initial segment](https://bliptext.com/articles/initial-segment)\nof the natural numbers to S.\nA set is [countable](https://bliptext.com/articles/countable-set) if it can be enumerated, that is, if there exists an enumeration of it.\nOtherwise, it is [uncountable](https://bliptext.com/articles/uncountable).\nFor example, the set of the real numbers is uncountable.\nA set is [finite](https://bliptext.com/articles/finite-set) if it can be enumerated by means of a proper initial segment\nof the natural numbers, in which case, its [cardinality](https://bliptext.com/articles/cardinality) is n. The [empty set](https://bliptext.com/articles/empty-set) is finite, as it can be enumerated by means of the empty initial segment of the natural numbers.\nThe term **enumerable set** is sometimes used for countable sets.\nHowever it is also often used for [computably enumerable sets](https://bliptext.com/articles/computably-enumerable-set), which are the countable sets for which an enumeration function can be computed with an algorithm.\nFor 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](https://bliptext.com/articles/injective-function) from it into the natural numbers.\n\n### Examples\n

The [natural numbers](https://bliptext.com/articles/natural-number) are enumerable by the function f(x) = x.\nIn this case is simply the [identity function](https://bliptext.com/articles/identity-function).
\\mathbb{Z}, the set of [integers](https://bliptext.com/articles/integers) is enumerable by\nis a bijection since every natural number corresponds to exactly one integer.\nThe following table gives the first few values of this enumeration:\n
All (non empty) finite sets are enumerable.\nLet S be a finite set with n > 0 elements and let K = {1,2,...,n}.\nSelect any element s in S and assign f(n) = s.\nNow set S ' = S − {s} (where − denotes [set difference](https://bliptext.com/articles/set-difference)).\nSelect any element s' ∈ S' and assign f(n − 1) = s' .\nContinue this process until all elements of the set have been assigned a natural number.\nThen f: K \\to S is an enumeration of S.
The [real numbers](https://bliptext.com/articles/real-number) have no countable enumeration as proved by [Cantor's diagonal argument](https://bliptext.com/articles/cantor-s-diagonal-argument) and [Cantor's first uncountability proof](https://bliptext.com/articles/cantor-s-first-uncountability-proof).

\n\n### Properties\n\n## Ordinals\nIn [set theory](https://bliptext.com/articles/set-theory), there is a more general notion of an enumeration than the characterization requiring the domain of the listing function to be an [initial segment](https://bliptext.com/articles/initial-segment) of the Natural numbers where the domain of the enumerating function can assume any [ordinal](https://bliptext.com/articles/ordinal-number).\nUnder this definition, an enumeration of a set S is any [surjection](https://bliptext.com/articles/surjection) from an ordinal α onto S.\nThe more restrictive version of enumeration mentioned before is the special case where α is a finite ordinal or the first limit ordinal ω.\nThis more generalized version extends the aforementioned definition to encompass [transfinite](https://bliptext.com/articles/transfinite-induction) listings.\nUnder this definition, the [first uncountable ordinal \\omega 1](https://bliptext.com/articles/first-uncountable-ordinal) can be enumerated by the identity function on \\omega_1 so that these two **not**ions do **not** coincide.\nMore generally, it is a theorem of ZF that any [well-ordered](https://bliptext.com/articles/well-ordered) set can be enumerated under this characterization so that it coincides up to relabeling with the generalized listing enumeration.\nIf one also assumes the [Axiom of Choice](https://bliptext.com/articles/axiom-of-choice), then all sets can be enumerated so that it coincides up to relabeling with the most general form of enumerations.\nSince [set theorists](https://bliptext.com/articles/set-theorist) work with infinite sets of arbitrarily large [cardinalities](https://bliptext.com/articles/cardinality), 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.\nIndeed, in Jech's book, which is a common reference for set theorists, an enumeration is defined to be exactly this.\nTherefore, in order to avoid ambiguity, one may use the term finitely enumerable or [denumerable](https://bliptext.com/articles/denumerable) to denote one of the corresponding types of distinguished countable enumerations.\n\n## Comparison of cardinalities\nFormally, the most inclusive definition of an enumeration of a set S is any [surjection](https://bliptext.com/articles/surjection) from an arbitrary [index set](https://bliptext.com/articles/index-set) I onto S.\nIn this broad context, every set S can be trivially enumerated by the [identity function](https://bliptext.com/articles/identity-function) from S onto itself.\nIf one does not assume the [axiom of choice](https://bliptext.com/articles/axiom-of-choice) or one of its variants, S need not have any [well-ordering](https://bliptext.com/articles/well-ordering).\nEven if one does assume the axiom of choice, S need not have any natural well-ordering.\nThis general definition therefore lends itself to a counting notion where we are interested in \"how many\" rather than \"in what order.\"\nIn practice, this broad meaning of enumeration is often used to compare the relative sizes or [cardinalities](https://bliptext.com/articles/cardinality) of different sets.\nIf one works in [Zermelo–Fraenkel set theory](https://bliptext.com/articles/zermelo-fraenkel-set-theory) without the axiom of choice, one may want to impose the additional restriction that an enumeration must also be [injective](https://bliptext.com/articles/injective) (without repetition) since in this theory, the existence of a surjection from I onto S need not imply the existence of an [injection](https://bliptext.com/articles/injection-mathematics) from S into I.\n\n# Computability and complexity theory\nIn [computability theory](https://bliptext.com/articles/computability-theory) one often considers countable enumerations with the added requirement that the mapping from \\mathbb{N} (set of all natural numbers) to the enumerated set must be [computable](https://bliptext.com/articles/computable-function).\nThe set being enumerated is then called [recursively enumerable](https://bliptext.com/articles/recursively-enumerable) (or computably enumerable in more contemporary language), referring to the use of [recursion theory](https://bliptext.com/articles/recursion-theory) in formalizations of what it means for the map to be computable.\nIn this sense, a subset of the natural numbers is [computably enumerable](https://bliptext.com/articles/computably-enumerable) if it is the range of a computable function.\nIn this context, enumerable may be used to mean computably enumerable.\nHowever, 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.\nA specific example of a set with an enumeration but not a computable enumeration is the complement of the [halting set](https://bliptext.com/articles/halting-problem).\nFurthermore, this characterization illustrates a place where the ordering of the listing is important.\nThere exists a computable enumeration of the halting set, but **not** one that lists the elements in an increasing ordering.\nIf there were one, then the halting set would be [decidable](https://bliptext.com/articles/decidable-language), which is provably false.\nIn general, being recursively enumerable is a weaker condition than being a [decidable set](https://bliptext.com/articles/decidable-set).\nThe notion of enumeration has also been studied from the point of view of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory) for various tasks in the context of [enumeration algorithms](https://bliptext.com/articles/enumeration-algorithm).","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T18:42:23.488Z","updated_at":"2025-01-25T18:42:23.488Z","search_vector":"'enumer':1","search_content":" \n \n\n# \nAn **enumeration** is a complete, ordered [listing](https://bliptext.com/articles/list) of all the items in a collection.\nThe term is commonly used in [mathematics](https://bliptext.com/articles/mathematics) and [computer science](https://bliptext.com/articles/computer-science) to refer to a listing of all of the [elements](https://bliptext.com/articles/element-mathematics) of a [set](https://bliptext.com/articles/set-mathematics).\nThe precise requirements for an enumeration (for example, whether the set must be [finite](https://bliptext.com/articles/finite-set), or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem.\nSome sets can be enumerated by means of a **natural ordering** (such as 1, 2, 3, 4, ... for the set of [positive integers](https://bliptext.com/articles/positive-integer)), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering.\nIn some contexts, such as [enumerative combinatorics](https://bliptext.com/articles/enumerative-combinatorics), the term enumeration is used more in the sense of [counting](https://bliptext.com/articles/counting) – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements.\n\n# Combinatorics\nIn combinatorics, enumeration means [counting](https://bliptext.com/articles/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](https://bliptext.com/articles/permutation) of some finite set.\nThere are flourishing subareas in many branches of mathematics concerned with enumerating in this sense objects of special kinds.\nFor instance, in [partition](https://bliptext.com/articles/integer-partition) enumeration and [graph enumeration](https://bliptext.com/articles/graph-enumeration) the objective is to count [partition](https://bliptext.com/articles/integer-partition)s or graphs that meet certain conditions.\n\n# Set theory\nIn [set theory](https://bliptext.com/articles/set-theory), the notion of enumeration has a broader sense, and does not require the set being enumerated to be finite.\n\n## Listing\nWhen an enumeration is used in an [ordered list](https://bliptext.com/articles/sequence) context, we impose some sort of ordering structure requirement on the [index set](https://bliptext.com/articles/index-set-recursion-theory).\nWhile 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](https://bliptext.com/articles/well-ordered).\nAccording to this characterization, an ordered enumeration is defined to be a surjection (an onto relationship) with a well-ordered domain.\nThis 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.\n\n## Countable vs. uncountable\nUnless otherwise specified, an enumeration is done by means of [natural numbers](https://bliptext.com/articles/natural-number).\nThat is, an enumeration of a [set](https://bliptext.com/articles/set-mathematics) S is a [bijective function](https://bliptext.com/articles/bijective-function) from the [natural numbers](https://bliptext.com/articles/natural-number) \\mathbb{N} or an [initial segment](https://bliptext.com/articles/initial-segment)\nof the natural numbers to S.\nA set is [countable](https://bliptext.com/articles/countable-set) if it can be enumerated, that is, if there exists an enumeration of it.\nOtherwise, it is [uncountable](https://bliptext.com/articles/uncountable).\nFor example, the set of the real numbers is uncountable.\nA set is [finite](https://bliptext.com/articles/finite-set) if it can be enumerated by means of a proper initial segment\nof the natural numbers, in which case, its [cardinality](https://bliptext.com/articles/cardinality) is n. The [empty set](https://bliptext.com/articles/empty-set) is finite, as it can be enumerated by means of the empty initial segment of the natural numbers.\nThe term **enumerable set** is sometimes used for countable sets.\nHowever it is also often used for [computably enumerable sets](https://bliptext.com/articles/computably-enumerable-set), which are the countable sets for which an enumeration function can be computed with an algorithm.\nFor 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](https://bliptext.com/articles/injective-function) from it into the natural numbers.\n\n### Examples\n \n The [natural numbers](https://bliptext.com/articles/natural-number) are enumerable by the function f(x) = x.\nIn this case is simply the [identity function](https://bliptext.com/articles/identity-function). \n \\mathbb{Z}, the set of [integers](https://bliptext.com/articles/integers) is enumerable by\nis a bijection since every natural number corresponds to exactly one integer.\nThe following table gives the first few values of this enumeration:\n \n All (non empty) finite sets are enumerable.\nLet S be a finite set with n > 0 elements and let K = {1,2,...,n}.\nSelect any element s in S and assign f(n) = s.\nNow set S ' = S − {s} (where − denotes [set difference](https://bliptext.com/articles/set-difference)).\nSelect any element s' ∈ S' and assign f(n − 1) = s' .\nContinue this process until all elements of the set have been assigned a natural number.\nThen f: K \\to S is an enumeration of S. \n The [real numbers](https://bliptext.com/articles/real-number) have no countable enumeration as proved by [Cantor's diagonal argument](https://bliptext.com/articles/cantor-s-diagonal-argument) and [Cantor's first uncountability proof](https://bliptext.com/articles/cantor-s-first-uncountability-proof). \n \n\n### Properties\n\n## Ordinals\nIn [set theory](https://bliptext.com/articles/set-theory), there is a more general notion of an enumeration than the characterization requiring the domain of the listing function to be an [initial segment](https://bliptext.com/articles/initial-segment) of the Natural numbers where the domain of the enumerating function can assume any [ordinal](https://bliptext.com/articles/ordinal-number).\nUnder this definition, an enumeration of a set S is any [surjection](https://bliptext.com/articles/surjection) from an ordinal α onto S.\nThe more restrictive version of enumeration mentioned before is the special case where α is a finite ordinal or the first limit ordinal ω.\nThis more generalized version extends the aforementioned definition to encompass [transfinite](https://bliptext.com/articles/transfinite-induction) listings.\nUnder this definition, the [first uncountable ordinal \\omega 1](https://bliptext.com/articles/first-uncountable-ordinal) can be enumerated by the identity function on \\omega_1 so that these two **not**ions do **not** coincide.\nMore generally, it is a theorem of ZF that any [well-ordered](https://bliptext.com/articles/well-ordered) set can be enumerated under this characterization so that it coincides up to relabeling with the generalized listing enumeration.\nIf one also assumes the [Axiom of Choice](https://bliptext.com/articles/axiom-of-choice), then all sets can be enumerated so that it coincides up to relabeling with the most general form of enumerations.\nSince [set theorists](https://bliptext.com/articles/set-theorist) work with infinite sets of arbitrarily large [cardinalities](https://bliptext.com/articles/cardinality), 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.\nIndeed, in Jech's book, which is a common reference for set theorists, an enumeration is defined to be exactly this.\nTherefore, in order to avoid ambiguity, one may use the term finitely enumerable or [denumerable](https://bliptext.com/articles/denumerable) to denote one of the corresponding types of distinguished countable enumerations.\n\n## Comparison of cardinalities\nFormally, the most inclusive definition of an enumeration of a set S is any [surjection](https://bliptext.com/articles/surjection) from an arbitrary [index set](https://bliptext.com/articles/index-set) I onto S.\nIn this broad context, every set S can be trivially enumerated by the [identity function](https://bliptext.com/articles/identity-function) from S onto itself.\nIf one does not assume the [axiom of choice](https://bliptext.com/articles/axiom-of-choice) or one of its variants, S need not have any [well-ordering](https://bliptext.com/articles/well-ordering).\nEven if one does assume the axiom of choice, S need not have any natural well-ordering.\nThis general definition therefore lends itself to a counting notion where we are interested in \"how many\" rather than \"in what order.\"\nIn practice, this broad meaning of enumeration is often used to compare the relative sizes or [cardinalities](https://bliptext.com/articles/cardinality) of different sets.\nIf one works in [Zermelo–Fraenkel set theory](https://bliptext.com/articles/zermelo-fraenkel-set-theory) without the axiom of choice, one may want to impose the additional restriction that an enumeration must also be [injective](https://bliptext.com/articles/injective) (without repetition) since in this theory, the existence of a surjection from I onto S need not imply the existence of an [injection](https://bliptext.com/articles/injection-mathematics) from S into I.\n\n# Computability and complexity theory\nIn [computability theory](https://bliptext.com/articles/computability-theory) one often considers countable enumerations with the added requirement that the mapping from \\mathbb{N} (set of all natural numbers) to the enumerated set must be [computable](https://bliptext.com/articles/computable-function).\nThe set being enumerated is then called [recursively enumerable](https://bliptext.com/articles/recursively-enumerable) (or computably enumerable in more contemporary language), referring to the use of [recursion theory](https://bliptext.com/articles/recursion-theory) in formalizations of what it means for the map to be computable.\nIn this sense, a subset of the natural numbers is [computably enumerable](https://bliptext.com/articles/computably-enumerable) if it is the range of a computable function.\nIn this context, enumerable may be used to mean computably enumerable.\nHowever, 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.\nA specific example of a set with an enumeration but not a computable enumeration is the complement of the [halting set](https://bliptext.com/articles/halting-problem).\nFurthermore, this characterization illustrates a place where the ordering of the listing is important.\nThere exists a computable enumeration of the halting set, but **not** one that lists the elements in an increasing ordering.\nIf there were one, then the halting set would be [decidable](https://bliptext.com/articles/decidable-language), which is provably false.\nIn general, being recursively enumerable is a weaker condition than being a [decidable set](https://bliptext.com/articles/decidable-set).\nThe notion of enumeration has also been studied from the point of view of [computational complexity theory](https://bliptext.com/articles/computational-complexity-theory) for various tasks in the context of [enumeration algorithms](https://bliptext.com/articles/enumeration-algorithm).","revisionCount":0},"hasMore":false,"nextCursor":null}

History