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}$?
 A: 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.$$
A: 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.
A: 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}$
A: I read this proof in Amer. Math. Monthly.
Suffices to find out an injective function from the set of positive rationals to positive integers.
Consider the representation of numbers in base 11, where the 11 digits used are $0,1,2,3, ..., 9, /$ (yes, it is a slash as digit for the number ten).
Now the rational number $7/83$ represents the 4-digit base-11 positive integer:
 $(7\times 11^3) + (10\times 11^2) + (8\times 11) + 3$.
A: A002487 Stern's diatomic series (or Stern-Brocot sequence)
Also called fusc(n) [Dijkstra]. a(n)/a(n+1) runs through all
the reduced nonnegative rationals exactly once [Stern; Calkin and Wilf].
https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD570.html
fusc(1) = 1
fusc(2n) = fusc(n)
fusc(2n+1) = fusc(n) + fusc(n+1)

And it seems that fusc(k)/fusc(k+1) gives the positive rational numbers. 
There was also a contrieved proof recently that fusc does what it does here:
https://www.isa-afp.org/browser_info/current/AFP/Stern_Brocot/document.pdf
Using the sign of Z we could create a mapping to the positive and negative rational numbers.
A: Consider for $n=2,3,4,\ldots$ the sets
$$A_n=\left\{\frac pq :(p,q)=1,p,q>0,p+q=n\right\}$$
Claim Each $A_n$ is finite, and $\Bbb Q^+=A_2\cup A_3\cup A_4\cup\dots$
