The set \(\mathbb{Q}\) of rational numbers is countable: that is, there is a bijection between \(\mathbb{Q}\) and the set \(\mathbb{N}\) of natural numbers.

Proof

By the Schröder-Bernstein theorem, it is enough to find an injection \(\mathbb{N} \to \mathbb{Q}\) and an injection \(\mathbb{Q} \to \mathbb{N}\).

The former is easy, because \(\mathbb{N}\) is a subset of \(\mathbb{Q}\) so the identity injection \(n \mapsto \frac{n}{1}\) works.

For the latter, we may define a function \(\mathbb{Q} \to \mathbb{N}\) as follows. Take any rational in its lowest terms, as \(\frac{p}{q}\), say. noteThat is, the GCD of the numerator \(p\) and denominator \(q\) is \(1\). At most one of \(p\) and \(q\) is negative (if both are negative, we may just cancel \(-1\) from the top and bottom of the fraction); by multiplying by \(\frac{-1}{-1}\) if necessary, assume without loss of generality that \(q\) is positive. If \(p = 0\) then take \(q = 1\).

Define \(s\) to be \(1\) if \(p\) is positive, and \(2\) if \(p\) is negative.

Then produce the natural number \(2^p 3^q 5^s\).

The function \(f: \frac{p}{q} \mapsto 2^p 3^q 5^s\) is injective, because prime factorisations are unique so if \(f\left(\frac{p}{q}\right) = f \left(\frac{a}{b} \right)\) (with both fractions in their lowest terms, and \(q\) positive) then \(|p| = |a|, q=b\) and the sign of \(p\) is equal to the sign of \(a\). Hence the two fractions were the same after all.