The set of rational numbers is countable

by Patrick Stevens Jul 3 2016

Although there are "lots and lots" of rational numbers, there are still only countably many of them.

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.


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. %%note:That 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.