Proof that the Rationals are Countable

One of the most surprising results in set theory is that the rational numbers $\mathbb{Q}$ , despite being dense in the real line, have the same cardinality as the natural numbers. This stands in stark contrast to the real numbers, which are uncountable. The proof illustrates powerful techniques for showing countability.

TheoremCountability of the Rationals

The set of rational numbers $\mathbb{Q}$ is countably infinite, i.e., $|\mathbb{Q}| = |\mathbb{N}| = \aleph_0$ .

Proof

We will construct an explicit bijection between $\mathbb{N}$ and $\mathbb{Q}$ , though showing that $\mathbb{Q}$ is countable only requires an injection into $\mathbb{N}$ or a surjection from $\mathbb{N}$ .

Method 1: Cantor's Enumeration

Every rational number can be written uniquely in lowest terms as $p/q$ where $q > 0$ and $\gcd(p, q) = 1$ . We arrange the positive rationals in an infinite array:

\begin{array}{ccccccc} 1/1 & \to & 1/2 & & 1/3 & \to & 1/4 & \cdots \\ \downarrow & \nearrow & & \searrow & & \nearrow & \\ 2/1 & & 2/2 & & 2/3 & & 2/4 & \cdots \\ & \searrow & & \nearrow & & \searrow & \\ 3/1 & & 3/2 & & 3/3 & & 3/4 & \cdots \\ \downarrow & \nearrow & & \searrow & & \nearrow & \\ 4/1 & & 4/2 & & 4/3 & & 4/4 & \cdots \\ \vdots & & \vdots & & \vdots & & \vdots & \end{array}

where row $p$ and column $q$ contains $p/q$ . We enumerate by following diagonal paths (Cantor's diagonal argument):

1/1, \quad 2/1, 1/2, \quad 3/1, 2/2, 1/3, \quad 4/1, 3/2, 2/3, 1/4, \quad \ldots

Skipping duplicates (like $2/2 = 1/1$ ), we get an enumeration of all positive rationals. Including $0$ and negative rationals (by interleaving), we obtain an enumeration of all of $\mathbb{Q}$ .

Method 2: Pairing Function

Define the height of a rational $p/q$ in lowest terms (with $q > 0$ ) as $h(p/q) = |p| + q$ . For each finite height $n$ , there are only finitely many rationals of height $n$ . List all rationals in order of increasing height, breaking ties arbitrarily:

Height 1: $0/1$
Height 2: $1/1, -1/1$
Height 3: $2/1, -2/1, 1/2, -1/2$
Height 4: $3/1, -3/1, 1/3, -1/3, 2/3, -2/3$
...

This produces an enumeration $\mathbb{Q} = \{q_0, q_1, q_2, \ldots\}$ , giving a bijection $n \mapsto q_n$ from $\mathbb{N}$ to $\mathbb{Q}$ .

Method 3: Using Cantor Pairing

The Cantor pairing function $\pi: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a bijection defined by:

\pi(m, n) = \frac{(m + n)(m + n + 1)}{2} + n

This function is bijective, showing $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$ .

Now, the positive rationals are in bijection with $(\mathbb{N} \setminus \{0\}) \times (\mathbb{N} \setminus \{0\})$ via $(m, n) \mapsto m/n$ (not injective, but surjective). Since there is a surjection from $\mathbb{N} \times \mathbb{N}$ onto $\mathbb{Q}^+$ , and $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$ , we have $|\mathbb{Q}^+| \leq |\mathbb{N}|$ . Combined with the obvious injection $\mathbb{N} \hookrightarrow \mathbb{Q}$ , Schröder-Bernstein gives $|\mathbb{Q}| = |\mathbb{N}|$ .

■

Remark

The key insight is that $\mathbb{Q}$ can be organized into a sequence of finite layers (by height or diagonal), allowing systematic enumeration. This strategy works for any countable union of countable sets—a general theorem we prove next.

TheoremCountable Union of Countable Sets

If $\{A_n : n \in \mathbb{N}\}$ is a countable collection of countable sets, then $\bigcup_{n=0}^\infty A_n$ is countable.

Proof

For each $n$ , since $A_n$ is countable, there is an enumeration $A_n = \{a_{n,0}, a_{n,1}, a_{n,2}, \ldots\}$ (possibly finite). Arrange these in an array:

\begin{array}{ccccc} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} & \cdots \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} & \cdots \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} & \cdots \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

Enumerate by diagonals as before. This gives a surjection $\mathbb{N} \twoheadrightarrow \bigcup_{n=0}^\infty A_n$ , proving the union is countable.

■

ExampleApplications of Countability

Using the theorem that countable unions of countable sets are countable:

Algebraic numbers: The set of roots of polynomials with rational coefficients is countable (countable union over degree, each degree is countable)
Finite sequences: The set of all finite sequences of natural numbers is countable: $\bigcup_{n=0}^\infty \mathbb{N}^n$ is countable
Computable reals: The set of Turing-computable real numbers is countable (countable number of Turing machines)
Rational points: The set $\mathbb{Q}^n = \mathbb{Q} \times \cdots \times \mathbb{Q}$ (n times) is countable for any finite $n$

Remark

The proof that countable unions of countable sets are countable requires the axiom of countable choice, a weak form of the axiom of choice. Without it, we cannot guarantee that each countable set $A_n$ has an enumeration simultaneously. This shows that even seemingly elementary results in set theory can depend on choice principles.

TheoremUncountability of the Reals

In contrast to $\mathbb{Q}$ , the real numbers are uncountable: $|\mathbb{R}| > |\mathbb{N}|$ . In fact, $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$ .

Proofsketch

Cantor's diagonal argument: Suppose $\mathbb{R}$ were countable with enumeration $\{r_0, r_1, r_2, \ldots\}$ . Write each $r_n$ in decimal expansion. Construct a new real $r$ by ensuring its $n$ -th decimal digit differs from the $n$ -th digit of $r_n$ . Then $r \neq r_n$ for all $n$ , contradicting completeness of the enumeration.

■

ExampleThe Cardinality Hierarchy

We now have an infinite hierarchy of cardinalities:

\begin{align*} |\emptyset| &= 0 \\ |\mathbb{N}| &= \aleph_0 \text{ (countably infinite)} \\ |\mathbb{Q}| &= \aleph_0 \\ |\mathbb{R}| &= 2^{\aleph_0} = \mathfrak{c} \text{ (the continuum)} \\ |\mathcal{P}(\mathbb{R})| &= 2^\mathfrak{c} \\ |\mathcal{P}(\mathcal{P}(\mathbb{R}))| &= 2^{2^\mathfrak{c}} \\ &\vdots \end{align*}

The continuum hypothesis (CH) conjectures that there is no cardinality strictly between $\aleph_0$ and $\mathfrak{c}$ , i.e., $\mathfrak{c} = \aleph_1$ . Kurt Gödel and Paul Cohen showed that CH is independent of ZFC: it can neither be proved nor disproved from the standard axioms.

The countability of $\mathbb{Q}$ and uncountability of $\mathbb{R}$ reveal the subtle and counterintuitive nature of infinity. Despite $\mathbb{Q}$ being dense in $\mathbb{R}$ , it has "measure zero" from the perspective of cardinality. These results form the foundation for modern analysis and topology.