Enumerating the Rational Numbers

One of my tutoring students is taking an Introduction to Mathematical Proof course. During one of our recent sessions, he had a problem that challenged him to come up with a way of enumerating the rational numbers, thus showing that they can be mapped to the natural numbers, and thus are a countably infinite set. I saw the proof that the rational numbers are countable way back in undergrad, but I couldn’t remember the process. So, I tried to come up with a means of counting the rational numbers. The enumeration I came up with is solid, I’m pretty sure, and I can’t seem to find it replicated elsewhere on the web.

So, I’m putting it here for others to comment on and to see if anyone can point me to where this method may have been used before. Here is my method for enumerating the rational numbers.

Let m, n \in \mathbb{Z} and m \ge 0, n > 0 such that \frac{m}{n} \in \mathbb{Q} and is irreducible.

Now let p_n refer to the nth prime number.

The number (p_n)^m \in \mathbb{N}. This value is unique in the natural numbers.

Thus, each positive rational number–and zero–maps onto a unique natural number. This same process can be duplicated for the negative rational numbers. Since both the positive and negative rational numbers can be shown to be countable in this way, the union of the two sets is also countable.

Continue reading

Advertisements