How to prove that $\mathbb{Q}$ ( the rationals) is a countable set

Clearly $\mathbb{Z}$ injects into $\mathbb{Q}$.

Let $p_i$ enumerate all the prime numbers.

If $q \neq 0, 1, -1$, let $q = \pm \frac{p_{i_0}^{n_0} ... p_{i_k}^{n_k}}{p_{j_0}^{m_0} ... p_{j_p}^{m_p}}$ be the prime decomposition the numerator and denominator of $q$ written in simplest form. Define

$\Phi(q) = \begin{cases} 0 & \quad q = 0 \\ 1 & \quad q = 1 \\ -1 & \quad q = -1 \\ p_{2 i_0}^{n_0} ... p_{2 i_k}^{n_k} p_{2 j_0 + 1}^{m_0} ... p_{2 j_p + 1}^{m_p} & \quad q = \frac{p_{i_0}^{n_0} ... p_{i_k}^{n_k}}{p_{j_0}^{m_0} ... p_{j_p}^{m_p}} \\ - p_{2 i_0}^{n_0} ... p_{2 i_k}^{n_k} p_{2 j_0 + 1}^{m_0} ... p_{2 j_p + 1}^{m_p} & \quad q = - \frac{p_{i_0}^{n_0} ... p_{i_k}^{n_k}}{p_{j_0}^{m_0} ... p_{j_p}^{m_p}} \end{cases}$

$\Phi$ is an injection of $\mathbb{Q}$ into $\mathbb{Z}$.

By the Cantor Schroder Theorem, there is a bijection between $\mathbb{Z}$ and $\mathbb{Q}$.

---

As bof mentioned, a nicer injection would be

$\Phi(q) = \begin{cases} 0 & \quad q = 0 \\ 1 & \quad q = 1 \\ -1 & \quad q = -1 \\ 2^m (2n + 1) & \quad q = \frac{m}{n} \text{ simplest form } \\ - 2^m(2n + 1) & \quad q = - \frac{m}{n} \text{ simplest form} \end{cases}$

If you know that $\mathbb{Z}$ is countable, you know there is a bijection $\chi:\mathbb{N} \rightarrow \mathbb{Z}$. Hence, it is sufficient to find a bijection $\nu:\mathbb{Z} \rightarrow \mathbb{Q}$ since then $\chi \circ \nu$ is a bijection between $\mathbb{N}$ and $\mathbb{Q}$.

In any case, the following figure illustrates a bijection between $\mathbb{Z}$ and $\mathbb{Q}$.

We follow the worm back and forth "counting" the rational numbers, skipping any numbers that are not simplified fractions.

Hint: There is a natural map $$\left\{ \begin{array}{ccc} \mathbb{Z} \times \mathbb{Z}_{>0} & \to & \mathbb{Q} \\ (a,b) & \mapsto & \frac{a}{b} \end{array} \right.$$