Are There More Positive Rational Numbers than Positive Integers?

I asked that near the end of my previous post; and the answer, counterintuitively, is that these two sets are also equally big. Remember that the standard definition we're working with is that two sets are equally big if there's a way of mapping each element of the first to precisely one element of the second. So here's the mapping, with the unbracketed item in each cell being a rational number (e.g., 2/3), and the bracketed item being the positive integer to which the mapping is being done. (To make it simple, I'll ignore the double counting that happens when some fractions equal some others that came before, for instance when we get to 2/2 and 3/3, which equal 1/1; to make it more precise, we can just skip over them.

1/1 [1]2/1 [2]3/1 [4]4/1 [7]5/1 [11]6/1 [16] ...
1/2 [3]2/2 [5]3/2 [8]4/2 [12]5/2 [17] ...
1/3 [6]2/3 [9]3/3 [13]4/3 [18] ...
1/4 [10]2/4 [14]3/4 [19] ...
1/5 [15]2/5 [20] ...
1/6 [21] ...

As you can see, if the rational numbers in the form p/q are organized in an infinite matrix, we can start counting by diagonals, and eventually get to any p/q you care to mention. So every positive rational number has precisely one positive integer to which it's mapped. And therefore the sets are equal in size.

If you want another mapping, try mapping any p/q (where p and q are relatively prime) to 2^p x 3^q; that maps the positive rationals to a subset of the positive integers. Of course, if you grasp why that works, you've probably learned the diagonals proof already.

Related Posts (on one page):

  1. Beyond Infinity:
  2. Are There More Positive Rational Numbers than Positive Integers?
  3. To Infinity, and Beyond: