28
$\begingroup$

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$
8
  • $\begingroup$ 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$. $\endgroup$
    – bof
    Feb 1, 2014 at 8:25
  • $\begingroup$ is just an injection sufficient to prove countability, though? $\endgroup$
    – furashu
    Feb 1, 2014 at 8:33
  • $\begingroup$ 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. $\endgroup$
    – bof
    Feb 1, 2014 at 8:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – furashu
    Feb 1, 2014 at 8:40
  • $\begingroup$ 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. $\endgroup$
    – bof
    Feb 1, 2014 at 8:46

7 Answers 7

Reset to default
33
$\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}$.

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
22
$\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
  • 2
    $\begingroup$ this is one of the most impressive and elegant answers i've seen on here, well done! $\endgroup$
    – furashu
    Feb 1, 2014 at 9:18
  • 6
    $\begingroup$ Instead of using prime factorizations, you could just map the reduced fraction $\frac mn$ to the integer $2^m(2n+1)$ $\endgroup$
    – bof
    Feb 1, 2014 at 9:23
  • 1
    $\begingroup$ @bof True. This would have saved me like ten minutes of typing. $\endgroup$
    – William
    Feb 1, 2014 at 9:27
  • 1
    $\begingroup$ @William can you explain what bof said? what's the significance of that integer? $\endgroup$
    – furashu
    Feb 1, 2014 at 9:39
  • $\begingroup$ @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. $\endgroup$
    – furashu
    Feb 1, 2014 at 9:46
6
$\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
  • 2
    $\begingroup$ Is mapping from Z x Z the same as mapping from Z, though? $\endgroup$
    – furashu
    Feb 1, 2014 at 8:44
  • 3
    $\begingroup$ Lemma : If $A$ is countable, then $A \times A$ is countable. $\endgroup$
    – Euler....IS_ALIVE
    Feb 1, 2014 at 8:53
  • 1
    $\begingroup$ @Euler....IS_ALIVE How does one prove that? $\endgroup$
    – jimjim
    Jan 19, 2017 at 12:23
  • $\begingroup$ How to show this is injective $\endgroup$
    – Ppp
    Jan 3, 2020 at 4:40
2
$\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
  • 1
    $\begingroup$ 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. $\endgroup$
    – HeWhoMustBeNamed
    Jan 12, 2019 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – P Vanchinathan
    Jan 13, 2019 at 2:08
1
$\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]. 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.

$\endgroup$
1
$\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 ...
$\endgroup$
0
$\begingroup$

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .