9
$\begingroup$

This question already has an answer here:

Can any one tell me how to prove that the set of rational numbers are countable? Prove give me a prove?

Thanks.

$\endgroup$

marked as duplicate by Shaun, PhoemueX, Did, Jeel Shah, Mark Fantini Jan 18 '15 at 0:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ The standard argument is the visual argument found here: aminsaied.wordpress.com/2012/05/21/diagonal-arguments $\endgroup$ – Lepidopterist Mar 17 '13 at 22:41
  • 1
    $\begingroup$ @BrianSilva: They are countable $\endgroup$ – MITjanitor Mar 17 '13 at 22:43
  • 1
    $\begingroup$ @BrianSilva: So what? "Countable" means "has the same cardinality as the natural numbers", which is infinite too. (Or sometimes "has the same cardinality as the natural numbers, or less than that", but that's not relevant here). $\endgroup$ – Henning Makholm Mar 17 '13 at 22:43
  • 1
    $\begingroup$ @BrianSilva You're confused about the definition of countable. Countable means finite or equinumerous to $\Bbb N$ $\endgroup$ – Git Gud Mar 17 '13 at 22:44
  • 7
    $\begingroup$ I can't make head or tails of the sentence "Prove give me a prove?" $\endgroup$ – Pedro Tamaroff Mar 17 '13 at 22:45
11
$\begingroup$

Map each rational $\frac{a}{b}$ into the integer $2^a 3^b$. This shows that the number of rationals is at most the number of integers.

If you want to handle the negative rationals, map the sign ($-1$, $0$, or $+1$) to $5^{\mathrm{sign}+1}$ and stick it on the end, so the mapping is $\mathrm{sign} \times \frac{a}{b} \to 2^a \, 3^b \,5^{\mathrm{sign}+1}$.

If you find this troubling, that's OK. You are not the only one.

$\endgroup$
  • $\begingroup$ How would you go about proving that $\mathbb{N}\leftrightarrow\{\text{integers in the form }2^a3^b5^{\text{sign} + 1}\}$. Proving this is not trivial (at least for me.) $\endgroup$ – Nairit Sarkar Jul 2 '17 at 4:08
9
$\begingroup$

Here is another argument:

Consider the map $\varphi:\mathbb{Q}\rightarrow \mathbb{Z}\times\mathbb{N}$ which sends the rational number $\frac{a}{b}$ in lowest terms to the ordered pair $(a,b)$ where we take negative signs to always be in the numerator of the fraction. This map is an injection into a countably infinite set (the cartesian product of countable sets is countable), so therefore $\mathbb{Q}$ is at most countable. Since $\mathbb{Q}$ is not finite, it must be countably infinite.

$\endgroup$
  • $\begingroup$ Well, I became confused. So what does mean "has the same cardinality as the natural numbers"? Does countable mean that we count them or mean anything else? $\endgroup$ – LoveMath Mar 17 '13 at 23:01
  • $\begingroup$ Two sets have the same cardinality if we can exhibit a bijection between them, i.e., a map that is one-to-one on the elements. Any set that can be put in one-to-one correspondence in this way with the natural numbers is called countable. In some sense, this means there is a way to label each element of the set with a distinct natural number, and all natural numbers label some element of the set. $\endgroup$ – Jared Mar 18 '13 at 0:33
1
$\begingroup$

For an explicit enumeration of positive rationals, you can use the Calkin-Wilf sequence: $$q_{i+1}= \frac{1}{ \lfloor q_i \rfloor +1 - \{q_i\} }, \ q_0=1.$$

More details can be found in Proofs from THE BOOK.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.