Functions and higher-order functions

Section 1.6 Functions and higher-order functions

Recordings on Re:View.

The entire section

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.

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))\)

(b)

\(\Phi_3(\Phi_1(2))\)

(c)

\(\Phi_2 \circ \Phi_3\)

Prev Top Next