Discrete Mathematics for Computer Science

Countable and Uncountable Sets 269

positive integer. For I p I + q = 1 and 2, we have

0

Ip p +q=l

-1 1

Then, for I p + q = 3, we have

-2 -1 1 2

For I p I + q = 4, skipping -2/2 and 2/2 (since they are not in lowest terms), we have

-3 3

1'1

and so forth.

The order in which the distinct rationals are listed is shown in Figure 4.26, where the

rationals p/q are represented as points on the plane with x coordinate p and y coordinate

q. As the indicated path is followed, just rationals not already occurring on the list are

added to the list.

y

(-6,6) (-5,6) (-4,6) (-3,6) ( (-1,6) (0,6) 6 (2,6) (3,6) (4,6) (5,6) (6,6)

(-6,5) (-5,5) (-4,5) ( (^7) (-1,5) (0,) 5) (3,5) (4,5) (,5) (6,5)
(-6,4) (-5,4) 7 7 (-24 (-1,4) (0,4) 4) (4,4) (5,4) (6,4)
(-6,3) (-5,3 (-4,3 (-33 3 (-13) (0,) 3) 3) 3) (5,3) (6,3)
(-1,2•) ••^62
(-,2 (-,2 (-,2(-3,2
(-2,2 g(0 (2
)2) 2) 2)
2) (6,2)
.) ) 1) (-2•1• 1) 0 O 1, (,1 (3,1) (4,1 (5,1) (6,1)•
(-6,0N) (-5,0) .0 - (-2,0) (-(,0) (0,0) (2,0) '(3,0) ,( ,( (6,0)
Figure 4.26 Order for listing elements of Q.
For any positive integer n, there are only finitely many different rational numbers p/q
with I p I + q = n. In fact, since q must be greater than zero, q must be one of 1, 2, 3 ... , n
for a total of n choices. There are two choices for p, n - q and -(n - q), giving a total

of 2n choices for p/q. Among these 2n choices, some, such as 0/2 and 2/2, will not be in

lowest terms and so will be ignored.

Let p/q be a rational number such that I p I + q = n. Then, there are fewer than

2.l+2.2+2.3+...+2.n =n.(n+ 1)

rationals that could be listed in front of p/q. Hence, every rational number ultimately

appears on the list. Furthermore, since each rational number is listed only in lowest terms,
each rational number is listed only once.