Countable set

A mathematical set is countable if either it is finite or it can be put in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

In more technical terms, assuming the axiom of countable choice, a set is countable if its cardinality (the number of elements of the set) is not greater than that of the natural numbers. A countable set that is not finite is said to be countably infinite; for example the set of all natural numbers

N

{\displaystyle \mathbb {N} }

or all rational numbers

Q

{\displaystyle \mathbb {Q} }

.

The concept is attributed to Georg Cantor, who proved the existence of uncountable sets, that is, sets that are not countable; for example the set of the real numbers

R

{\displaystyle \mathbb {R} }

.

A note on terminology

Although the terms "countable" and "countably infinite" as defined here are quite common, the terminology is not universal. An alternative style uses countable to mean what is here called countably infinite, and at most countable to mean what is here called countable.

The terms enumerable and denumerable may also be used, referring to countable and countably infinite, respectively. Definitions vary and care is needed respecting the difference with recursively enumerable.

Definition

A set

S

{\displaystyle S}

is countable if:

Its cardinality

|

S

|

{\displaystyle |S|}

is less than or equal to

ℵ

0

{\displaystyle \aleph _{0}}

(aleph-null), the cardinality of the set of natural numbers

N

{\displaystyle \mathbb {N} }

.