Skip to main content

PLP: An introduction to mathematical proof

Section 10.5 Composition of functions

Our last step before defining inverse functions is to explain a generic way of combining functions. Now since we are dealing with general sets and not just sets of numbers, we can’t add or subtract or divide or differentiate or any of the things we usually do with functions in calculus courses. Really the only thing we can with our abstract functions defined on abstract sets is composition — that is, take an element, apply the first function and then apply the second function.

Definition 10.5.1.

Let f:AB and g:BC be two functions. The composition of f and g is denoted gf which we read “g of f”. It defines a new function
gf:AC(gf)(a)=g(f(a))aA
This standard notation for compositions looks a bit backwards — we read things from left to right, but when we actually evaluate the composition we do the rightmost function first.
(hgf)(x)=h(g(f(x)))
We start with x, apply f, then apply g to the result, and finally apply h to the result of that.
It is important to note that composition is not, in general, commutative:
gffg.
But it is associative
The proof of associativity is not difficult but is quite long; we leave it to the interested reader to work through it. Instead we’ll look at the following useful (and nice) theorem. This tells us that composition of functions interacts nicely with injections, surjections and bijections.
Scratch work:
  • Injective: Assume both f and g are injective. So if a1a2A then f(a1)f(a2). Similarly if b1b2 then g(b1)g(b2). We can just put these together. If a1a2 then f(a1)f(a2) and so g(f(a1))g(f(a2)). Thus (gf)(a1)(gf)(a2). The diagram below should help.
  • Surjective: Assume both f and g are surjective. Then for each cC there is some bB such that g(b)=c. Similarly for each bB there is some aA such that f(a)=b. Thus g(f(a))=c. Again, we refer the reader to the diagram below.
  • Bijectiveness follows from surjectiveness and injectiveness. That is, if f,g are both bijective, then they are both injective and surjective. Hence their composition gf is injective and surjective, and so bijective.
We are ready to write things up nicely for the reader.
It suffices to prove the first two points, since the final point follows immediately from them.
  • Let f,g be injective functions. And let a1,a2A such that a1a2. Since f is injective, it follows that f(a1)f(a2). And since g is injective it followst that g(f(a1))g(f(a2)). Thus (gf)(a1)(gf)(a2). Thus gf is injective.
  • Let f,g be surjective functions and let cC. Since g is surjective, g(b)=c for some bB. Since f is surjective, there is some aA such that f(a)=b. It follows that g(f(a))=c and so gf is surjective.
Here is another nice result about compositions, injections and surjections. In particular, if we know the composition gf is injective, then what can we say about f,g. Similarly, if gf is surjective, then what can we say about f,g. Similarly
We prove each in turn.
  • Assume that gf is injective, and let a1,a2A so that f(a1)=f(a2). To show that f is injective it suffices to show that a1=a2. Since f(a1)=f(a2), we know that g(f(a1))=g(f(a2)), and since gf is injective we have that a1=a2.
  • Now assume that gf is surjective and let cC. To prove that g is surjective it suffices to find bB so that g(b)=c. Since gf is surjective, we know that there is aA so that g(f(a))=c. Now set b=f(a). Then g(b)=g(f(a))=c as required.

Example 10.5.5.

The above theorem proves that when gf is injective, we know that f is injective, the following example show that g need not be injective. Further, it also shows that just because gf and g are surjective, we need not have that f is surjective.
Let A={1,2},B={3,4,5},C={6,7} and consider the following functions
f:ABf(1)=3,f(2)=4g:BCg(3)=6,g(4)=7,g(5)=7gf:ACg(f(1))=6,g(f(2))=7
Notice that f and gf are injective, but g is not injective since g(4)=g(5). Additionally, g and gf are surjective, but f is not surjective.