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$