a function \(A \to C\) created from given functions \(\funcdef{f}{A}{B}\) and \(\funcdef{g}{B}{C}\) by \(a \mapsto g\bbrac{f(a)}\)
\(g \funccomp f\)
the composition of functions \(\funcdef{f}{A}{B}\) and \(\funcdef{g}{B}{C}\text{,}\) so that \(\funcdef{g \funccomp f}{A}{C}\) by \((g \funccomp f)(a) = g\bbrac{f(a)}\)
Figure10.4.1.A Venn diagram of a function composition.
Example10.4.2.A composition of two functions.
Consider the functions
\begin{align*}
f \colon \R \amp \to \nnegset{\R},
\amp g \colon \nnegset{\R} \amp \to \nnegset{\R},\\
x \amp \mapsto x^2,
\amp x \amp \mapsto \sqrt{x},
\end{align*}
Then we have
\begin{align*}
g \funccomp f \colon \R \amp \to \nnegset{\R}, \\
x \amp \mapsto \sqrt{x^2} = \abs{x}.
\end{align*}
Warning10.4.3.Composition order matters.
The notation for the composition of functions \(f\) and \(g\) involves a reversal of order, so that we write \(g \funccomp f\text{.}\) This is so that when we use this notation with input-output notation \((g \funccomp f)(a)\text{,}\) the notation reminds us that \(f\) must first be applied to the input \(a\text{,}\) and then \(g\) is applied to the result \(f(a)\text{.}\)
In general, \(f \funccomp g \ne g \funccomp f\text{.}\) Usually, one of the two is not even defined, because domains and codomains of \(f\) and \(g\) will not necessarily match up in both orders. And when both are defined, the two different orders of composition usually have different domains and codomains.
Example10.4.4.Comparing composition order.
Consider functions
\begin{align*}
f \colon \N \amp \to \N, \amp g \colon \N \amp \to \N, \\
n \amp \mapsto n^2, \amp n \amp \mapsto n + 1.
\end{align*}
Then, both \(\funcdef{f \funccomp g}{\N}{\N}\) and \(\funcdef{g \funccomp f}{\N}{\N}\) are defined. But they are not equal, as
But \(\sqrtop \funccomp \flr\) is not defined, as the codomain of \(\flr\) does not match the domain of \(\sqrtop\text{.}\) In particular, \(\flr\) will sometimes return a negative output, and we cannot use such an output as an input in \(\sqrtop\text{.}\)
Checkpoint10.4.6.Properties of compositions.
Consider functions \(\funcdef{f}{A}{B}\) and \(\funcdef{g}{B}{C}\text{.}\)
If \(g \funccomp f\) is injective, are either or both of \(f,g\) necessarily injective?
Answer the same question as above with “injective” replaced by “surjective”.
Demonstrate that if both \(f\) and \(g\) are bijective, then the composition \(g \funccomp f\) is also bijective.
Of course, we can compose any number of functions.
Example10.4.7.A composition of three functions.
Let us reconsider the function defined by algorithm in Example 10.1.5. As the function description involved a multi-step algorithm, we should be able to break the steps involved into their own functions, then recreate the original functions as a composition.
First, define \(\funcdef{\operatorname{abs}}{\powset{\Z}}{\powset{\N}}\) by
Next, define \(\funcdef{\min}{\powset{\N}}{\N}\) so that \(\min(X)\) outputs the minimum number in input set \(X\text{,}\) and outputs \(0\) in case \(X = \emptyset\text{.}\)
Finally, define \(\funcdef{f}{\N}{\N}\) by \(f(n) = 2 n + 1\text{.}\)
Each of these functions represents one step in the algorithm defining the function in Example 10.1.5, but to recreate that function we need to compose the functions in the correct order: write \(\varphi = f \funccomp \min \funccomp \operatorname{abs}\text{,}\) so that
