# Rational Numbers are Countably Infinite

## Theorem

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

## Intuitive Proof

We arrange the rationals thus:

$\displaystyle \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, \frac {-1} 3, \frac {-2} 3, \frac 3 1, \frac 3 2, \frac {-3} 1, \frac {-3} 2, \frac 1 4, \frac 3 4, \frac {-1} 4, \frac {-3} 4, \frac 4 1, \frac 4 3, \frac {-4} 1, \frac {-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$

## Formal Proof

Let us define the mapping $\phi: \Q \to \Z \times \N$ as follows:

$\forall \dfrac p q \in \Q: \phi \left({\dfrac p q}\right) = \left({p, q}\right)$

where $\dfrac p q$ is in canonical form.

Then $\phi$ is clearly injective.

From Cartesian Product of Countable Sets is Countable‎, we have that $\Z \times \N$ is countably infinite.

The result follows directly from Domain of Injection to Countable Set is Countable‎.

$\blacksquare$