Discrete Mathematics

----------------------------COMBINATORICS

267

I Proof I

We

must show that there is

no

bijection/:

N

~

R.

The proof is

by

contradiction. Assume for the

purpose

of

contradiction that such a bijection f exists. Let r be the real number with decimal expansion 0.

rO

rl

r2 r3

.... where

r.

is 5 + the

(i

+ 1 )-st decimal digit

off

(i), taken modulo 10.

For

all

i,f

(i)

::f:.

r,

since the

(i

+ I )-st digits

off

(i) and r disagree by 5 and

so

I

r-

f (i)

~

4 ·

IO

-

(i

•

1).

This implies that f is not swjective,

contradicting the assumption that

f is a bijection.

This is called a

"diagonalization argument", because

of

the construction based on diagonal