Discrete Mathematics for Computer Science

Countable and Uncountable Sets 267

JR to JR was given that is not onto, and an onto function from R to R was given that is not

1-1. We recommend the reader find a 1-1 function from N to N that is not onto and an

onto function from N to N that is not 1-1.

The next three results give proofs that some of the common sets we use are indeed

infinite.

Theorem 4. Evens = {n E N :n = 2k for some k e N} is countably infinite.

Proof. Let

F : N -+ Evens

be defined by F(n) = 2n. The graph of this function is shown in Figure 4.25.

1

1 2

2 3

3 4

4 5

5 6

67

8

9

10

11

12

Figure 4.25 Bijection F(n) = 2n maps N to Evens.

Show that F is both 1-1 and onto. First, show that F is 1-1. Suppose F(m) = F(n).

That is, suppose 2m = 2n. Dividing both sides by 2 gives m = n. So, F is 1-1. Now show

that F is onto. Suppose k is even, and show that k = F(n) for some n E N. Since k is even,
k = 2no for some no E N. Now, F(no) = 2no = k as required. 0

Theorem 5 tells us that there were infinitely many base cases in our proof of the Fun-
damental Theorem of Arithmetic.

Theorem 5. The set of prime positive integers is countably infinite.

Proof. First, show that the set of primes is not finite. Suppose it were, and let the set of

primes be

{p, pi P dn-1

The set is nonempty since 2 is a prime. Now, let k = Po" Pl ... •Pn-1 + 1. None of the

given primes divides k, because each divides k - 1. Thus, there must be some other prime
that divides k-perhaps even k itself. In any case, the existence of at least one more prime
contradicts our assumption that P0, P1. Pn-1 are the only primes. Therefore, there
must be infinitely many primes.