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

I want to prove that $\mathbb{Q}$ is countable. So basically, I could find a bijection from $\mathbb{Q}$ to $\mathbb{N}$. But I have also recently proved that $\mathbb{Z}$ is countable, so is it equivalent to find a bijection from $\mathbb{Q}$ to $\mathbb{Z}$?

Solution 1:

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.

Solution 2:

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}$