Section 10.4 Composition of functions

composition function: a function \(A \to C \) created from 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)} \)

Figure 10.4.1. A Venn diagram of a function composition.

Example 10.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*}

Warning 10.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.

Example 10.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

\begin{align*} (f \funccomp g)(n) \amp = (n+1)^2 = n^2+2n+1, \amp (g \funccomp f)(n) \amp = n^2+1. \end{align*}

Example 10.4.5. An undefined composition.

Consider functions

\begin{align*} \sqrtop \colon \N \amp \to \R, \amp \flr \colon \R \amp \to \Z, \\ n \amp \mapsto \sqrt{n}, \amp x \amp \mapsto \floor{x}. \end{align*}

(See Example 10.3.15 for a description of the \(\flr \) function.)

Then, \(\funcdef{\flr \funccomp \sqrtop}{\N}{\Z} \) is defined, with

\begin{equation*} (\flr \funccomp \sqrtop)(n) = \floor{\sqrt{n}} \text{.} \end{equation*}

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{.}\)

Checkpoint 10.4.6. Properties of compositions.

Consider functions \(\funcdef{f}{A}{B} \) and \(\funcdef{g}{B}{C} \text{.}\)

(a)

If \(g \funccomp f \) is injective, are either or both of \(f,g \) necessarily injective?

(b)

Answer the same question as above with “injective” replaced by “surjective”.

(c)

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.

Example 10.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

\begin{equation*} \operatorname{abs}(X) = \setdef{\abs{x}}{x \in X} \text{.} \end{equation*}

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

\begin{equation*} \varphi(X) = 2 \min\bbrac{\operatorname{abs}(X)} + 1 \end{equation*}

computes the same result for an input set \(X \) as the algorithm described in Example 10.1.5.

Prev Top Next