Rational Numbers are Countably Infinite/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

The set $\Q$ of rational numbers is countably infinite.


Proof

The rational numbers are arranged thus:

$\dfrac 0 1, \dfrac 1 1, \dfrac {-1} 1, \dfrac 1 2, \dfrac {-1} 2, \dfrac 2 1, \dfrac {-2} 1, \dfrac 1 3, \dfrac 2 3, \dfrac {-1} 3, \dfrac {-2} 3, \dfrac 3 1, \dfrac 3 2, \dfrac {-3} 1, \dfrac {-3} 2, \dfrac 1 4, \dfrac 3 4, \dfrac {-1} 4, \dfrac {-3} 4, \dfrac 4 1, \dfrac 4 3, \dfrac {-4} 1, \dfrac {-4} 3 \ldots$

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 $\N$.

$\blacksquare$


Sources