countability

Countability is a concept in set theory describing whether the elements of a set can be matched with natural numbers. A set is countable if it is finite or there exists a bijection between the set and the natural numbers. If the set is infinite and such a bijection exists, it is called countably infinite.

Examples of countable sets include the natural numbers N, the integers Z, and the rational numbers Q. All finite sets are also countable. The rationals are countable even though they are dense in the reals; they can be listed in a sequence, for example by arranging fractions in increasing order and skipping duplicates.

Subsets of countable sets are countable as well: any subset of a countable set is either finite or countably infinite. The set of all finite strings over a finite alphabet is countable because it is a countable union of finite sets. By contrast, the real numbers R are uncountable; Cantor's diagonal argument shows there is no bijection between R and N. In fact, the cardinality of R equals the power set of N. Many commonly considered sets, such as the set of all subsets of N, are uncountable.

Countability is a foundational notion in analysis and topology. It informs the idea of separable spaces (having a countable dense subset) and interacts with concepts such as countable additivity in measure theory and the study of sequences in analysis.