countable

Countable is a term used in set theory to describe the size of a set. A set is countable if it is finite or countably infinite. Equivalently, there exists a bijection between the set and the natural numbers, or between the set and a subset of the natural numbers. In some contexts, the phrase “at most countable” is used to emphasize finiteness, while others use countable to include both finite and infinite cases; in strict mathematical use, countable usually means finite or countably infinite.

A set that is countably infinite is one that has the same cardinality as the natural numbers, meaning there is a bijection with N. If a set is finite, it is also countable by definition. Sets that are not countable are called uncountable; a famous result is that the real numbers are uncountable, as shown by Cantor’s diagonal argument.

Examples of countable sets include the natural numbers, the integers, and the rational numbers. The set of finite strings over a finite alphabet is countable, and any finite or countable union of countable sets is countable. The set of algebraic numbers (roots of polynomials with integer coefficients) is countable, while the set of all real numbers is uncountable.

In cardinal terms, countable infinite sets have cardinality aleph-null (ℵ0). Countability is preserved under many standard constructions: subsets of countable sets are countable, finite unions of countable sets are countable, and the set of all finite or countable sequences over a countable alphabet is countable.