The Set of Rational Numbers is Countably Infinite

The Set of Rational Numbers is Countably Infinite

On The Set of Integers is Countably Infinite page we proved that the set of integers $\mathbb{Z}$ is countably infinite. We will now show that the set of rational numbers $\mathbb{Q}$ is countably infinite.

Theorem 1: The set of rational numbers $\mathbb{Q}$ is countably infinite.
  • Proof: Observe that the set of rational numbers is defined by:
(1)
\begin{align} \quad \mathbb{Q} = \left \{ \frac{a}{b} : a, b \in \mathbb{Z}, \: b \neq 0 \right \} \end{align}
  • In fact, every rational number $r$ can be uniquely written in the form $r = \frac{p}{q}$ where $p, q \in \mathbb{Z}$, $q \neq 0$, and $p$ and $q$ are relatively prime, that is, the greatest common divisor of $p$ and $q$ is $1$. For each rational number $r \in \mathbb{Q}$ we define a function $f : \mathbb{Q} \to \mathbb{Z} \times \mathbb{Z}$ by:
(2)
\begin{align} \quad f(r) = (p, q) \end{align}
  • Then by the observation made above, $f$ is injective. Furthermore, since $\mathbb{Z}$ is countable we have that $\mathbb{Z} \times \mathbb{Z}$ is countable by the theorem presented on The Cartesian Product of Two Countable Sets is Countable page. Therefore $f(\mathbb{Q})$ is countably infinite and so there exists a bijection $g : f(\mathbb{Q}) \to \mathbb{N}$.
  • Note that the function $h : \mathbb{Q} \to f(\mathbb{Q})$ defined by $h(q) = f(q)$ is a bijection. Therefore the composition $g \circ h : \mathbb{Q} \to \mathbb{N}$ is a bijection. So $\mathbb{Q}$ is countably infinite. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License