Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

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: A \to B\) and \(g: B \to C\) be two functions. The composition of \(f\) and \(g\) is denoted \(g \circ f\) which we read “\(g\) of \(f\)”. It defines a new function
\begin{align*} g\circ f: A \to C && \left(g\circ f\right)(a) = g\left(f(a)\right) \qquad\forall a \in A \end{align*}
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.
\begin{gather*} (h \circ g \circ f)(x) = h \left( g\left (f (x) \right) \right) \end{gather*}
We start with \(x\text{,}\) apply \(f\text{,}\) 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:
\begin{gather*} g \circ f \neq f \circ g. \end{gather*}
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 \(a_1 \neq a_2 \in A\) then \(f(a_1) \neq f(a_2)\text{.}\) Similarly if \(b_1 \neq b_2\) then \(g(b_1) \neq g(b_2)\text{.}\) We can just put these together. If \(a_1 \neq a_2\) then \(f(a_1) \neq f(a_2)\) and so \(g(f(a_1)) \neq g(f(a_2))\text{.}\) Thus \((g \circ f)(a_1) \neq (g\circ f)(a_2)\text{.}\) The diagram below should help.
  • Surjective: Assume both \(f\) and \(g\) are surjective. Then for each \(c \in C\) there is some \(b \in B\) such that \(g(b) = c\text{.}\) Similarly for each \(b \in B\) there is some \(a \in A\) such that \(f(a) = b\text{.}\) Thus \(g(f(a)) = c\text{.}\) 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 \(g \circ f\) 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 \(a_1, a_2 \in A\) such that \(a_1 \neq a_2\text{.}\) Since \(f\) is injective, it follows that \(f(a_1) \neq f(a_2)\text{.}\) And since \(g\) is injective it followst that \(g(f(a_1)) \neq g(f(a_2))\text{.}\) Thus \((g\circ f)(a_1) \neq (g\circ f)(a_2)\text{.}\) Thus \(g\circ f\) is injective.
  • Let \(f,g\) be surjective functions and let \(c \in C\text{.}\) Since \(g\) is surjective, \(g(b) = c\) for some \(b \in B\text{.}\) Since \(f\) is surjective, there is some \(a \in A\) such that \(f(a) = b\text{.}\) It follows that \(g(f(a)) = c\) and so \(g\circ f\) is surjective.
Here is another nice result about compositions, injections and surjections. In particular, if we know the composition \(g \circ f\) is injective, then what can we say about \(f,g\text{.}\) Similarly, if \(g \circ f\) is surjective, then what can we say about \(f,g\text{.}\) Similarly
We prove each in turn.
  • Assume that \(g\circ f\) is injective, and let \(a_1,a_2 \in A\) so that \(f(a_1)=f(a_2)\text{.}\) To show that \(f\) is injective it suffices to show that \(a_1=a_2\text{.}\) Since \(f(a_1)=f(a_2)\text{,}\) we know that \(g(f(a_1))=g(f(a_2))\text{,}\) and since \(g\circ f\) is injective we have that \(a_1=a_2\text{.}\)
  • Now assume that \(g\circ f\) is surjective and let \(c \in C\text{.}\) To prove that \(g\) is surjective it suffices to find \(b \in B\) so that \(g(b)=c\text{.}\) Since \(g\circ f\) is surjective, we know that there is \(a \in A\) so that \(g(f(a))=c\text{.}\) Now set \(b = f(a)\text{.}\) Then \(g(b) = g(f(a))=c\) as required.

Example 10.5.5.

The above theorem proves that when \(g\circ f\) 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 \(g\circ f\) and \(g\) are surjective, we need not have that \(f\) is surjective.
Let \(A = \set{1,2}, B=\set{3,4,5}, C=\set{6,7}\) and consider the following functions
\begin{align*} \amp f: A \to B \amp\amp f(1)=3,\quad f(2)=4\\ \amp g: B \to C \amp\amp g(3)=6,\quad g(4)=7, \quad g(5)=7\\ \amp g\circ f: A \to C \amp\amp g(f(1))=6, \quad g(f(2))=7 \end{align*}
Notice that \(f\) and \(g\circ f\) are injective, but \(g\) is not injective since \(g(4)=g(5)\text{.}\) Additionally, \(g\) and \(g\circ f\) are surjective, but \(f\) is not surjective.
<Prev^TopNext>