In Example, we showed you how to match the natural numbers with the positive rational numb...

In Example, we showed you how to match the natural numbers with the positive rational numbers in a one-to-one correspondence. Use that matching to answer the following questions.

What rational number corresponds to the natural number 12?

The Set of Rational Numbers Is Countable

Show that the set of rational numbers is countable.

SOLUTION:

First consider the positive rational numbers as we list them in Figure. The first row of the arrangement has all positive rational numbers with denominator 1. The second row has all denominators 2, the third row has denominators of 3, and so on. We then trace through the arrangement following the red line in Figure, skipping over numbers that we have encountered earlier.

We will follow the path through the rational numbers in Figure and list those numbers in a straight line, matching them with the natural numbers as follows:

Notice that in our matching, we have skipped over rational numbers that we have encountered earlier, such as 2/2, 2/4, 3/3, and 4/2.

When we look at the positive rational numbers in this way, we see that there is a first number, then a second, then a third, and so on, and we are listing each number exactly once. Therefore, there is a one-to-one correspondence between N and the positive rational numbers.