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

CHAP. 3] FUNCTIONS AND ALGORITHMS 61

3.4. Letf:R→Randg:R→Rbe defined byf(x)= 2 x+1 andg(x)=x^2 −2. Find the formula for the

composition functiong◦f.

Computeg◦fas follows:(g◦f )(x)=g(f (x))=g( 2 x+ 1 )=( 2 x+ 1 )^2 − 2 = 4 x^2 + 4 x−1.

Observe that the same answer can be found by writing

y=f(x)= 2 x+1 and z=g(y)=y^2 − 2

and then eliminatingyfrom both equations:

z=y^2 − 2 =( 2 x+ 1 )^2 − 2 = 4 x^2 + 4 x− 1

ONE-TO-ONE, ONTO, AND INVERTIBLE FUNCTIONS

3.5. Let the functionsf:A→B,g:B→C,h:C→Dbe defined by Fig. 3-9. Determine if each function is:

(a) onto, (b) one-to-one, (c) invertible.

Fig. 3-9

(a) The functionf:A→Bis not onto since 3∈Bis not the image of any element inA.

The functiong:B→Cis not onto sincez∈Cis not the image of any element inB.

The functionh:C→Dis onto since each element inDis the image of some element ofC.

(b) The functionf:A→Bis not one-to-one sinceaandchave the same image 2.

The functiong:B→Cis one-to-one since 1, 2 and 3 have distinct images.

The functionh:C→Dis not one-to-one sincexandzhave the same image 4.

(c) No function is one-to-one and onto; hence no function is invertible.

3.6. Consider permutationsσ=

(

123456

364512

)

andτ=

(

123456

246531

)

inS 6.

Find: (a) compositionτ◦σ;(b)σ−^1.

(a) Note thatσsends 1 into 3 andτsends 3 into 6. So the compositionτ◦σsends 1 into 6. I.e.(τ◦σ)( 1 )=6. Moreover,

τ◦σsends 2 into 6 into 1 that is,(τ◦σ)( 2 )=1, Similarly,

(τ◦σ)( 3 )= 5 ,(τ◦σ)( 4 )= 3 ,(τ◦σ)= 2 ,(τ◦σ)( 6 )= 4

Thus

τ◦σ=

(

123456

615324

)

(b) Look for 1 in the second row ofσ. Noteσsends 5 into 1. Henceσ−^1 ( 1 )=5. Look for 2 in the second row ofσ.

Noteσsends 6 into 2. Henceσ−^1 ( 2 )=6. Similarly,σ−^1 ( 3 )=1,σ−^1 ( 4 )=3,σ−^1 ( 5 )=4,σ−^1 ( 6 )=2. Thus

σ−^1 =

(

123456

561342

)