10.4: Composition of functions
- Page ID
- 83454
a function \(A \to C\) created from given functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\) by \(a \mapsto g(f(a))\)
the composition of functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\text{,}\) so that \(g \circ f: A\rightarrow C\) by \((g \circ f)(a) = g(f(a))\)
Consider the functions
\begin{align*} f \colon \mathbb{R} & \to \mathbb{R}_{\geq 0}, & g \colon \mathbb{R}_{\geq 0} & \to \mathbb{R}_{\geq 0},\\ x & \mapsto x^2, & x & \mapsto \sqrt{x}, \end{align*}
Then we have
\begin{align*} g \circ f \colon \mathbb{R} & \to \mathbb{R}_{\geq 0}, \\ x & \mapsto \sqrt{x^2} = \vert x \vert. \end{align*}
The notation for the composition of functions \(f\) and \(g\) involves a reversal of order, so that we write \(g \circ f\text{.}\) This is so that when we use this notation with input-output notation \((g \circ 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 \circ g \ne g \circ 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.
Consider functions
\begin{align*} f \colon \mathbb{N} & \to \mathbb{N}, & g \colon \mathbb{N} & \to \mathbb{N}, \\ n & \mapsto n^2, & n & \mapsto n + 1. \end{align*}
Then, both \(f \circ g: \mathbb{N} \rightarrow \mathbb{N}\) and \(g \circ f: \mathbb{N} \rightarrow \mathbb{N}\) are defined. But they are not equal, as
\begin{align*} (f \circ g)(n) & = (n+1)^2 = n^2+2n+1, & (g \circ f)(n) & = n^2+1. \end{align*}
Consider functions
\begin{align*} \text{sqrt} \colon \mathbb{N} & \to \mathbb{R}, & \text{flr} \colon \mathbb{R} & \to \mathbb{Z}, \\ n & \mapsto \sqrt{n}, & x & \mapsto \lfloor x \rfloor. \end{align*}
(See Example 10.3.4 for a description of the \(\text{flr}\) function.)
Then, \(\text{flr} \circ \text{sqrt} : \mathbb{N} \rightarrow \mathbb{Z}\) is defined, with
\begin{equation*} (\text{flr} \circ \text{sqrt} )(n) = \lfloor \sqrt{n} \rfloor \text{.} \end{equation*}
But \(\text{sqrt} \circ \text{flr}\) is not defined, as the codomain of \(\text{flr}\) does not match the domain of \(\text{sqrt} \text{.}\) In particular, \(\text{flr}\) will sometimes return a negative output, and we cannot use such an output as an input in \(\text{sqrt} \text{.}\)
Consider functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\text{.}\)
If \(g \circ 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 \circ f\) is also bijective.
Of course, we can compose any number of functions.
Let us reconsider the function defined by algorithm in Example 10.1.3. 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 \(\text{abs} : \mathscr{P}( \mathbb{Z}) \rightarrow \mathscr{P}( \mathbb{N})\) by
\begin{equation*} \text{abs}(X) = \{\vert x \vert \; \vert x \in X\} \text{.} \end{equation*}
Next, define \(min : \mathscr{P}( \mathbb{N}) \rightarrow \mathbb{N}\) so that \(\text{min}(X)\) outputs the minimum number in input set \(X\text{,}\) and outputs \(0\) in case \(X = \emptyset\text{.}\)
Finally, define \(f: \mathbb{N} \rightarrow \mathbb{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.3, but to recreate that function we need to compose the functions in the correct order: write \(\varphi = f \circ \text{min} \circ \text{abs}\text{,}\) so that
\begin{equation*} \varphi(X) = 2 \text{min}(\text{abs}(X)) + 1 \end{equation*}
computes the same result for an input set \(X\) as the algorithm described in Example 10.1.3.