Proof that the rationals are countable

Proof

We find injections in both directions and apply the Schröder–Bernstein theorem.

1. Let $x \in \Q$ be a rational number. Then $x = p/q$ for some $p \in \Z$ and some integer $q \ge 1$.
2. So the set $D_x = \{q \in \N : q \ge 1,\ qx \in \Z\}$ is nonempty. By the well-ordering principle, it has a least element $q_x$.
3. Define $r \colon \Q \to \Z \times \N$ by $r(x) = (q_x x,\ q_x)$. Its first entry is an integer by the choice of $q_x$.
4. The map $r$ is injective. If $r(x) = r(y)$, then $q_x = q_y$ and $q_x x = q_y y$. Dividing by $q_x \ge 1$ gives $x = y$.
5. By the integers are countable, there is a bijection $f \colon \N \to \Z$. Its inverse $f^{-1} \colon \Z \to \N$ is a bijection, so it is injective. Hence $\Z$ is countable.
6. The set $\N$ is countable, through the identity map. By the product of countable sets is countable, there is an injection $s \colon \Z \times \N \to \N$.
7. The composite $s \circ r \colon \Q \to \N$ is injective.
8. The inclusion $\N \to \Q$, $n \mapsto n$, is injective.
9. By the Schröder–Bernstein theorem, steps 7 and 8 give a bijection $\N \to \Q$. So $\Q$ is countably infinite.