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

• Sure. Better yet, it's sufficient to find an injection from $\mathbb Q$ to $\mathbb Z$. Or for that matter a surjection from $\mathbb Z$ to $\mathbb Q$, or from $\mathbb N$ to $\mathbb Q$. – bof Feb 1 '14 at 8:25
• is just an injection sufficient to prove countability, though? – furashu Feb 1 '14 at 8:33
• I guess it depends on how you define "countable". Are finite sets countable? If not, then besides finding an injection from $\mathbb Q$ to $\mathbb Z$, you also have to prove that $\mathbb Q$ is infinite. But I you already know that. – bof Feb 1 '14 at 8:36
• i would say finite sets are not "countable" but "finite" .. seems weird, but countable is a term I would reserve specifically for distinction between cardinality of infinite sets. – furashu Feb 1 '14 at 8:40
• Fine. $\mathbb Q$ is an infinite set. An infinite set is countable if it has an injection into $\mathbb N$. Or into any countable set, such as $\mathbb Z$, which you already know is countable. – bof Feb 1 '14 at 8:46

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

• this is one of the most impressive and elegant answers i've seen on here, well done! – furashu Feb 1 '14 at 9:18
• Instead of using prime factorizations, you could just map the reduced fraction $\frac mn$ to the integer $2^m(2n+1)$ – bof Feb 1 '14 at 9:23
• @bof True. This would have saved me like ten minutes of typing. – William Feb 1 '14 at 9:27
• @William can you explain what bof said? what's the significance of that integer? – furashu Feb 1 '14 at 9:39
• @William oh i am checking it now, I just like to know where things coem from, to get a glimpse on peoples intuition and knowledge. – furashu Feb 1 '14 at 9:46

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

• Is mapping from Z x Z the same as mapping from Z, though? – furashu Feb 1 '14 at 8:44
• Lemma : If $A$ is countable, then $A \times A$ is countable. – Euler....IS_ALIVE Feb 1 '14 at 8:53
• @Euler....IS_ALIVE How does one prove that? – Arjang Jan 19 '17 at 12:23

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

• I didn't understand this. Can you explain why we can give a completely different meaning to the slash (from its established definition as the division symbol to a numeral in base-11) so as to create an injection. – Mr Reality Jan 12 at 20:21
• Ok. Write out a rational number which has a division symbol slash, say for example 3/4. Now replace slash by x. (Remember x is roman numeral for ten). So this becomes 3x4 which is a 3-digit number in base 11 system. The value of this is three eleven squared plus ten elevens and 4 which in base 10 is $(3\times 121 + 10 \times 11 +4= 363+110+4=477$. SO the function sends $3/4$ to 477. – P Vanchinathan Jan 13 at 2:08

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$

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.