# How is the set of rational numbers countably infinite? [duplicate]

How is $\mathbb{Q}$ countably infinite?

The definition says all elements of the set must have a one-to-one relation to the natural numbers. I do not understand this.

How do the elements in $\mathbb{Q}$ have a one-to-one relation with natural numbers?

## marked as duplicate by Elliot G, msm, Rohan, Moishe Kohan, MasacrosoJan 6 '17 at 7:25

• Do you see that $\mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Z}^2$ all have the same cardinality? – copper.hat Jan 6 '17 at 7:10
• you've already asked this question and I've posted a solution. Also I'm sure that if you googled "rational numbers countable proof" it would be the first link to appear. – Daniel Xiang Jan 6 '17 at 7:10
• Just for the record see that. – Masacroso Jan 6 '17 at 7:26

Because you can construct a mapping of the rationals into the integers.

One easy way is to map the positive rational $\dfrac{a}{b}$ to the integer $2^a 3^b$.

This shows that there are at least as many integers as there are positive rationals.

There are many proofs here.

For the sake of completeness I will write one down here.

The rational numbers are arranged thus $$\frac {0}{1}, \frac {1}{1}, \frac {-1}{1},\frac {1}{2},\frac {-1}{2},\frac {2}{1 },\frac {-2}{1},\frac {1}{3},\frac {2}{3},\cdots$$

It is clear that every rational number will appear somewhere in this list. Thus it is possible to set up a bijection between each rational number and its position in the list, which is an element of $\mathbb N$.

Also see here. Hope it helps.

A roundabout way of showing this is to express the elements of $\mathbb{Q} - \{0\}$ as products of prime numbers. Labeling the prime numbers as $p_1, p_2, ...$ every nonzero rational number can be uniquely expressed as a product

$$p_1^{n_1} p_2^{n_2} \cdots$$

where $n_i$ are integers and for all but finitely many $i$, $n_i = 0$.

Your question becomes equivalent to asking why the set $A$ of sequences of integers $(n_1,n_2, ...)$ such that $n_i = 0$ for all but finitely many $i$, is countable.

To show this, let $A_j$ be the set of integer sequences $(n_1, ... , n_j, 0, 0, ...)$. Then $A_j$ is clearly in bijection with $\prod\limits_{i=1}^j \mathbb{Z}$, which is countable, and $A$ is equal to the union of the $A_j$. Now, you just have to show that a countable union of countable sets is countable.