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 corollary 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 composition 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.
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 corollary 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 composition 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.