To show that
\(\Q\) is countable, we will use
Fact 13.1.2 and construct an infinite sequence which contains each element of
\(\Q\) exactly once. First, construct an infinite grid which contains
all positive rational numbers. By zig-zagging through the grid, we obtain an infinite sequence which contains each positive element of
\(\Q\) at least once, though there are duplicates because an element of
\(\Q\) can have many different representations as a fraction.
The path through the grid creates the following sequence of positive rational numbers. By crossing out duplicates, we obtain an infinite sequence which contains each positive rational number exactly once.
\begin{gather*}
1, \;\;\;
\frac{1}{2}, \;\;\;
2, \;\;\;
3, \;\;\;
\xcancel{1,} \;\;\;
\frac{1}{3}, \;\;\;
\frac{1}{4}, \;\;\;
\frac{2}{3}, \;\;\;
\frac{3}{2}, \;\;\;
4, \;\;\;
5,\\
\xcancel{2,} \;\;\;
\xcancel{1,} \;\;\;
\xcancel{\frac{1}{2},} \;\;\;
\frac{1}{5}, \;\;\;
\frac{1}{6}, \;\;\;
\frac{2}{5}, \;\;\;
\frac{3}{4}, \;\;\;
\frac{4}{3}, \;\;\;
\frac{5}{2}, \;\;\;
\dotsc
\end{gather*}
Finally, interleave the negative rational numbers into the above sequence, and insert \(0\) at the beginning.
\begin{gather*}
0, \;\;\;
1, \;\;\;
-1, \;\;\;
\frac{1}{2}, \;\;\;
-\frac{1}{2}, \;\;\;
2, \;\;\;
-2, \;\;\;
3, \;\;\;
-3, \;\;\;
\frac{1}{3}, \;\;\;
-\frac{1}{3}, \;\;\;\\
\frac{1}{4}, \;\;\;
-\frac{1}{4}, \;\;\;
\frac{2}{3}, \;\;\;
-\frac{2}{3}, \;\;\;
\frac{3}{2}, \;\;\;
-\frac{3}{2}, \;\;\;
4, \;\;\;
-4, \;\;\;
5, \;\;\;
-5, \;\;\;
\dotsc
\end{gather*}