Discrete Mathematics for Computer Science

268 CHAPTER 4 Functions

Now, show that the set of primes is countably infinite. List the primes in increasing

order:

2,3,5,7, 11, 13, 17,19,23,29,31,37,41,43,47,53,59,....

Then, define a function

P : N --+ {2, 3,5,7, 11, 13, 17, 19,23,29,31,37,41,43,47,53,59,....

by the rule that P(n) is the nth prime on the list for n = 0, 1, 2, 3 ..... We claim that P is

a 1-1 and onto function. Function P is 1-1, because it is strictly increasing. Function P is

also onto, because the nth prime is always larger than n, so if k is prime, then k = P(n)

for some n E {0, 1, 2 ..... k - 11. 0

The first somewhat surprising result that follows from Theorem 5 is that there are no

more integers than there are prime numbers, even though there certainly are gaps between

consecutive primes.

Theorem 6. Z is countably infinite.

Proof. This part depends on listing the integers in a special order-in order of their ab-

solute values. First, list the integer with absolute value 0:

0

Then, add to the list the integers with absolute value 1:

0, -1, 1

and so forth:

0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, ...., -n, n....

We must now formalize this idea of a function. For any n E N, define G(n) to be

the nth number on this list. It is apparent that every integer is listed exactly once on the

list. In fact, it is easy to see that G(0) = 0, and for n > 1, we have G(2n - 1) = -n and

G(2n) = n. It follows that the function G : N -÷7 Z is 1-1 and onto. U

4.8.2 Cantor's First Diagonal Argument

Cantor found two important proof techniques for showing that two sets had the same car-

dinality. The first of these arguments, called Cantor's first diagonal argument, is used in

proving that I Z I = I Q I.

Theorem 7. Q is countably infinite.

Proof. The proof depends on listing all the rational numbers in a special order. For each

rational number r, pick out its expression p/q in lowest terms where q > 0. Lowest terms

means p and q have no common divisor. For every rational number p/q written in lowest

terms, compute the number I p I + q. Since p and q are integers and q > 0, I p I + q is a