Enumeration

Enumeration

Discussion
Ask a question about 'Enumeration'
Start a new discussion about 'Enumeration'
Answer questions from other users
Full Discussion Forum
 
Encyclopedia
{{Otheruses4|mathematical enumeration|enumeration types in programming languages|enumerated type}} {{Wiktionary}} In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and theoretical computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, 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 is 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
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the 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 in combinatorics

{{main|Enumerative combinatorics}} In combinatorics, enumeration means counting
Counting
Counting is the action of finding the number of elements of a finite set of objects. The traditional way of counting consists of continually increasing a counter by a unit for every element of the set, in some order, while marking those elements to avoid visiting the same element more than once,...

, 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 permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

s 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
Partition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...

 enumeration
and graph enumeration
Graph enumeration
In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph...

the objective is to count partitions or graphs that meet certain conditions.

Enumeration in set theory

In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

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

Enumeration as listing

When an enumeration is used in an ordered list
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

 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 in set theory 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 ω, the ordinal of the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s. This definition can also be stated as follows: NEWLINE
    NEWLINE
  • As a surjective mapping from \mathbb{N} (the natural number
    Natural number
    In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

    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 of computability and elementary set theory
    Set theory
    Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

    .
NEWLINE We may also define it differently when working with finite sets. In this case an enumeration may be defined as follows: NEWLINE
    NEWLINE
  • 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 the cardinality of S.
NEWLINE 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
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...

 (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

NEWLINE
    NEWLINE
  • The natural numbers are enumerable by the function f(x) = x. In this case f: \mathbb{N} \to \mathbb{N} is simply the identity function
    Identity function
    In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

    .
  • NEWLINE
  • \mathbb{Z}, the set of integers is enumerable by
NEWLINE NEWLINE
NEWLINE
NEWLINE
NEWLINE
f(x):= \begin{cases} -(x+1)/2, & \mbox{if } x \mbox{ is odd} \\ x/2, & \mbox{if } x \mbox{ is even}. \end{cases}
NEWLINE
NEWLINE f: \mathbb{N} \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: NEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINENEWLINE
x 0 1 2 3 4 5 6 7 8
ƒ(x) 0 −1 1 −2 2 −3 3 −4 4
NEWLINENEWLINE NEWLINE
    NEWLINE
  • 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 − denotes set 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\} \to S is an enumeration of S.
NEWLINE NEWLINE
    NEWLINE
  • The real number
    Real number
    In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

    s have no countable enumeration as proved by Cantor's diagonal argument
    Cantor's diagonal argument
    Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

     and Cantor's first uncountability proof
    Cantor's first uncountability proof
    Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...

    .
NEWLINE

Properties

NEWLINE
    NEWLINE
  • There exists an enumeration for a set (in this sense) if and only if the set is countable.
NEWLINE NEWLINE
    NEWLINE
  • 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.
NEWLINE NEWLINE
    NEWLINE
  • An enumeration e of a set S with domain \mathbb{N} induces a well-order
    Well-order
    In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...

     ≤ on that set defined by st 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.
NEWLINE

Ordinal enumeration

In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, there is a more general notion of an enumeration than the characterization requiring the domain of the listing function to be an initial segment of the Natural numbers where the domain of the enumerating function can assume any ordinal
Ordinal
Ordinal may refer to:* Ordinal number , a word representing the rank of a number* Ordinal scale, ranking things that are not necessarily numbers* Ordinal indicator, the sign adjacent to a numeral denoting that it is an ordinal number...

. Under this definition, an enumeration of a set S is any surjection from an ordinal
Ordinal
Ordinal may refer to:* Ordinal number , a word representing the rank of a number* Ordinal scale, ranking things that are not necessarily numbers* Ordinal indicator, the sign adjacent to a numeral denoting that it is an ordinal number...

 α 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 encompass transfinite listings. Under this definition, the first uncountable ordinal \omega 1
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by ω1 or sometimes by Ω, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals...

 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 any well-ordered set can be enumerated under this characterization so that it coincides up to relabeling with the generalized listing enumeration. If one also assumes the Axiom 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 comparison of cardinalities

Formally, the most inclusive definition of an enumeration of a set S is any surjection from an arbitrary index set
Index set
In mathematics, the elements of a set A may be indexed or labeled by means of a set J that is on that account called an index set...

 I onto S. In this broad context, every set S can be trivially enumerated by the identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...

 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 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 or cardinalities of different sets. If one works in Zermelo-Fraenkel set theory without the axiom of 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 in computability theory

In computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

 one often considers countable enumerations with the added requirement that the mapping from \mathbb{N} to the enumerated set must be computable
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

. The set being enumerated is then called recursively enumerable (or computably enumerable in more contemporary language), referring to the use of recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

 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
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

. 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 decidable
Decidable
The word decidable may refer to:* Decidable language*Decidability for the equivalent in mathematical logic*Gödel's incompleteness theorem, a theorem on the indecidability of languages consisting of "true statements" in mathematical logic....

, which is provably false. In general, being recursively enumerable is a weaker condition than being a decidable set.

External Links

NEWLINENEWLINE