Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. Equivalently, a set is countable if there exists an injective function from the set into the natural numbers, meaning that its elements can be listed in a finite or infinite sequence. Countable sets are either finite or countably infinite; the latter have cardinality ℵ₀ (aleph-null), the smallest infinite cardinal. The concept of countability, introduced by Georg Cantor in the 1870s, is fundamental in set theory, analysis, and computer science, as it distinguishes between discrete "listable" collections and richer, uncountable structures such as the real numbers.

Definition

A set \(S\) is called countable if there exists an injective function \(f : S \to \mathbb{N}\), where \(\mathbb{N}\) is the set of natural numbers (usually taken to be \(\{0,1,2,\dots\}\) or \(\{1,2,3,\dots\}\); the choice is irrelevant). Since every subset of \(\mathbb{N}\) is either finite or in bijection with \(\mathbb{N}\), this definition is equivalent to saying that the cardinality of \(S\) is at most \(\aleph_0\), i.e., \(|S| \le \aleph_0\).

For a nonempty set \(S\), countability is also equivalent to the existence of a surjective function \(g : \mathbb{N} \to S\). This captures the idea that the elements of \(S\) can be enumerated (possibly with repetitions) as \(g(0), g(1), g(2), \dots\). If \(S\) is infinite and such a surjection exists, it can be refined to a bijection between \(\mathbb{N}\) and \(S\).

Some authors, particularly in older literature or in analysis, reserve the term countable for what is more precisely called countably infinite (or denumerable), i.e., having a bijection with \(\mathbb{N}\). To avoid ambiguity, the term at most countable may be used to include finite sets. In modern set theory (ZFC), the standard convention is that countable includes both finite and countably infinite sets, and context usually clarifies the intended meaning.

Countably infinite sets

A set is countably infinite if it has the same cardinality as \(\mathbb{N}\) itself, i.e., there exists a bijection \(h : \mathbb{N} \to S\). The cardinality of all such sets is denoted by \(\aleph_0\). Familiar examples and their standard bijections with \(\mathbb{N}\) include:

• The set of integers \(\mathbb{Z}\): the mapping \(0 \mapsto 0\), \(1 \mapsto 1\), \(2 \mapsto -1\), \(3 \mapsto 2\), \(4 \mapsto -2\), … yields a bijection.
• The set of rational numbers \(\mathbb{Q}\): using Cantor's diagonal argument on an array of fractions \(p/q\) (with \(q \neq 0\) and reduced form), one obtains a bijection with \(\mathbb{N}\). Alternatively, a pairing function such as the Cantor pairing function \(\pi(m,n) = \frac{1}{2}(m+n)(m+n+1)+n\) gives a bijection between \(\mathbb{N} \times \mathbb{N}\) and \(\mathbb{N}\), from which a bijection with \(\mathbb{Q}\) follows.
• The set of algebraic numbers: the roots of polynomials with integer coefficients are countable because the set of all such polynomials is countable (each polinomial can be coded by a finite sequence of integers) and each polynomial has finitely many roots. Since the real numbers are uncountable, this shows that transcendental numbers exist and form an uncountable set.
• The set of all finite sequences over a finite or countable alphabet: for a finite alphabet, strings can be ordered by length and then lexicographically. For a countable alphabet, a similar diagonal encoding works. This implies that the set of all computer programs, theorems in a formal language, or Turing machines is countably infinite (or finite, depending on restrictions).

A useful criterion is that a set is countably infinite if and only if it is the image of a countably infinite set under a surjection, or equivalently, if it can be written as the union of a countable family of finite sets.

Finite sets and countability

Every finite set is countable because there trivially exists an injection into \(\mathbb{N}\) (map the \(n\) elements to distinct natural numbers, e.g., to \(\{0,1,\dots,n-1\}\)). In many contexts, such as when discussing cardinalities, it is explicit that countable includes finite sets; for example, one says "finite or countable". However, in everyday mathematical English, saying "countable" often implies infinite, so care is required. A set that is not countable is called uncountable.

Examples of countable sets

In addition to the natural numbers themselves, the following sets are all countable (most are countably infinite, some may be finite):

• \(\mathbb{N}, \mathbb{Z}, \mathbb{Q}\), and their finite Cartesian products.
• Algebraic numbers (as noted), and therefore also the set of computable numbers.
• The set of all finite subsets of a countable set.
• The set of all polynomials with integer (or rational) coefficients.
• The set of all vectors in \(\mathbb{Q}^n\) for a fixed finite \(n\).
• Any subset of a countable set (hence, for instance, the set of prime numbers is countable).
• The set of all sentences in a formal language with a countable alphabet.
• A countable union of countable sets is countable (requires at least the axiom of countable choice; without any choice, a countable union of countable sets may not be countable). For example, the set of all sequences of natural numbers that are eventually zero is countable.

Sets that are not countable are uncountable; the most prominent example is the set of real numbers \(\mathbb{R}\). Cantor's diagonal argument (1891) shows that the set of all infinite binary sequences, and hence the real interval \([0,1]\), is uncountable. Other uncountable sets include the power set \(\mathcal{P}(\mathbb{N})\) (which has cardinality \(2^{\aleph_0}\)), the set of all infinite sequences of natural numbers, and the set of all subsets of a countably infinite set. The continuum hypothesis posits that there is no cardinal strictly between \(\aleph_0\) and \(2^{\aleph_0}\).

Properties

• Subsets: Any subset of a countable set is countable.
• Cartesian product: The Cartesian product of two countable sets is countable. By induction, the product of finitely many countable sets is countable. The product of a countably infinite family of countable sets, however, need not be countable (e.g., the set of all sequences of 0s and 1s is uncountable).
• Union: A countable union of countable sets is countable (in ZF set theory, this requires the axiom of countable choice; in ZFC it is a theorem). This is used to show that the set of algebraic numbers is countable.
• Power set: The power set of an infinite countable set is uncountable (Cantor's theorem). The cardinality of \(\mathcal{P}(\mathbb{N})\) is \(2^{\aleph_0}\), often denoted \(\mathfrak{c}\) (the cardinality of the continuum).
• Measurability: Countable subsets of Euclidean space have Lebesgue measure zero.
• Orderability: Every countable set can be well-ordered (e.g., by transferring the natural order of \(\mathbb{N}\) via a bijection). In fact, a set is countable if and only if it can be well-ordered in a way where every initial segment is finite.
• Topology: A topological space with a countable dense subset is called separable. The real line \(\mathbb{R}\) is separable because \(\mathbb{Q}\) is a countable dense subset. A space where every point has a countable local base is first-countable; many spaces of analysis are first-countable. A space whose topology has a countable basis is second-countable; second-countable spaces are both separable and first-countable.
• Logic and computability: The Löwenheim–Skolem theorem implies that any consistent, countable first-order theory has a countable model. In computability theory, a set is computably enumerable (c.e.) if it is the domain of a partial computable function, i.e., can be algorithmically listed, possibly with repetitions; all c.e. sets are countable.

History

The concept of countability was introduced by Georg Cantor in his work on trigonometric series and set theory. In 1874, he published a landmark paper proving that the set of algebraic numbers is countable while the set of real numbers is not. This established the existence of transcendental numbers and laid the groundwork for cardinal arithmetic. Cantor later developed the diagonal argument (1891) to show the uncountability of the real numbers directly, and he introduced the notation \(\aleph_0\) for the cardinality of the natural numbers. The distinction between countable and uncountable sets became a cornerstone of modern mathematics, leading to the development of axiomatic set theory and the study of the continuum hypothesis by Cantor, Hilbert, Gödel, and Cohen.

See also

• Cardinal number
• Aleph number
• Cantor's diagonal argument
• Uncountable set
• Hilbert's paradox of the Grand Hotel
• Countable choice
• First-countable space
• Second-countable space
• Separable space