Proposition: Rationals are Countable

The set of all rational numbers is countable.

Proof:

Every rational number has the form p / q, and we may assume that q is always positive. Define the height of a rational number p / q as |p| + q. Then we can list all rational numbers as follows: 
   Height 1:    0/1

   Height 2:   -1/1,   1/1

   Height 3:   -2/1,  -1/2,   1/2,  2/1

   Height 4:   -3/1,  -2/2,  -1/3,  1/3,  2/2,  3/1

   Height 5:   ...

   ......
But then each row is countable (in fact, finite), and there are countably many rows. Hence, we have written the rationals as a countable union of countable sets, so that the rationals are indeed countable. As a matter of fact, the above list contains many rational numbers more than once. But if that set is countable, then the subset of rational numbers of that set must also be countable, because it is certainly not finite.

To Theory | Glossary | Map
(bgw)