Is the set of rational numbers countable?

Steps to Solve

1. Understand Countability
   A set is countable if its elements can be listed in a sequence such that each element corresponds to a natural number. This means you can "count" them like 1, 2, 3, ...

2. Define Rational Numbers
   The rational numbers are all numbers that can be expressed as the fraction $\frac{p}{q}$, where $p$ is an integer and $q$ is a non-zero integer.

3. Show Rational Numbers are Countable
   To prove that the rational numbers are countable, we can arrange them systematically. We can list them in a two-dimensional array indexed by the integers, where the first index represents the numerator and the second index represents the denominator:

   • List all fractions: $\left(\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \ldots \right), \left(\frac{2}{1}, \frac{2}{2}, \frac{2}{3}, \ldots \right), \ldots$

4. Use Diagonal Argument
   We can then apply a diagonal argument to show that we can traverse this array in a way that guarantees every rational number will appear eventually.

5. Simplification of Fractions
   Note that many fractions will appear multiple times (like $\frac{2}{4} = \frac{1}{2}$). To count them once, we can only include each fraction in its simplest form, thus excluding the duplicates.

6. Conclusion
   Since we can create a systematic listing of the rational numbers that includes every rational number without missing any, we conclude that the set of rational numbers is countable.