Editing Enumeration (section)

===Countable vs. uncountable===

Unless otherwise specified, an enumeration is done by means of [[natural number]]s. That is, an ''enumeration'' of a [[set (mathematics)|set]] {{mvar|S}} is a [[bijective function]] from the [[natural number]]s <math>\mathbb{N}</math> or an [[initial segment]] {{math|{{mset|1, ..., ''n''}}}} of the natural numbers to {{mvar|S}}.

A set is [[countable set|countable]] if it can be enumerated, that is, if there exists an enumeration of it. Otherwise, it is [[uncountable]]. For example, the set of the real numbers is uncountable.

A set is [[finite set|finite]] if it can be enumerated by means of a proper initial segment {{math|{{mset|1, ..., ''n''}}}} of the natural numbers, in which case, its [[cardinality]] is {{mvar|n}}. The [[empty set]] is finite, as it can be enumerated by means of the empty initial segment of the natural numbers.

The term '''{{vanchor|enumerable}} set''' is sometimes used for countable sets. However it is also often used for [[computably enumerable set]]s, 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 set {{mvar|S}} is countable if and only if there exists an [[injective function]] from it into the natural numbers.

==== Examples ====
<ul>
<li> The [[natural number]]s are enumerable by the function ''f''(''x'') = ''x''. In this case <math>f\colon\mathbb{N} \to \mathbb{N}</math> is simply the [[identity function]].</li>
<li> <math>\mathbb{Z}</math>, the set of [[integers]] is enumerable by
<math display="block">f(x):=\frac {1-(-1)^x\,(2\,x+1)} 4 </math>
<math>f\colon\mathbb{N}_0 \to \mathbb{Z}</math> 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
|-
! ''f''(''x'')
| 0
| 1
| -1
| 2
| -2
| 3
| -3
| 4
| -4
|}
</li>
<li> All (non empty) finite sets are enumerable. Let ''S'' be a finite set with ''n > 0'' elements and let ''K'' = {1,2,...,''n''}. Select any element ''s'' in ''S'' and assign ''f''(''n'') = ''s''. Now set ''S<nowiki>'</nowiki>'' = ''S''&nbsp;−&nbsp;{''s''} (where − denotes [[set difference]]). Select any element ''s' ''&nbsp;∈&nbsp;''S' '' and assign ''f''(''n''&nbsp;−&nbsp;1) = ''s' ''. Continue this process until all elements of the set have been assigned a natural number. Then <math>f: K \to S</math> is an enumeration of ''S''.</li>
<li> The [[real number]]s have no countable enumeration as proved by [[Cantor's diagonal argument]] and [[Cantor's first uncountability proof]].</li>
</ul>

==== 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 ''f''(''n'') is defined then ''f''(''m'') must be defined for all ''m''&nbsp;<&nbsp;''n'', then a finite set of ''N'' elements has exactly ''N''! enumerations.
* An enumeration ''e'' of a set ''S'' with domain <math>\mathbb{N}</math> induces a [[well-order]] ≤ on that set defined by ''s'' ≤ ''t'' if and only if <math>\min e^{-1}(s) \leq \min e^{-1}(t)</math>. Although the order may have little to do with the underlying set, it is useful when some order of the set is necessary.