Discrete Mathematics for Computer Science

272 CHAPTER 4 Functions

Proof. It is enough to show that (0, 1) is uncountable, since clearly, 1 (0, 1) 1 < I R 1. (See

Exercise 7 in Section 4.9 for a function that is a bijection from (0, 1) to R.)

We assume that F is any 1-1 correspondence from N onto (0, 1). Let F(n) =

0. ft f2 f3 ... be a decimal representation of F(n). Construct a new decimal d =
   O.d 1 d 2 d 3 ... by putting d, = 4 if the f, is 5 and d, = 5 otherwise. Then, d differs from
   F(n) in the nth digit. Since no digit of d is 0 or 9, by Theorem 8(d), d is the only decimal
   expansion of the real number that it represents-call it D. So, if F(n) has two decimal
   representations, then D is certainly not equal to F(n), and otherwise, D 7 F(n) because

dn * fn. This contradicts our assumption that F is onto. Since there is no 1-1 correspon-

dence from N to IR, we conclude the reals are not countable. U

Corollary 1: Not every real number is rational.

Proof. Since Q C R, either Q = R or there is a real number r E JR - Q. Since Q is count-

able and JR is uncountable, Q 0 R. Therefore, there is a real number that is not rational.

0

Corollary 2: The set R - Q is uncountable.

Proof. This proof is left as an exercise for the reader. 0

Working with infinite cardinalities gives us the impression that uncountable sets are

much larger than countable sets. So Corollary 2 states that almost all real numbers are

irrational. But it does not demonstrate any particular number to be irrational! It has been

known since the days of Pythagoras, an early Greek mathematician, that /2 is irrational.

Perhaps more stunning is the next theorem.

Definition 4. A real number r is algebraic if there is a polynomial P (x) of the form

P(x) = a, -x+ +- a,-I " xn-1- "I -+a2 - • x^2 +- al .x + ao

where each ai is an integer and r is a root of the equation-that is,

P(r) =a, "r" +a,-, "r-I + -" +a2 .r2 +-al • r +ao = 0

For example, every rational number is algebraic: p/q where p and q are integers is a

root ofthe polynomial equation qx - p = 0. Also, '/2 and ý V9/§_ + 217 -(333/41)

are algebraic, as are almost all numbers humans normally write down.

Theorem 10. The set A of algebraic numbers is countably infinite. Furthermore, JR - A

is uncountable.

Proof This proof is left as an exercise for the reader. M

A number that is not algebraic is transcendental. Theorem 10 states that almost all

real numbers are transcendental, yet it is very difficult to show that any particular real

number is transcendental! The two standard examples are 7r and e. Proving that 7r is tran-

scendental is very complicated.

A more difficult question to answer is whether any X C R exists where I N I < I X I <

I R I. The conjecture that there is no such set X is called the continuum hypothesis. The

conjecture is a famous and much-studied question. Finally, work of the famous mathe-

maticians Kurt Godel (1906-1978, b. Austria-Hungary) and Paul Cohen (1934-, b. United