Discrete Mathematical Structures by Pearson

3-8 Discrete Mathematical Structures

THEOREM 3.1 Let f: A → B be one-one ONTO function, then f

-1

: B → A is also one-one ONTO

function.

Proof: Since the function f is one-one, there will exist unique elements x

1

, x

2

∈ A such that

y

1

= f (x

1

), y

2

= f (x

2

), y

1

, y

2

∈ B

Now, suppose f

-1

( y

1

) = x

1

and f ( y

2

) = x

2

, then f

-1

( y

1

) = f

-1

( y

2

) ⇒ x

1

= x

2

⇒ f (x

1

) = f (x

2

)

⇒ y

1

= y

2

which shows that the function f

-1

is one-one.

To prove that f

-1

is ONTO, let x be an arbitrary element in A, then for every x ∈ A, there exists

a unique element y ∈ B such that f (x) = y because f is one-one. Hence, for each x ∈ A, we have

y ∈ B such that x = f

-1

( y) which shows that f

-1

is ONTO.

3.5.5 Some Illustrative Examples

Example 1 Prove that the function f: Q