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 , and , such that and is irreducible.
Now let refer to the th prime number.
The number . 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.
That’s it. That’s my enumeration. Just let the denominator denote a prime number and let the numerator become the exponent of that prime number. The result will have to be a natural number and no other fraction will lead to that same natural number since prime factorizations are unique.
Of course, there are natural numbers that don’t get mapped to. There are lots of them, in fact. Any natural number that is the composite of more than one prime number, in fact, will never be included in this scheme. If I wanted to sacrifice the simplicity of this method, I could just create an enumeration algorithm that would check for an unused natural number before finding the exponentiation of a prime number.
No implications of this method occur to me. I’m mostly just excited to have come up with a method that I’d never seen before. I don’t get an opportunity to do new work very often. Now, let’s pick this apart.