Rationals are Countable

Cantor defined a set to be countable if you can find a way to enumerate all of its elements, even if the enumeration never finishes. The natural numbers $\mathbb{N}$ are the standard example of a set with infinitely many elements that is still countable. The usual proof of the fact that the rationals $\mathbb{Q}$ are countable is by Cantor’s enumeration which is visualized below. The (positive) rationals are represented in a 2D grid as fractions where one axis is the numerator and the other the denominator. (The fractions in blue are not reduced and thus some numbers appear more than once, however this doesn’t affect the countability result.) The enumeration is defined by picking up the fractions in a spiral fashion.

A non-visual proof

Mathematically, the enumeration corresponds to finding a mapping from $\mathbb{N}$ to $\mathbb{Q}$ that visits all elements in $\mathbb{Q}$ at some point, i.e., it is surjective. For simplicity, let’s only consider the non-negative rationals $\mathbb{Q}^+$. If we find a surjective mapping $f: \mathbb{N} \rightarrow \mathbb{Q}^+$, we can define the surjective mapping $f’: \mathbb{N} \rightarrow \mathbb{Q}, x \mapsto \begin{cases}
f(k) & \text{if } x=2k\\
-f(k) & \text{if } x=2k+1
\end{cases}$ proving the statement. Choose $f: \mathbb{N} \rightarrow \mathbb{Q}^+, x \mapsto \begin{cases}
\frac{a}{b} & \text{if } x=2^a3^b\\
0 & \text{otherwise}
\end{cases}$ which is well-defined because each integer has a unique prime factorization, and for each $\frac{a}{b} \in \mathbb{Q}^+$ there is a pre-image $2^a3^b$, i.e., $f$ is surjective. Thus $|\mathbb{Q}| \leq |\mathbb{N}|$.


Get updates on new content.

No spam, no sales pitch, I promise. I don't like these myself.

Similar Work

Leave a Reply