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}$?
$\endgroup$ 87 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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}$
$\endgroup$ 10 $\begingroup$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.$$
$\endgroup$ 4 $\begingroup$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$.
$\endgroup$ 2 $\begingroup$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].
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:
Using the sign of Z we could create a mapping to the positive and negative rational numbers.
$\endgroup$ $\begingroup$Let $[0,1)_{\,\Bbb Q}$ denote the interval of rational numbers greater than or equal to $0$ and less than $1$.
There is a natural bijection
$\tag 1 \psi: \Bbb Z \times [0,1)_{\,\Bbb Q} \to \Bbb Q$$\tag 2 (m,q) \mapsto m + q$
Since the Cartesian product of two countable sets is countable (see for example the wiki article Pairing function), if $[0,1)_{\,\Bbb Q}$ is countable then so is $\Bbb Q$.
We can build a $1:1$ correspondence between $\Bbb N$ and $[0,1)_{\,\Bbb Q}$ using the theory
$\quad$ Generating All Coprime Pairs
The reader's eyes would glaze over if we fastidiously filled in the details. But a Python program that I adapted from stackoverflow will bijectively enumerate the first $1000$ rational numbers using the algorithm. (see scroll bar).
Python Program
from fractions import Fraction
def coprimes(): yield (2, 1) yield (3, 1) for m, n in coprimes(): yield (2*m - n, m) yield (2*m + n, m) yield (m + 2*n, n)
print(Fraction(0,1), '', end='')
pairs = coprimes()
for _ in range(1000): m,n = next(pairs) print(Fraction(n,m), '', end='')
print('...')OUTPUT
0 1/2 1/3 2/3 2/5 1/4 3/5 3/7 1/5 3/4 3/8 2/7 5/8 5/12 2/9 4/7 4/9 1/6 5/7 5/13 3/11 7/11 7/17 3/13 5/9 5/11 1/7 4/5 4/11 3/10 8/13 8/19 3/14 7/12 7/16 2/11 8/11 8/21 5/18 12/19 12/29 5/22 9/16 9/20 2/13 7/10 7/18 4/15 9/14 9/22 4/17 6/11 6/13 1/8 7/9 7/19 5/17 13/21 13/31 5/23 11/19 11/25 3/17 11/15 11/29 7/25 17/27 17/41 7/31 13/23 13/29 3/19 9/13 9/23 5/19 11/17 11/27 5/21 7/13 7/15 1/9 5/6 5/14 4/13 11/18 11/26 4/19 10/17 10/23 3/16 13/18 13/34 8/29 19/30 19/46 8/35 14/25 14/31 3/20 12/17 12/31 7/26 16/25 16/39 7/30 11/20 11/24 2/15 11/14 11/30 8/27 21/34 21/50 8/37 18/31 18/41 5/28 19/26 19/50 12/43 29/46 29/70 12/53 22/39 22/49 5/32 16/23 16/41 9/34 20/31 20/49 9/38 13/24 13/28 2/17 10/13 10/27 7/24 18/29 18/43 7/32 15/26 15/34 4/23 14/19 14/37 9/32 22/35 22/53 9/40 17/30 17/38 4/25 11/16 11/28 6/23 13/20 13/32 6/25 8/15 8/17 1/10 9/11 9/25 7/23 19/31 19/45 7/33 17/29 17/39 5/27 21/29 21/55 13/47 31/49 31/75 13/57 23/41 23/51 5/33 19/27 19/49 11/41 25/39 25/61 11/47 17/31 17/37 3/23 15/19 15/41 11/37 29/47 29/69 11/51 25/43 25/57 7/39 27/37 27/71 17/61 41/65 41/99 17/75 31/55 31/69 7/45 23/33 23/59 13/49 29/45 29/71 13/55 19/35 19/41 3/25 13/17 13/35 9/31 23/37 23/55 9/41 19/33 19/43 5/29 17/23 17/45 11/39 27/43 27/65 11/49 21/37 21/47 5/31 13/19 13/33 7/27 15/23 15/37 7/29 9/17 9/19 1/11 6/7 6/17 5/16 14/23 14/33 5/24 13/22 13/30 4/21 18/25 18/47 11/40 26/41 26/63 11/48 19/34 19/42 4/27 17/24 17/44 10/37 23/36 23/56 10/43 16/29 16/35 3/22 18/23 18/49 13/44 34/55 34/81 13/60 29/50 29/66 8/45 30/41 30/79 19/68 46/73 46/111 19/84 35/62 35/78 8/51 25/36 25/64 14/53 31/48 31/76 14/59 20/37 20/43 3/26 17/22 17/46 12/41 31/50 31/74 12/55 26/45 26/59 7/40 25/34 25/66 16/57 39/62 39/94 16/71 30/53 30/67 7/44 20/29 20/51 11/42 24/37 24/59 11/46 15/28 15/32 2/19 14/17 14/39 11/36 30/49 30/71 11/52 27/46 27/62 8/43 34/47 34/89 21/76 50/79 50/121 21/92 37/66 37/82 8/53 31/44 31/80 18/67 41/64 41/100 18/77 28/51 28/61 5/38 26/33 26/71 19/64 50/81 50/119 19/88 43/74 43/98 12/67 46/63 46/121 29/104 70/111 70/169 29/128 53/94 53/118 12/77 39/56 39/100 22/83 49/76 49/120 22/93 32/59 32/69 5/42 23/30 23/62 16/55 41/66 41/98 16/73 34/59 34/77 9/52 31/42 31/82 20/71 49/78 49/118 20/89 38/67 38/85 9/56 24/35 24/61 13/50 28/43 28/69 13/54 17/32 17/36 2/21 13/16 13/36 10/33 27/44 27/64 10/47 24/41 24/55 7/38 29/40 29/76 18/65 43/68 43/104 18/79 32/57 32/71 7/46 26/37 26/67 15/56 34/53 34/83 15/64 23/42 23/50 4/31 19/24 19/52 14/47 37/60 37/88 14/65 32/55 32/73 9/50 35/48 35/92 22/79 53/84 53/128 22/97 40/71 40/89 9/58 30/43 30/77 17/64 38/59 38/93 17/72 25/46 25/54 4/33 16/21 16/43 11/38 28/45 28/67 11/50 23/40 23/52 6/35 20/27 20/53 13/46 32/51 32/77 13/58 25/44 25/56 6/37 15/22 15/38 8/31 17/26 17/42 8/33 10/19 10/21 1/12 11/13 11/31 9/29 25/41 25/59 9/43 23/39 23/53 7/37 31/43 31/81 19/69 45/71 45/109 19/83 33/59 33/73 7/47 29/41 29/75 17/63 39/61 39/95 17/73 27/49 27/59 5/37 29/37 29/79 21/71 55/89 55/131 21/97 47/81 47/107 13/73 49/67 49/129 31/111 75/119 75/181 31/137 57/101 57/127 13/83 41/59 41/105 23/87 51/79 51/125 23/97 33/61 33/71 5/43 27/35 27/73 19/65 49/79 49/117 19/87 41/71 41/93 11/63 39/53 39/103 25/89 61/97 61/147 25/111 47/83 47/105 11/69 31/45 31/79 17/65 37/57 37/91 17/71 23/43 23/49 3/29 19/23 19/53 15/49 41/67 41/97 15/71 37/63 37/85 11/59 47/65 47/123 29/105 69/109 69/167 29/127 51/91 51/113 11/73 43/61 43/111 25/93 57/89 57/139 25/107 39/71 39/85 7/53 37/47 37/101 27/91 71/115 71/169 27/125 61/105 61/139 17/95 65/89 65/171 41/147 99/157 99/239 41/181 75/133 75/167 17/109 55/79 55/141 31/117 69/107 69/169 31/131 45/83 45/97 7/59 33/43 33/89 23/79 59/95 59/141 23/105 49/85 49/111 13/75 45/61 45/119 29/103 71/113 71/171 29/129 55/97 55/123 13/81 35/51 35/89 19/73 41/63 41/101 19/79 25/47 25/53 3/31 17/21 17/47 13/43 35/57 35/83 13/61 31/53 31/71 9/49 37/51 37/97 23/83 55/87 55/133 23/101 41/73 41/91 9/59 33/47 33/85 19/71 43/67 43/105 19/81 29/53 29/63 5/39 23/29 23/63 17/57 45/73 45/107 17/79 39/67 39/89 11/61 43/59 43/113 27/97 65/103 65/157 27/119 49/87 49/109 11/71 37/53 37/95 21/79 47/73 47/115 21/89 31/57 31/67 5/41 19/25 19/51 13/45 33/53 33/79 13/59 27/47 27/61 7/41 23/31 23/61 15/53 37/59 37/89 15/67 29/51 29/65 7/43 17/25 17/43 9/35 19/29 19/47 9/37 11/21 11/23 1/13 7/8 7/20 6/19 17/28 17/40 6/29 16/27 16/37 5/26 23/32 23/60 14/51 33/52 33/80 14/61 24/43 24/53 5/34 22/31 22/57 13/48 30/47 30/73 13/56 21/38 21/46 4/29 25/32 25/68 18/61 47/76 47/112 18/83 40/69 40/91 11/62 41/56 41/108 26/93 63/100 63/152 26/115 48/85 48/107 11/70 34/49 34/87 19/72 42/65 42/103 19/80 27/50 27/58 4/35 24/31 24/65 17/58 44/71 44/105 17/78 37/64 37/84 10/57 36/49 36/95 23/82 56/89 56/135 23/102 43/76 43/96 10/63 29/42 29/74 16/61 35/54 35/86 16/67 22/41 22/47 3/28 23/28 23/64 18/59 49/80 49/116 18/85 44/75 44/101 13/70 55/76 55/144 34/123 81/128 81/196 34/149 60/107 60/133 13/86 50/71 50/129 29/108 66/103 66/161 29/124 45/82 45/98 8/61 41/52 41/112 30/101 79/128 79/188 30/139 68/117 68/155 19/106 73/100 73/192 46/165 111/176 111/268 46/203 84/149 84/187 19/122 62/89 62/159 35/132 78/121 78/191 35/148 51/94 51/110 8/67 36/47 36/97 25/86 64/103 64/153 25/114 53/92 53/120 14/81 48/65 48/127 31/110 76/121 76/183 31/138 59/104 59/132 14/87 37/54 37/94 20/77 43/66 43/106 20/83 26/49 26/55 3/32 22/27 22/61 17/56 46/75 46/109 17/80 41/70 41/94 12/65 50/69 50/131 31/112 74/117 74/179 31/136 55/98 55/122 12/79 45/64 45/116 26/97 59/92 59/144 26/111 40/73 40/87 7/54 34/43 34/93 25/84 66/107 66/157 25/116 57/98 57/130 16/89 62/85 62/163 39/140 94/149 94/227 39/172 71/126 71/158 16/103 53/76 53/136 30/113 67/104 67/164 30/127 44/81 44/95 7/58 29/38 29/78 20/69 51/82 51/122 20/91 42/73 42/95 11/64 37/50 37/98 24/85 59/94 59/142 24/107 46/81 46/103 11/68 28/41 28/71 15/58 32/49 32/79 15/62 19/36 19/40 2/23 17/20 17/48 14/45 39/64 39/92 14/67 36/61 36/83 11/58 49/68 49/128 30/109 71/112 71/172 30/131 52/93 52/115 11/74 46/65 46/119 27/100 62/97 62/151 27/116 43/78 43/94 8/59 47/60 47/128 ...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$
$\endgroup$
