Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 3] FUNCTIONS AND ALGORITHMS 63

3.12. LetA 1 ,A 2 ,...be a countable number of finite sets. Prove that the unionS=∪iAiis countable.

Essentially, we list the elements ofA 1 , then we list the elements ofA 2 which do not belong toA 1 , then we list

the elements ofA 3 which do not belong toA 1 orA 2 , i.e., which have not already been listed, and so on. Since theAi

are finite, we can always list the elements of each set. This process is done formally as follows.

First we define setsB 1 ,B 2 ,...whereBicontains the elements ofAiwhich do not belong to preceding sets, i.e.,

we define

B 1 =A 1 and Bk=Ak\(A 1 ∪A 2 ∪···∪Ak− 1 )

Then theBiare disjoint andS=∪iBi. Letbi 1 ,bi 2 ,...,bim, be the elements ofBi. ThenS={bij}. Letf:S→N

be defined as follows:

f(bij)=m 1 +m 2 +···+mi− 1 +j

IfSis finite, thenSis countable. IfSis infinite thenfis a one-to-one correspondence betweenSandN. ThusSis

countable.

3.13. Prove Theorem 3.2: A countable union of countable sets is countable.

SupposeA 1 ,A 2 ,A 3 ,...are a countable number of countable sets. In particular, supposeai 1 ,ai 2 ,ai 3 ,...are the

elements ofAi. Define setsB 2 ,B 3 ,B 4 ,...as follows:

Bk={aij|i+j=k}

For example,B 6 ={a 15 ,a 24 ,a 33 ,a 12 ,a 51 }. Observe that eachBkis finite and

S=∪iAi=∪kBk

By the preceding problem∪kBkis countable. HenceS=∪iAiis countable and the theorem is proved.

3.14. Prove Theorem 3.3: The setIof all real numbers between 0 and 1 inclusive is uncountable.

The setIis clearly infinite, since it contains 1,^12 ,^13 ,.... SupposeIis denumerable. Then there exists a one-to-

one correspondencef:N→I. Letf( 1 )=a 1 ,f( 2 )=a 2 ,...; that is,I={a 1 ,a 2 ,a 3 ,...}. We list the elements

a 1 ,a 2 ,.... in a column and express each in its decimal expansion:

a 1 = 0 .x 11 x 12 x 13 x 14 ...

a 2 = 0 .x 21 x 22 x 23 x 24 ...

a 3 = 0 .x 31 x 32 x 33 x 34 ...

a 4 = 0 .x 41 x 42 x 43 x 44 ...

.................................

wherexij∈{ 0 , 1 , 2 , ..., 9 }. (For those numbers which can be expressed in two different decimal expansions, e.g.,

0. 2000000 ...= 0. 1999999 ..., we choose the expansion which ends with nines.)

Letb= 0 .y 1 y 2 y 3 y 4 ...be the real number obtained as follows:

yi=

{

1ifxii= 1

2ifxii= 1

Nowb∈I. But

b=a 1 becausey 1 =x 11

b=a 2 becausey 2 =x 22

b=a 3 becausey 3 =x 33

....................................

Thereforebdoes not belong toI={a 1 ,a 2 ,...}. This contradicts the fact thatb∈I. Hence the assumption thatIis

denumerable must be false, soIis uncountable.

SPECIAL MATHEMATICAL FUNCTIONS

3.15. Find: (a) 7. 5 ,− 7. 5 ,− 18 ;(b) 7. 5 ,− 7. 5 ,− 18 .

(a) By definition,xdenotes the greatest integer that does not exceedx, hence 7. 5 =7,− 7. 5 =−8,

− 18 =−18.

(b) By definition,xdenotes the least integer that is not less thanx, hence 7. 5 =8,− 7. 5 =−7,− 18 =−18.