# The set of rational numbers is countable

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.

# 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. %%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.