| | |
Proof:
The positive rationals can only have the same cardinality as the natural numbers if they can be put into a one-to-one correspondence with the natural numbers (i.e., if a bijection between the sets can be found). Putting the positive rationals into a one-to-one correspondence with the natural numbers is equivalent to "listing" all of the positive rationals with no duplications. In this way, 1 is paired with the first element of the list, 2 is paired with the second element of the list, 3 is paired with the third, and so on... If all of the rationals show up in the list, we are guaranteed the implied function is surjective (i.e., "onto"). If there are no duplicates in the list, we are guaranteed the implied function is injective.
Consider the following infinite table, which clearly contains all of the positive rationals (with some duplicates upon considering reducing things to lowest form). Suppose we list the positive rationals in the following way. Starting with the upper left corner, snake back and forth along the diagonals as shown below, writing down the fractions as they appear on this path, being careful to skip any (reducible) fractions that would have previously appeared in the list.
So we can see the first few elements of this list (and hence, the first few elements of the one-to-one correspondence with the natural numbers) would be...
$$\begin{array}{c|c}
\mathbb{N} & \mathbb{Q}^+\\\hline
1 & 1/1\\
2 & 1/2\\
3 & 2/1\\
4 & 1/3\\
5 & 3/1\\
6 & 1/4\\
7 & 2/3\\
8 & 3/2\\
9 & 4/1\\
10 & 1/5\\
11 & 5/1\\
\vdots & \vdots\\
\end{array}$$
Every positive rational number eventually shows up in the list on the right, and (by design) there are no duplicates.
Thus, there is a bijection between the positive rationals and the natural numbers. Consequently, these two sets to have the same cardinality.
QED.