# Countable Set How big is infinity? The integers, the rationals, and the algebraic numbers are all infinite [sets](/page/Set), yet every one of them can be arranged into a single list indexed by the natural numbers. The real numbers cannot. This distinction — between infinities that can be enumerated and those that resist enumeration — is the starting point of the theory of [cardinality](/page/Cardinality), and the concept of a *countable set* sits at its heart. This article develops the idea of countability from first principles. We begin by asking what it means for two infinite sets to have "the same size," arrive at Cantor's definition via [bijections](/page/Function), and then build up the basic toolkit: closure under subsets, products, and countable unions. With these tools in hand we prove that $\mathbb{Q}$ and the algebraic numbers are countable, and then show — via Cantor's diagonal argument — that $\mathbb{R}$ is not. The article closes with [Cantor's theorem](/theorems/758) on power sets, which reveals that there is no largest infinity, and with the Schroeder–Bernstein theorem, which provides the practical criterion most often used to establish that two sets have the same cardinality. ## Motivation [motivation] ### Infinity is not one thing At first glance it is tempting to believe that all infinite sets are "the same size." After all, both $\mathbb{N}$ and $\mathbb{R}$ go on forever; neither one runs out. But this naive view — that infinity is a single, monolithic quantity — collapses the moment we try to make it precise. Consider the sets $\mathbb{N} = \{1, 2, 3, \ldots\}$ and $2\mathbb{N} = \{2, 4, 6, \ldots\}$. The even numbers form a proper subset of the naturals, so in one sense $2\mathbb{N}$ is "smaller." Yet the map $n \mapsto 2n$ pairs every natural number with a unique even number and vice versa, leaving nothing unmatched on either side. By the criterion of perfect pairing, the two sets have the same size. This tension — that an infinite set can be matched one-to-one with a proper subset of itself — was noticed already by Galileo, and it shows that our finite intuitions about "part versus whole" do not carry over to the infinite. ### Bijections as the measure of size Georg Cantor resolved this tension in the 1870s with a bold proposal: two sets $A$ and $B$ have *the same cardinality* if and only if there exists a bijection $f: A \to B$. For finite sets this reproduces the familiar notion of "same number of elements." For infinite sets it provides a rigorous, unambiguous definition that does not depend on how the sets are described or on any notion of "containment." The entire theory of countability flows from this single idea. ### The shocking discovery With Cantor's definition in hand, two results emerge that reshape our understanding of infinity. First, the rational numbers $\mathbb{Q}$ — which are densely packed along the number line, with infinitely many rationals between any two distinct reals — turn out to be countable. There is a bijection $\mathbb{N} \to \mathbb{Q}$, so the rationals are no more numerous than the natural numbers. Second, and far more surprising, the real numbers $\mathbb{R}$ are *not* countable. No list, no matter how cleverly arranged, can include every real number. These two facts together reveal that there are genuinely different sizes of infinity, and countability is the dividing line between the smallest infinity and all larger ones. [/motivation] ## Formal Definition The fundamental question is: which infinite sets are "small" in the sense that their elements can be listed? The answer requires making the notion of "listing" precise. A set whose elements can be matched one-to-one with a subset of the natural numbers is one that can — at least in principle — be enumerated by a procedure that assigns a natural number label to each element. Sets that admit such an enumeration are called *countable*; sets that do not are genuinely larger. [definition:Countable Set] A [set](/page/Set) $X$ is **countable** if there exists an injection from $X$ into $\mathbb{N}$. Equivalently, $X$ is countable if $X$ is finite or if there exists a bijection $f: \mathbb{N} \to X$. [/definition] The definition splits countable sets into two species. A finite set $\{x_1, x_2, \ldots, x_n\}$ is countable because the map $x_k \mapsto k$ injects it into $\mathbb{N}$. A countably infinite set is one that can be written as a list $x_1, x_2, x_3, \ldots$ indexed by the natural numbers, with every element of the set appearing exactly once. The empty set $\varnothing$ is countable: it is finite, and the empty [function](/page/Function) $\varnothing \to \mathbb{N}$ is an injection. Not every infinite set is countable, and the distinction between countable and uncountable infinities is the central theme of this article. The following definitions isolate the two cases. [definition:Countably Infinite Set] A set $X$ is **countably infinite** if there exists a bijection $f : \mathbb{N} \to X$. Equivalently, $X$ is countably infinite if it is infinite and countable. [/definition] [definition:Uncountable Set] A set $X$ is **uncountable** if $X$ is infinite and not countable — that is, there is no injection from $X$ into $\mathbb{N}$. [/definition] The convention that $\mathbb{N} = \{1, 2, 3, \ldots\}$ starts at $1$ (not $0$) is used throughout this article. ## Equivalent Characterisations The definition of countability via injection into $\mathbb{N}$ is clean, but in practice one often wants to verify countability by producing a surjection from $\mathbb{N}$, without worrying about constructing an injection or a bijection. The following theorem says that all three approaches are equivalent, giving the working mathematician flexibility to choose whichever is most convenient. [quotetheorem:753] The characterisation via surjection is especially useful. To show a set $X$ is countable, it suffices to describe a procedure that lists every element of $X$ — even with repetitions. Conversely, if a set is countable and non-empty, we can always produce a surjection from $\mathbb{N}$ onto it, which means we can "enumerate" its elements as a (possibly repeating) [sequence](/page/Sequence) $x_1, x_2, x_3, \ldots$ that eventually hits every element. The characterisation via injection is the workhorse for proving countability indirectly: embed $X$ into a known countable set, and you are done. ## Closure Properties Three closure properties underpin almost every countability argument: countability is inherited by subsets, preserved under finite products, and stable under countable unions. These properties together make the class of countable sets remarkably robust — they allow us to assemble countable sets from countable building blocks, and to verify countability of complicated sets by reducing to simpler ones. ### Subsets of Countable Sets Every subset of a countable set inherits the property of being listable — restricting an enumeration to a subset simply produces a (possibly shorter) enumeration. This hereditary property is the simplest of the three closure results, but it is used constantly: it says that to prove a set is countable, it suffices to embed it into any set already known to be countable. [quotetheorem:752] The converse does not hold: a set that contains an uncountable subset is itself uncountable (by contrapositive), but a countable set cannot contain an uncountable subset. This asymmetry — countability passes to subsets but uncountability passes to supersets — is a recurring theme. ### Products of Countable Sets The Cartesian product $\mathbb{N} \times \mathbb{N}$ is the prototypical example. At first it may seem that $\mathbb{N} \times \mathbb{N}$ should be "larger" than $\mathbb{N}$, since it is two-dimensional. But a clever enumeration scheme shows that the pairs can be listed in a single [sequence](/page/Sequence). The key insight is to traverse the pairs not row-by-row (which would never leave the first row) but along finite anti-diagonals. [quotetheorem:754] The diagonal enumeration is worth internalising as a visual technique. Imagine the pairs $(x, y)$ arranged in an infinite grid. Instead of trying to traverse the grid row by row (which would never leave the first row), we traverse it along finite diagonals: first the diagonal of sum $2$, then sum $3$, then sum $4$, and so on. Each diagonal is finite, so we make progress across the entire grid. By induction, the product $\mathbb{N}^k = \mathbb{N} \times \mathbb{N} \times \cdots \times \mathbb{N}$ ($k$ factors) is countable for every $k \in \mathbb{N}$. More generally, if $A$ and $B$ are countable, then $A \times B$ is countable: injections $A \hookrightarrow \mathbb{N}$ and $B \hookrightarrow \mathbb{N}$ compose to give an injection $A \times B \hookrightarrow \mathbb{N} \times \mathbb{N}$, and $\mathbb{N} \times \mathbb{N}$ is countable. ### Countable Unions of Countable Sets The most powerful of the three closure properties states that a countable union of countable sets is countable. This is the theorem invoked most frequently in practice, and its proof combines the well-ordering principle with the two-dimensional dovetailing idea from the product case. [quotetheorem:755] The intuition behind this proof is a two-dimensional "dovetailing" argument. Arrange the sets $A_1, A_2, A_3, \ldots$ as rows of an infinite table. Each row is countable, so it can be listed as a sequence. An element $x$ that appears in multiple rows is assigned to the row with the smallest index, breaking ties via the well-ordering principle. The injection $h$ then encodes $x$ as a pair (row number, position within that row), and we already know that the set of all such pairs is countable. ## The Rationals Are Countable The rational numbers $\mathbb{Q}$ are dense in $\mathbb{R}$: between any two distinct real numbers there are infinitely many rationals. It is therefore surprising that $\mathbb{Q}$ is no larger than $\mathbb{N}$. The proof is a direct application of the countable union theorem, decomposing $\mathbb{Q}$ into countably many countable slices. [quotetheorem:756] The decomposition into slices $\{m/n : m \in \mathbb{Z}\}$ deliberately allows the same rational number to appear in multiple slices (for instance, $1/2$ and $2/4$ appear in different slices). This is perfectly acceptable: the countable union theorem does not require the sets $A_i$ to be disjoint. The well-ordering mechanism in the proof of that theorem handles duplicates automatically by assigning each element to its first occurrence. [example:Enumerating Rationals] **Enumerating the first few rationals.** The slices are: - $n = 1$: $\ldots, -2, -1, 0, 1, 2, \ldots$ - $n = 2$: $\ldots, -1, -1/2, 0, 1/2, 1, \ldots$ - $n = 3$: $\ldots, -2/3, -1/3, 0, 1/3, 2/3, \ldots$ Dovetailing across these slices (and skipping duplicates), a listing of $\mathbb{Q}$ begins: \begin{align*} 0,\; 1,\; -1,\; 2,\; -2,\; \tfrac{1}{2},\; -\tfrac{1}{2},\; 3,\; -3,\; \tfrac{1}{3},\; -\tfrac{1}{3},\; \tfrac{2}{3},\; -\tfrac{2}{3},\; \ldots \end{align*} Every rational number eventually appears because every $m/n$ lies in the $n$-th slice, and the dovetailing process visits every entry of every slice in finite time. [/example] ## Algebraic Numbers Are Countable An algebraic number is a real number that satisfies a [polynomial](/page/Polynomial) equation with integer coefficients. Every rational number is algebraic (since $p/q$ is a root of $qx - p = 0$), and so are irrational numbers like $\sqrt{2}$ (a root of $x^2 - 2 = 0$) and $\sqrt[3]{5} + \sqrt{2}$ (which satisfies a polynomial of degree $6$). Despite the richness of the algebraic numbers, the set of all of them is still countable — a fact that depends on the same closure properties we have already established. [quotetheorem:757] The proof reveals the structural reason why the algebraic numbers are countable: they are parametrised by integer polynomials, which are in turn parametrised by finite tuples of integers. At each level, the objects form a countable set, and countable unions of countable sets remain countable. The finiteness of the root set of each polynomial is essential — without it, the argument would fail. This is not merely a technicality: a single equation like $\sin(x) = 0$ has infinitely many roots, and if we allowed transcendental equations the conclusion would break down. ## Uncountable Sets and Cantor's Diagonal Argument The closure properties of the previous sections show that many naturally occurring sets are countable: $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{A}$, the set of all finite strings over a countable alphabet, and so on. One might begin to wonder whether *every* infinite set is countable. Cantor's diagonal argument shatters this expectation: the real numbers cannot be listed, no matter how cleverly the list is arranged. This single result launched the theory of uncountable sets and the hierarchy of infinities. [quotetheorem:758] The diagonal argument is the most important proof technique in the theory of cardinality, and its structure reappears in many areas of mathematics and computer science — from the undecidability of the halting problem to the existence of non-[measurable](/page/Measure%20Theory) sets. The argument works by a *self-referential contradiction*: given any proposed enumeration, we construct a real number that differs from the $n$-th listed number in the $n$-th decimal place, guaranteeing that it is not on the list. The name "diagonal argument" comes from the fact that we look at the "diagonal" entries $d_{11}, d_{22}, d_{33}, \ldots$ of the decimal expansion table and change each one. Two subtle points deserve attention. First, the choice of replacement digits $1$ and $2$ (rather than, say, $0$ and $9$) is deliberate. It avoids the trap of dual representations: the number $0.1000\ldots$ and $0.0999\ldots$ are the same real number, so a careless choice of digits could produce a number $r$ that *is* on the list under a different decimal expansion. By restricting to digits $1$ and $2$, the constructed number has a unique decimal expansion, and the argument goes through cleanly. Second, the argument is inherently non-constructive in the following sense: it does not produce a specific real number that is missing from a specific list, but rather shows that *for every* proposed list, some real number is missing. ### Uncountably Many Transcendentals The countability of $\mathbb{A}$ and the uncountability of $\mathbb{R}$ together yield a striking corollary that demonstrates the power of cardinality arguments: the transcendental numbers not only exist, but vastly outnumber the algebraic numbers. [quotetheorem:763] This is a remarkable non-constructive existence proof. Without exhibiting a single transcendental number, we have shown that the transcendentals vastly outnumber the algebraic numbers. In a precise cardinality sense, "almost every" real number is transcendental — the algebraic numbers, despite including all rationals and many familiar irrationals, are a negligible sliver of the real line. Constructive proofs that specific numbers (such as $e$ or $\pi$) are transcendental require much harder analytic arguments (Hermite's theorem for $e$, the Lindemann–Weierstrass theorem for $\pi$), but the *existence* of transcendental numbers comes for free from a simple counting argument. ### Cantor's Theorem The diagonal argument for $\mathbb{R}$ is actually a shadow of a much more general phenomenon: for *any* set $X$, the [power set](/page/Power%20Set) $\mathcal{P}(X)$ is strictly larger than $X$. This result generates an infinite hierarchy of ever-larger infinities and shows that there is no "largest set." [quotetheorem:759] Cantor's theorem has a profound consequence: there is no largest set. Given any set $X$, the power set $\mathcal{P}(X)$ is strictly larger, $\mathcal{P}(\mathcal{P}(X))$ is larger still, and so on. This produces an infinite hierarchy of ever-larger infinities: \begin{align*} |\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots \end{align*} The first of these cardinalities, $|\mathbb{N}|$, is denoted $\aleph_0$ and is the cardinality of every countably infinite set. The cardinality $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}| = 2^{\aleph_0}$ is the *cardinality of the continuum*. Whether there exists a set whose cardinality lies strictly between $\aleph_0$ and $2^{\aleph_0}$ is the famous [Continuum Hypothesis](/page/Continuum%20Hypothesis), which is independent of the standard axioms of [set theory](/page/Set%20Theory) (ZFC). ## The Schroeder–Bernstein Theorem In many applications, we want to show that two sets $A$ and $B$ have the same cardinality. Constructing a bijection directly can be difficult — the bijection must handle every element of both sets, and the interactions between different parts of the sets can be subtle. The Schroeder–Bernstein theorem provides a powerful shortcut: it suffices to find an injection in each direction. The theorem's statement is intuitive — "if $A$ fits inside $B$ and $B$ fits inside $A$, they must be the same size" — but its proof is genuinely subtle, requiring a careful partition of both sets based on "ancestor sequences." [quotetheorem:760] The Schroeder–Bernstein theorem is used constantly in [set theory](/page/Set%20Theory) and [analysis](/page/Real%20Analysis). In practice, it reduces the problem of constructing a bijection — which requires a single map that is simultaneously injective and surjective — to the easier problem of constructing two separate injections, one in each direction. One important caveat: the Schroeder–Bernstein theorem does not hold for all algebraic structures. There exist [groups](/page/Group) $G$ and $H$ such that $G$ embeds into $H$ and $H$ embeds into $G$, but $G$ and $H$ are not isomorphic. There exist [topological spaces](/page/Topology) with the analogous property. The theorem is purely a statement about sets and functions; it says nothing about preserving algebraic or topological structure. ## Common Techniques Several recurring strategies appear throughout countability arguments. Recognising them explicitly helps both in solving problems and in reading proofs. **Injection into a known countable set.** To show $X$ is countable, find an injection $X \hookrightarrow C$ where $C$ is already known to be countable. This is the most direct method and follows from the subset closure property. **Decompose and apply the countable union theorem.** Write $X = \bigcup_{i \in I} A_i$ where $I$ is countable and each $A_i$ is countable. This is the strategy used for $\mathbb{Q}$ (slices by denominator) and $\mathbb{A}$ (slices by polynomial degree). The key is finding the right decomposition. **Encode as tuples.** Many naturally occurring sets can be parametrised by finite tuples of integers or natural numbers. Since $\mathbb{N}^k$ is countable for each $k$, any set that injects into $\mathbb{N}^k$ is countable. This underlies the proof that polynomials of fixed degree are countable. **Diagonal argument for uncountability.** To show a set is uncountable, assume a listing exists and construct an element that differs from the $n$-th listed element in a controlled way. The construction must ensure uniqueness of representation (avoiding the dual-expansion issue). **Schroeder–Bernstein for equicardinality.** To show $|A| = |B|$, find injections in both directions rather than constructing a bijection directly. ## References - Cantor, G., "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen," *Journal für die reine und angewandte Mathematik* **77** (1874), 258–262. - Cantor, G., "Ueber eine elementare Frage der Mannigfaltigkeitslehre," *Jahresbericht der Deutschen Mathematiker-Vereinigung* **1** (1891), 75–78. - Halmos, P., *Naive Set Theory*, Springer (1974). - Rudin, W., *Principles of Mathematical Analysis*, 3rd edition, McGraw-Hill (1976). - Enderton, H. B., *Elements of Set Theory*, Academic Press (1977).