[proofplan]
We decompose $\mathbb{Q}$ by denominators: for each $n \in \mathbb{N}$, the rationals with denominator $n$ form a set indexed by $\mathbb{Z}$. Each such denominator slice is countable because it is the image of a [countable set](/page/Countable-Set) under an injective parametrization. Since the slices are indexed by the [countable set](/page/Countable%20Set) $\mathbb{N}$, the [countable-union theorem](/theorems/755) implies that their union, which is all of $\mathbb{Q}$, is countable.
[/proofplan]
[step:Decompose $\mathbb{Q}$ into denominator slices]
For each $n \in \mathbb{N}$, define the denominator slice
\begin{align*}
A_n := \left\{\frac{m}{n} : m \in \mathbb{Z}\right\} \subset \mathbb{Q}.
\end{align*}
By the definition of rational number, every $q \in \mathbb{Q}$ has a representation $q = m/n$ with $m \in \mathbb{Z}$ and $n \in \mathbb{N}$. Hence $q \in A_n$ for some $n \in \mathbb{N}$, so $\mathbb{Q} \subset \bigcup_{n \in \mathbb{N}} A_n$. Conversely, each $A_n$ consists of rational numbers, so $\bigcup_{n \in \mathbb{N}} A_n \subset \mathbb{Q}$. Therefore
\begin{align*}
\mathbb{Q} = \bigcup_{n \in \mathbb{N}} A_n.
\end{align*}
[/step]
[step:Show each denominator slice is countable]
Fix $n \in \mathbb{N}$. Define the map
\begin{align*}
\varphi_n: \mathbb{Z} &\to A_n \\
m &\mapsto \frac{m}{n}.
\end{align*}
The map $\varphi_n$ is surjective by the definition of $A_n$. It is injective because if $m_1,m_2 \in \mathbb{Z}$ and $\varphi_n(m_1)=\varphi_n(m_2)$, then
\begin{align*}
\frac{m_1}{n} = \frac{m_2}{n},
\end{align*}
and multiplying both sides by the nonzero integer $n$ gives $m_1=m_2$. Thus $\varphi_n$ is a bijection from $\mathbb{Z}$ to $A_n$. Since $\mathbb{Z}$ is countable, $A_n$ is countable.
[guided]
Fix one denominator $n \in \mathbb{N}$. We want to prove that the set
\begin{align*}
A_n = \left\{\frac{m}{n} : m \in \mathbb{Z}\right\}
\end{align*}
is countable. The natural comparison set is $\mathbb{Z}$, because the only free parameter in $A_n$ is the numerator $m$.
Define the map
\begin{align*}
\varphi_n: \mathbb{Z} &\to A_n \\
m &\mapsto \frac{m}{n}.
\end{align*}
This map is surjective: if $a \in A_n$, then by definition of $A_n$ there exists $m \in \mathbb{Z}$ such that $a = m/n$, and hence $a = \varphi_n(m)$.
It is also injective. Suppose $m_1,m_2 \in \mathbb{Z}$ satisfy $\varphi_n(m_1)=\varphi_n(m_2)$. Then
\begin{align*}
\frac{m_1}{n} = \frac{m_2}{n}.
\end{align*}
Since $n \in \mathbb{N}$, we have $n \neq 0$, so multiplying both sides by $n$ is valid and gives $m_1=m_2$. Therefore $\varphi_n$ is injective.
Thus $\varphi_n$ is a bijection from $\mathbb{Z}$ to $A_n$. Since $\mathbb{Z}$ is countable, any set in bijection with $\mathbb{Z}$ is countable, so $A_n$ is countable.
[/guided]
[/step]
[step:Apply the countable union theorem to the denominator decomposition]
The family $(A_n)_{n \in \mathbb{N}}$ is indexed by $\mathbb{N}$, and $\mathbb{N}$ is countable. The previous step shows that every set $A_n$ in this family is countable. Therefore the hypotheses of the Countable Union of Countable Sets are satisfied. Applying that theorem gives that
\begin{align*}
\bigcup_{n \in \mathbb{N}} A_n
\end{align*}
is countable. Since the first step proved $\mathbb{Q} = \bigcup_{n \in \mathbb{N}} A_n$, it follows that $\mathbb{Q}$ is countable.
[guided]
We now verify the hypotheses needed to use the Countable Union of Countable Sets. The theorem applies to a family of countable sets indexed by a countable index set.
Here the index set is $\mathbb{N}$, which is countable. The indexed family is $(A_n)_{n \in \mathbb{N}}$, where
\begin{align*}
A_n = \left\{\frac{m}{n} : m \in \mathbb{Z}\right\}.
\end{align*}
For every fixed $n \in \mathbb{N}$, the previous step constructed a bijection $\varphi_n:\mathbb{Z} \to A_n$, so each $A_n$ is countable.
Thus all hypotheses of the countable-union theorem are met, and it gives that
\begin{align*}
\bigcup_{n \in \mathbb{N}} A_n
\end{align*}
is countable. The decomposition step already established that this union is exactly $\mathbb{Q}$:
\begin{align*}
\mathbb{Q} = \bigcup_{n \in \mathbb{N}} A_n.
\end{align*}
Therefore $\mathbb{Q}$ is countable.
[/guided]
[/step]
