Section 1.6 Functions and higher-order functions
In this unit we often need to reason about functions whose inputs and/or outputs are themselves functions, sometimes called higher-order functions. The supremum norm \(\n\blank_{\sup}\) in Example 1.7 is one such function; it takes in a function and outputs a real number. In order to avoid confusion, we will need to be extremely precise when we talk about functions of all types.
Definition 1.52.
A function (or mapping) \(f \maps A
\to B\) consists of
- a set \(A\text{,}\) called the domain;
- another set \(B\text{,}\) called the codomain; and
- a rule which associates a unique element \(f(a) \in B\) of the codomain to each element \(a \in A\) of the domain.
The set of functions with domain \(A\) and codomain \(B\) is denoted \(B^A\text{.}\)
Warning 1.53.
In this unit:
- The domain and codomain of a function are mandatory parts of its definition, and must be specified unless they are clear from context.
- The expressions \(f\) and \(f(a)\) in Definition 1.52 are not equivalent: \(f \in B^A\) is the function itself, while \(f(a) \in B\) is the output of the function for some input \(a \in A\text{.}\)
Definition 1.54.
Let \(A,B,C\) be sets and let \(f \maps A \to C\) and \(g \maps B \to C\) be functions. Suppose that \(A \subseteq B\) and \(f(a)=g(a)\) for all \(a \in A\text{.}\) Then we call \(f\) the restriction of \(g\) to \(A\) and write \(f = g|_A\text{.}\) We also call \(g\) an extension of \(f\) to \(B\text{.}\)
Example 1.55. Functions vs. formulas.
The following are all well-defined functions:
- the function \(f_1 \maps \R \to \R\) function defined by \(f_1(t)=t^2\text{;}\)
- the function \(f_2 \maps [0,1] \to \R\) defined by \(f_2(t)=t^2\text{;}\) and
- the function \(f_3 \maps [0,1] \to [0,1]\) defined by \(f_3(t)=t^2\text{.}\)
While \(f_1,f_2,f_3\) share the same formula \(t \mapsto
t^2\text{,}\) they are not the same as functions, because they have different domains and codomains. And indeed, these functions have different properties. For instance:
- \(f_3\) is surjective, but \(f_2\) and \(f_1\) are not.
- \(f_2\) and \(f_3\) are injective, but \(f_1\) is not.
- \(f_2\) and \(f_3\) are bounded, but \(f_1\) is not.
- \(f_2\) and \(f_3\) are uniformly continuous, while \(f_1\) is merely continuous.
Note that \(f_2 = f_1|_{[0,1]}\) is the restriction of \(f_1\) to \([0,1]\text{;}\) equivalently \(f_1\) is an extension of \(f_2\) to \(\R\text{.}\)
Convention 1.56. Anonymous functions.
Sometimes it’s useful to be able to talk about a function without giving it a name. One way to do this clearly is with the symbol \(\mapsto\text{,}\) read as ‘maps to’. For example, the last function in Example 1.55 could be described with a phrase like
“the function \([0,1] \to [0,1]\) given by \(t \mapsto t^2\)”.
Here \(t \mapsto t^2\) gives us the ‘formula’ or ‘rule’ describing the function, while \([0,1] \to [0,1]\) tells us about the domain and codomain. In cases where the domain and codomain are clear from context, we can use \(t \mapsto t^2\) as if it were the name of a function.
Definition 1.57.
Let \(f \maps A \to B\text{.}\) If \(C \subseteq A\text{,}\) then
\begin{equation*}
f(C) = \set{f(c)}{c \in C}
\end{equation*}
is called the image of \(C\) under \(f\text{.}\) If \(D
\subseteq B\text{,}\) then
\begin{equation*}
f^{-1}(D) = \set{a \in A}{f(a) \in D}
\end{equation*}
is called the preimage or inverse image of \(D\) under \(f\text{.}\)
Convention 1.58. Notation for higher-order functions.
Let \(A,B,C,D\) be sets.
- Let \(\Phi \in (A^B)^C\text{,}\) i.e. \(\Phi\) is a mapping \(C \to A^B\text{.}\) Then, for any \(c \in C\text{,}\) \(\Phi(c) \in A^B\text{,}\) i.e. \(\Phi(c)\) is a mapping \(B \to A\text{.}\) We denote the application of this mapping to an element \(b \in B\) by \(\Phi(c)(b)\text{.}\)
- Let \(\Phi \in A^{(B^C)}\text{,}\) i.e. \(\Phi\) is a mapping \(B^C \to A\text{.}\) Then, for any \(f \in B^C\text{,}\) i.e. any function \(f \maps C \to B\text{,}\) \(\Phi(f)\) is an element of \(A\text{.}\)
- Let \(\Phi \in (A^B)^{(C^D)}\text{,}\) i.e. \(\Phi\) is a mapping \(C^D \to A^B\text{.}\) Then, for any \(f \in C^D\text{,}\) i.e. any function \(f \maps D \to C\text{,}\) \(\Phi(f) \in A^B\text{,}\) i.e. \(\Phi(f)\) is a mapping \(B \to A\text{.}\) We denote the application of this mapping to an element \(b \in B\) by \(\Phi(f)(b)\text{.}\)
Example 1.59. Some simple higher-order functions.
- We can define a mapping \(\Phi_1 \in (\R^\R)^\R\) by\begin{equation*} \Phi_1(t)(s) = t+s^2\text{.} \end{equation*}This means that, for any \(t \in \R\text{,}\) \(\Phi_1(t) \in \R^\R\) is the function \(s \mapsto t+s^2\text{.}\)
- We can define a mapping \(\Phi_2 \in \R^{(\R^\R)}\) by\begin{equation*} \Phi_2(f) = f(0)f(1)\text{.} \end{equation*}For instance, if \(f \maps \R \to \R\) is defined by \(f(t)=e^{2t}\text{,}\) then we would have \(\Phi_2(f) = e^0 e^2 = e^2\text{.}\)
- We can define a mapping \(\Phi_3 \in (\R^\R)^{(\R^\R)}\) by\begin{equation*} \Phi_3(f)(t) = f(t)+f(2t)\text{.} \end{equation*}For instance, if \(f \maps \R \to \R\) is defined by \(f(t)=e^{2t}\text{,}\) then \(\Phi_3(f) \in \R^\R\) is the function \(t \mapsto e^{2t} + e^{4t}\text{.}\)
Remark 1.60. Non-examinable examples using Python.
Higher-order functions are also an important concept in Computer Science, where similar notation is often used. For instance, the mappings \(\Phi_1,\Phi_2,\Phi_3\) in Example 1.59 could be implemented in Python as follows.
def Phi1(t):
def f(s):
return t+s**2
return f
def Phi2(f):
return f(0)*f(1)
def Phi3(f):
def g(t):
return f(t)+f(2*t)
return g
Alternatively, using
lambda,Phi1 = lambda t: (lambda s: t+s**2)
Phi2 = lambda f: f(0)*f(1)
Phi3 = lambda f: (lambda t: f(t)+f(2*t))
Our main interest in higher order functions is not in their algebraic properties, but in their analytical properties, such as continuity.
Example 1.61. Continuity of a higher-order function.
Show that \(\Phi_3\) from Example 1.59 is a well-defined and continuous \(B(\R) \to B(\R)\text{,}\) where as usual \(B(\R)\) is equipped with the supremum norm.
Solution.
First we must check that \(\Phi_3\) is well-defined as a mapping \(B(\R) \to B(\R)\text{,}\) that is that \(\Phi_3(f) \in B(\R)\) whenever \(f
\in B(\R)\text{.}\) But this is clear as
\begin{align*}
\n{\Phi_3(f)}_{\sup}
\amp = \sup_{t \in \R} \abs{f(t) + f(2t)}\\
\amp \le \sup_{t \in \R} \abs{f(t)}
+ \sup_{t \in \R} \abs{f(2t)}\\
\amp = 2\n f_{\sup} \lt \infty
\end{align*}
whenever \(f \in B(\R)\text{.}\)
We will show that \(\Phi_3 \maps B(\R) \to B(\R)\) is in fact Lipschitz continuous. Let \(f,g \in B(\R)\text{.}\) Then we can estimate
\begin{align*}
\n{\Phi_3(f)-\Phi_3(g)}_{\sup}
\amp = \sup_{t \in \R} \abs{\Phi_3(f)(t)-\Phi_3(g)(t)}\\
\amp = \sup_{t \in \R} \abs{(f(t)+f(2t))-(g(t)+g(2t))}\\
\amp \le \sup_{t \in \R} \abs{f(t)-g(t)}
+ \sup_{t \in \R} \abs{f(2t)-g(2t))}\\
\amp = 2\n{f-g}_{\sup}\text{.}
\end{align*}
Thus the mapping is Lipschitz (with Lipschitz constant \(2\)).
Comment.
Note that the question is asking about the continuity of \(\Phi_3\) as a mapping \(B(\R) \to B(\R)\text{.}\) This is completely different from, for instance, the question of whether \(\Phi_3(f) \maps \R \to \R\) is continuous for some particular \(f \in B(\R)\text{.}\)
Exercises Exercises
1. (PS4) Compositions of higher-order functions.
Define mappings \(\Phi_1 \in (\R^\R)^\R\text{,}\) \(\Phi_2 \in \R^{(\R^\R)}\) and \(\Phi_3 \in (\R^\R)^{(\R^\R)}\) by
\begin{align*}
\Phi_1(t)(s) \amp = e^{st},\\
\Phi_2(f) \amp = f(0)+f(1),\\
\Phi_3(f)(t) \amp = f(t)f(1+t)\text{.}
\end{align*}
For each of the following expressions, state what type of object it is, and give an explicit formula. Be mindful of Warning 1.53!
(a)
\(\Phi_2(\Phi_1(1))\)
Solution 1. Outside-in
The domains and codomains of \(\Phi_1,\Phi_2\) line up nicely,
\begin{equation*}
1 \in \R \xrightarrow{\Phi_1} \R^\R \xrightarrow{\Phi_2} \R\text{,}
\end{equation*}
with \(1\) lying in the domain of \(\Phi_1\text{.}\) Thus \(\Phi_2(\Phi_1(1))\) is a well-defined element of \(\R\text{,}\) the codomain of \(\Phi_2\text{.}\) To find the value of this real number, we simply manipulate the expressions in brackets using our formulas for \(\Phi_1,\Phi_2\text{:}\)
\begin{align*}
\Phi_2(\Phi_1(1))
\amp = \Phi_1(1)(0) + \Phi_1(1)(1)\\
\amp = e^0 + e^1 \\
\amp = 1 + e\text{.}
\end{align*}
Here the first line is the trickiest one; you can think of it as plugging \(f = \Phi_1(1)\) into our formula for \(\Phi_2(f)\text{,}\) so that \(f(0)=\Phi_1(1)(0)\) and so on.
Solution 2. Inside-out
The previous solution works “from the outside in”, first using our formula for \(\Phi_2\) and only then using our formula for \(\Phi_1\text{.}\) Many students instead worked from “from the inside out”, first dealing with the \(\Phi_1(1)\) and only then applying our formula for \(\Phi_2\text{.}\) One way to accomplish this is with the \(\mapsto\) symbol; see this Convention 1.56 above. The fact that \(\Phi_2(\Phi_1(1))
\in \R\) follows as before, but to find the formula we now calculate this way:
\begin{align*}
\Phi_2(\Phi_1(1))
\amp = \Phi_2(t \mapsto e^t)\\
\amp = (t \mapsto e^t)(0) + (t \mapsto e^t)(1)\\
\amp = 1 + e\text{.}
\end{align*}
If you don’t like the \(\mapsto\) notation, you can always give this function a name. We could say that \(\Phi_1(1)\) is the function \(f
\maps \R \to \R\) defined by \(f(t) = e^t\text{,}\) and hence
\begin{align*}
\Phi_2(\Phi_1(1))
\amp = \Phi_2(f)\\
\amp = f(0) + f(1)\\
\amp = 1 + e\text{.}
\end{align*}
Comment 1.
Especially in more applied units, one is encouraged to view the function \(t \mapsto e^t\) and the expression \(e^t\) as essentially the same object. When talking about mappings between space of functions, this ambiguity in notation can lead to real confusion (and real lost marks on an exam). To avoid this, please do not write things like \(\Phi_1(e^t)\) when what you really mean is \(\Phi_1(t \mapsto e^t)\text{.}\) If you don’t like the \(\mapsto\) notation, then you can always introduce names for the various functions you encounter, as is done in the second official solution. Alternatively, arguing as in the first official solution, we didn’t actually encounter this issue at all!
Comment 2.
While the question asks what type of object \(\Phi_2(\Phi_1(1))\) is, in past years many students instead gave the type of the object \(\Phi_2 \circ \Phi_1\text{,}\) or else \(\Phi_2\) or \(\Phi_1\text{.}\) Note that these are different questions with different answers! Seems to be less of an issue this year.
(b)
\(\Phi_3(\Phi_1(2))\)
Solution 1. Outside-in
As with the previous part, the domains and codomains of \(\Phi_3,\Phi_1\) line up nicely:
\begin{equation*}
2 \in \R \xrightarrow{\Phi_1} \R^\R \xrightarrow{\Phi_3} \R^\R.
\end{equation*}
Thus \(\Phi_3(\Phi_1(2))\) is a well-defined element of \(\R^\R\text{,}\) the codomain of \(\Phi_3\text{.}\) In other words, \(\Phi_3(\Phi_1(2)) \maps \R \to \R\text{.}\) To get a formula for this function, we should input a real number, say \(t \in \R\text{.}\) Using our formulas for \(\Phi_1,\Phi_3\) we find that
\begin{align*}
\Phi_3(\Phi_1(2))(t)
\amp = \Phi_1(2)(t) \cdot \Phi_1(2)(1+t)\\
\amp = e^{2t} \cdot e^{2(1+t)}\\
\amp = e^{4t+2}\text{.}
\end{align*}
Solution 2. Inside-out
Alternatively, we can find the formula for \(\Phi_3(\Phi_1(2))\) working from the inside out. The fact that \(\Phi_3(\Phi_1(2)) \in \R^\R\) is a mapping \(\R \to
\R\) follows as in the previous solution, but now we calculate
\begin{align*}
\Phi_3(\Phi_1(2))(t)
\amp =
\Phi_3(s \mapsto e^{2s})(t)\\
\amp =
(s \mapsto e^{2s})(t) \cdot (s \mapsto e^{2s})(1+t)\\
\amp = e^{2t} \cdot e^{2(1+t)}\\
\amp = e^{4t+2}\text{.}
\end{align*}
To avoid the \(\mapsto\) notation, we can give the intermediate function a name. Let \(f = \Phi_1(2)\) be the function \(\R \to \R\) defined by \(f(t) = e^{2t}\text{.}\) Then
\begin{align*}
\Phi_3(\Phi_1(2))(t)
\amp = \Phi_3(f)(t)\\
\amp = f(t)f(1+t) \\
\amp = e^{2t} e^{2(t+1)} \\
\amp = e^{4t+2}\text{.}
\end{align*}
Comment 1.
Many students wrote things like \(\Phi_3(e^{2t}) = e^{4t+2}\text{.}\) Strictly speaking this is incorrect, and you should write something more verbose like \(\Phi_3(s \mapsto e^{2s})(t) = e^{4t+2}\text{,}\) or alternatively give the function \(s \mapsto e^{2s}\) a name as was done in the official solution. I won’t take off marks on exam for using the sloppier notation, but I’ve seen a lot of students on exams who use the sloppier notation get confused about what the mapping in the question even is, and lose a huge number of marks. Whatever notation you use, please be careful and stop to think about what these expressions mean.
Comment 2.
While the question asks what type of object \(\Phi_3(\Phi_1(2))\) is, in past years many students gave the type of the object \(\Phi_3 \circ \Phi_1\text{,}\) or else \(\Phi_3\) or \(\Phi_1\text{.}\) Note that these are different questions with different answers! Seems to be less of an issue this year.
(c)
\(\Phi_2 \circ \Phi_3\)
Solution 1. Outside-in
Once again, the domains and codomains of \(\Phi_2,\Phi_3\) line up nicely
\begin{equation*}
\R^\R \xrightarrow{\Phi_3} \R^\R \xrightarrow{\Phi_2} \R
\end{equation*}
so that the composition \(\Phi_2 \circ \Phi_3 \maps \R^\R \to \R\text{.}\) To find a formula for this mapping, we need to feed it an element of \(\R^\R\text{,}\) i.e. a function \(f \maps \R \to \R\text{.}\) Using the formulas for \(\Phi_2,\Phi_3\) we calculate
\begin{align*}
(\Phi_2 \circ \Phi_3)(f)
\amp = \Phi_2(\Phi_3(f))\\
\amp = \Phi_3(f)(0) + \Phi_3(f)(1)\\
\amp = f(0)f(0+1) + f(1)f(1+1)\\
\amp = f(0) f(1) + f(1) f(2)\text{.}
\end{align*}
Solution 2. Inside-out
Alternatively, we can calculate this composition from the inside out. Deducing as before that \(\Phi_2 \circ \Phi_3 \maps \R^\R \to \R\text{,}\) we have that, for \(f \in \R^\R\text{,}\)
\begin{align*}
(\Phi_2 \circ \Phi_3)(f)
\amp = \Phi_2\big(t \mapsto f(t)f(1+t)\big)\\
\amp = \big(t \mapsto f(t)f(1+t)\big)(0) + \big(t \mapsto f(t)f(1+t)\big)(1)\\
\amp = f(0)f(0+1) + f(1)f(1+1)\\
\amp = f(0) f(1) + f(1) f(2)\text{.}
\end{align*}
If you don’t like the \(\mapsto\) notation, you can introduce a name for the intermediate function. Given \(f \in \R^\R\text{,}\) let \(g = \Phi_2(f) \maps
\R \to \R\) be the function defined by \(g(s) = f(s)f(1+s)\text{.}\) Then
\begin{align*}
(\Phi_2 \circ \Phi_3)(f)
\amp = \Phi_2(g)\\
\amp = g(0) + g(1)\\
\amp = f(0)f(0+1) + f(1)f(1+1)\\
\amp = f(0) f(1) + f(1) f(2)\text{.}
\end{align*}
