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

62 FUNCTIONS AND ALGORITHMS [CHAP. 3

3.7. Consider functionsf:A→Bandg:B→C. Prove the following:

(a)Iffandgare one-to-one, then the composition functiong◦fis one-to-one.

(b)Iffandgare onto functions, theng◦fis an onto function.

(a) Suppose(g◦f )(x)=(g◦f )(y); theng(f (x))=g(f (y)). Hencef(x)=f(y)becausegis one-to-one. Further-

more,x=ysincefis one-to-one. Accordinglyg◦fis one-to-one.

(b) Letcbe any arbitrary element ofC. Sincegis onto, there exists ab∈Bsuch thatg(b)=c. Sincefis onto, there

exists ana∈Asuch thatf(a)=b. But then

(g◦f )(a)=g(f (a))=g(b)=c

Hence eachc∈Cis the image of some elementa∈A. Accordingly,g◦fis an onto function.

3.8. Letf:R→Rbe defined byf(x)= 2 x−3. Nowfis one-to-one and onto; hencefhas an inverse function

f−^1. Find a formula forf−^1.

Letybe the image ofxunder the functionf:

y=f(x)= 2 x− 3

Consequently,xwill be the image ofyunder the inverse functionf−^1. Solve forxin terms ofyin the above equation:

x=(y+ 3 )/ 2

Thenf−^1 (y)=(y+ 3 )/2. Replaceybyxto obtain

f−^1 (x)=

x+ 3

2

which is the formula forf−^1 using the usual independent variablex.

3.9. Prove the following generalization of DeMorgan’s law: For any class of sets{Ai}we have

(∪iAi)c=∩iAci

We have:

x∈(∪iAi)c iffx/∈∪iAi, iff∀i∈I,x∈Ai, iff∀i∈I,x∈Aci, iffx∈∩iAci

Therefore,(∪iAi)c=∩iAci. (Here we have used the logical notations iff for “if and only” if and∀for “for all.”)

CARDINALITY

3.10. Find the cardinal number of each set:

(a) A={a, b, c, ... ,y, z}, (c)C={ 10 , 20 , 30 , 40 ,...},

(b) B={x|x∈N,x^2 = 5 }, (d)D={ 6 , 7 , 8 , 9 ,...}.

(a) |A|=26 since there are 26 letters in the English alphabet.

(b) |B|=0 since there is no positive integer whose square is 5, that is,Bis empty.

(c) |Cא=| 0 becausef:N→C, defined byf (n)= (^10) n, is a one-to-one correspondence betweenNandC.
(d) |Dא=| 0 becauseg:N→D, defined byg(n)=n+5 is a one-to-one correspondence betweenNandD.
3.11. Show that the setZof integers has cardinalityא 0.
The following diagram shows a one-to-one correspondence betweenNandZ:
N= 12345678 ...
↓↓↓↓↓↓↓↓...
Z= 01 − 12 − 23 − 34 ...
That is, the following functionf:N→Zis one-to-one and onto:
f (n)=
{
n/2ifnis even
( 1 −n)/2ifnis oddn/^2
Accordingly,|Z|=|Nא=| 0.