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

CHAP. 3] FUNCTIONS AND ALGORITHMS 65

Fig. 3-10

MISCELLANEOUS PROBLEMS

3.22. Find the domainDof each of the following real-valued functions of a real variable:

(a) f (x)=x^1 − 2 (c) f (x)=

√

25 −x^2

(b) f (x)=x^2 − 3 x− 4 (d) x^2 where 0≤x≤ 2

When a real-valued function of a real variable is given by a formulaf(x), then the domainDconsists of the largest

subset ofRfor whichf(x)has meaning and is real, unless otherwise specified.

(a) fis not defined forx− 2 =0, i.e., forx=2; henceD=R\{ 2 }.

(b) fis defined for every real number; henceD=R.

(c) fis not defined when 25−x^2 is negative; henceD=[− 5 , 5 ]={x|− 5 ≤x≤ 5 }.

(d) Here, the domain offis explicitly given asD={x| 0 ≤x≤ 2 }.

3.23. For anyn∈N, letDn=( 0 , 1 /n), the open interval from 0 to 1/n. Find:

(a) D 3 ∪D 4 ; (b) D 3 ∩D 20 ; (c) Ds∪Dt; (d) Ds∩Dt.

(a) Since( 0 , 1 / 3 )is a superset of( 0 , 1 / 7 ),D 3 ∪D 4 =D 3.

(b) Since( 0 , 1 / 20 )is a subset of( 0 , 1 / 3 ),D 3 ∩D 20 =D 20.

(c) Letm=min(s, t), that is, the smaller of the two numberssandt; thenDmis equal toDsorDtcontains the

other as a subset. HenceDs∩Dt=Dm.

(d) LetM=max(s, t), that is, the larger of the two numberssandt; thenDs∩Dt=Dm.

3.24. SupposeP (n)=a 0 +a 1 n+a 2 n^2 +···+amn^2 has degreem. ProveP (n)=O(nm).

Letb 0 =|a 0 |,b 1 =|a 1 |,..., bm=|am|.Then forn≥ 1 ,

p(n)≤b 0 +b 1 n+b 2 n^2 +···+bmnm=

(

b 0

nm+

b 1

nm−^1 +···+bm

)

nm

≤(b 0 +b 1 +···+bm)nm=Mnm

whereM=|a 0 |+|a 1 |+···+|am|. HenceP (n)=O(nm).

For example, 5x^3 + 3 x=O(x^3 )andx^5 − 4000000 x^2 =O(x^5 ).

3.25. Prove Theorem 3.4 (Cantor):|A|<|Power(A)|(where Power (A) is the power setof A).

The functiong:A→Power(A)defined byg(a)={a}is clearly one-to-one; hence|A|≤|Power(A)|.

If we show that|A|  =|Power(A)|, then the theorem will follow. Suppose the contrary, that is, suppose

|A|=|Power(A)|and thatf:A→Power(A)is a function which is both one-to-one and onto. Leta∈Abe called

a “bad” element ifa/∈f(a), and letBbe the set of bad elements. In other words,

B={x:x∈A, x /∈f(x)}

NowBis a subset ofA. Sincef:A→Power(A)is onto, there existsb∈Asuch thatf(b)=B.Isba “bad”

element or a “good” element? Ifb∈Bthen, by definition ofB,b/∈f(b)=B, which is impossible. Likewise, if

b/∈Bthenb∈f(b)=B, which is also impossible. Thus the original assumption that|A|=|Power(A)|has led to

a contradiction. Hence the assumption is false, and so the theorem is true.