Discrete Mathematics for Computer Science

Operations on Functions 245

Theorem 1. Let X, Y, and Z be sets. Let both F : X - Y and G : Y --- Z be partial

functions. Then, G o F is a partial function from X to Z. Moreover, for every x E X, the

following hold:

(a) If F(x) is undefined, then (G o F)(x) is undefined.

(b) If F(x) is defined but G(F(x)) is undefined, then (G o F)(x) is undefined.

(c) If F(x) and G(F(x)) are defined, then (G o F)(x) is also defined, and (G o F)(x) =

G(F(x)).

The proof of Theorem 1 is omitted, since it is just a formalization of the discussion in

the example above. One important corollary to Theorem 1 is used all the time. This corol-

lary says that the composition of functions is an associative operation, just like addition

and multiplication with real numbers as well as union and intersection of sets.

Corollary 1: Let F:X--> Y,G:Y-- Z, andH:Z--* W be functions. Then, Fo

(G o H) = (F o G) o H.

Corollary 4.1 follows from Theorem 3 by reducing both F o (G o H)(x) and (F o

G) o H(x) to F(G(H(x)).

For functions F and G, one often defines G o F(x) to be G(F(x)). Since we have

already defined the operation o on relations in Section 3.2.2, we only had to show that

(G o F)(x) is the same as G(F(x)).

Example 2 shows that the composition of functions is not a commutative operation.

Example 2. Let G : N -* N and H : N --* N be given by the rules G(n) = n^2 + I and

H(n) = 2n. Then, (H o G) : N -- N, and for all n E N, we have (H o G)(n) = 2n2+1. By

contrast, (G o H)(n) = 22n + 1.

Earlier, we studied 1-1 and onto functions. It is now natural to ask whether the com-

position of 1-1 functions is 1-1 or whether the composition of onto functions is onto. We

answer these questions in Theorem 2.

Theorem 2. Let F : X -- Y and G : Y -- Z be functions.

(a) If F and G are both 1-1, then G o F is 1-1.

(b) If F and G are both onto, then G o F is onto.

(c) If F and G are 1-1 correspondences, then G o F is a 1-1 correspondence.

(d) If G o F is 1-1, then F is 1-1.

(e) If G o F is onto, G is onto.

Proof. These proofs are left as exercises for the reader. 0

4.3.2 Inverses of Functions

Recall the definition of the inverse of a relation given in Section 3.2.1. For any relation R
defined on a set X,

R- = {(y, X) E X x X: (x, y) E R)

Since functions are relations, they also have inverses.