(by Polymath) This page is part of the Advanced High School Math Project.

This result is well-known: the set of rational numbers and the set of natural (counting) numbers have the same cardinality (that is, they are the same size). This is normally shown with Cantor's diagonalization proof. This proof (and other proofs involving the sizes of infinite sets) rests on Cantor's insight that comparing the size of sets ought to be done by trying to find a one-to-one correspondence between them. If you can find such a one-to-one correspondence that matches every element of set X to an element of set Y, then set Y is at least as big as set X. The beauty of that method is that it works for both finite and infinite sets.

The fact that the rationals and naturals are the same size is usually considered counter-intuitive (to non-mathematicians) because there are infinitely many rational numbers just between 0 and 1 alone. But nevertheless, the set of rationals is indeed the same size as the set of naturals. This page demonstrates my favorite proof of this. I learned it from a professor in college. (Note that I will use only the positive rationals in this proof, but adding the negative rationals doesn't change the size of the set)

I find (and others have found) the proof instructive because it really shows how the infinity of rationals can be scattered among the naturals much like the naturals are scattered among the rationalsâ€”the natural numbers being, after all, a subset of the rationals. It is obvious, then that the rationals are at least as big as the naturals.

I will therefore go on to prove that the set of rational numbers can be associated one-to-one with a subset of the natural numbers. This will mean that the naturals are at least as big as the rationals, and combined with the previous paragraph, that proves they have to be the same size.

So, here goes: By definition, each positive rational number can be expressed in a unique manner as p/q, where p and q are natural numbers with no common factors. Consider the string of symbols composed of (digits of p)/(digits of q), with a slash between the strings of digits. Now read that string (which is unique for every rational) as an integer in base 11, with the slash being the symbol for 10. Since each of the strings of symbols is unique, that makes a unique natural number associated with that rational number. The rational number 1/7, for example, is associated with the number that has a decimal representation of 238: 1 times 121, plus 10 (the slash) times 11, plus 7. Since each natural number that gets landed on in this process is unique, the association is one-to-one, as required, which completes the proof.