Countable and Uncountable Sets
269
positive integer. For I p I + q = 1 and 2, we have
0
p
Ip +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.