Discrete Mathematics for Computer Science

Operations on Functions 247

The inverse of a function F is not always a function or a partial function. If, however,

F is 1-1 or a 1-1 correspondence, then we have Theorem 3.

Theorem 3. Let F : X -- Y be a function.

(a) F-1 is a function from Y to X if and only if F is a 1-1 correspondence.

(b) F-^1 is a partial function from Y to X if and only if F is 1-1.

(c) If F is a 1-1 correspondence, then F-1 : Y -- X is a 1-1 correspondence.

Proof.

(a) This proof is left as an exercise for the reader.

(b) F- is a partial function

.• for each y c Y, there is at most one x E X with (y, x) E F-^1

.:• for each y E Y there is at most one x E X with (x, y) E F

4•. F is 1-1.

(c) This proof is left as an exercise for the reader. 0

A function whose inverse is a function is also referred to as being invertible.

Theorem 4. Let X be a set, and let F : X -+ Y be a 1-1 and onto function.

(a) F-^1 oF=Idx

(b) F o F-^1 = Idy

Proof.

(a) First, observe that F-^1 o F is a 1-1 correspondence. This follows from three facts:

(i) F is given as a 1-1 correspondence; (ii) by Theorem 3(c) we have F-1 is a 1-1 corre-

spondence; and (iii) by Theorem 2(c) F-^1 o F is a 1-1 correspondence.

Now, let x E X. Since F is a total function, there is a y E Y such that (x, y) E F. By

the definition of an inverse, we have (y, x) E F-^1 .By the definition of composition of

functions (see Section 4.3.1), it follows that (x, x) E F-^1 o F. That is, Idx g F-1 o F.

To show that F-^1 o F C Idx, let (x, x') E F-^1 o F. Since we have just seen that

(x, x) E F-1 o F and we observed that F-1 o F is 1-1, we must have x' = x; that is,

(x, x') E Idx. Therefore, F-^1 o F C Idx.

(b) By Theorem 3, F-1 is 1-1 and onto. It follows from part (a) that (F-l)-1 o (F-1) -

Idy. By Theorem 2 in Section 3.2.1 it follows that F o F-^1 = (F-l)-1 o F. Now, by part

(a), (F-l)-1 o F = Idy. M

Very infonnally, Theorem 4 can be summarized as saying that if F-1 is a function at

all, then F-1 "undoes" what F "does."

Example 5. The function exp(x) = ex where e, the real number 2.718281828459 ....
is called the exponential function base e, which is also called exp. The function exp :
IR -+ (0, oo) is strictly increasing, 1-1, and onto. Its inverse is called the natural logarithm
function, designated In. Hence, y = In(x) is true if and only if x = exp(y) is true. It is also
easy to show that In is strictly increasing.