Composition and Function Spaces

The composition of functions and the structure of function spaces are central to modern mathematics. These concepts allow us to treat functions themselves as mathematical objects, leading to powerful abstract constructions.

DefinitionComposition of Functions

Let $f: A \to B$ and $g: B \to C$ be functions. The composition of $g$ and $f$ , denoted $g \circ f$ (read "g after f" or "g composed with f"), is the function $(g \circ f): A \to C$ defined by:

(g \circ f)(a) = g(f(a)) \quad \text{for all } a \in A

As a set of ordered pairs: $g \circ f = \{(a, c) : \exists b \in B((a, b) \in f \land (b, c) \in g)\}$ .

Composition captures the idea of applying functions sequentially. The output of $f$ becomes the input to $g$ , producing a new function from $A$ to $C$ . Note that the order matters: $g \circ f$ means "first $f$ , then $g$ ," which may seem backwards from the notation.

ExampleFunction Composition Examples

If $f: \mathbb{R} \to \mathbb{R}$ is $f(x) = x^2$ and $g: \mathbb{R} \to \mathbb{R}$ is $g(x) = x + 1$ , then:
- $(g \circ f)(x) = g(f(x)) = g(x^2) = x^2 + 1$
- $(f \circ g)(x) = f(g(x)) = f(x + 1) = (x + 1)^2 = x^2 + 2x + 1$
Note that $g \circ f \neq f \circ g$ in general!
For any function $f: A \to B$ :
- $f \circ \text{id}_A = f$ (identity on the left)
- $\text{id}_B \circ f = f$ (identity on the right)
If $f: A \to B$ is bijective with inverse $f^{-1}: B \to A$ , then:
- $f^{-1} \circ f = \text{id}_A$
- $f \circ f^{-1} = \text{id}_B$

TheoremAssociativity of Composition

Composition of functions is associative. For functions $f: A \to B$ , $g: B \to C$ , and $h: C \to D$ :

h \circ (g \circ f) = (h \circ g) \circ f

Thus we can write $h \circ g \circ f$ without ambiguity.

Proof

Both sides are functions from $A$ to $D$ . For any $a \in A$ :

\begin{align*} [h \circ (g \circ f)](a) &= h((g \circ f)(a)) = h(g(f(a))) \\ [(h \circ g) \circ f](a) &= (h \circ g)(f(a)) = h(g(f(a))) \end{align*}

Since both give the same result for every $a \in A$ , the functions are equal.

■

DefinitionFunction Space

Given sets $A$ and $B$ , the function space (or set of all functions) from $A$ to $B$ is denoted:

B^A = \{f : f \text{ is a function from } A \text{ to } B\}

This notation suggests exponentiation, and indeed, when $A$ and $B$ are finite, $|B^A| = |B|^{|A|}$ .

The function space $B^A$ is itself a set (by the axioms of ZFC), which allows us to consider functions between function spaces, leading to higher-order functions and functional analysis.

ExampleFinite Function Spaces

If $A = \{1, 2\}$ and $B = \{a, b, c\}$ , then $|B^A| = 3^2 = 9$ . The nine functions are all possible ways to assign elements of $B$ to elements of $A$ :
$\{1 \mapsto a, 2 \mapsto a\}, \{1 \mapsto a, 2 \mapsto b\}, \ldots, \{1 \mapsto c, 2 \mapsto c\}$
The set $2^A = \{0, 1\}^A$ is the set of all functions from $A$ to $\{0, 1\}$ . This is naturally bijective with $\mathcal{P}(A)$ via characteristic functions:
$\chi: \mathcal{P}(A) \to 2^A, \quad S \mapsto \chi_S$
where $\chi_S(a) = 1$ if $a \in S$ and $\chi_S(a) = 0$ if $a \notin S$ .
For infinite sets, $\mathbb{R}^\mathbb{N}$ is the set of all sequences of real numbers, while $\mathbb{R}^\mathbb{R}$ is the (much larger) set of all functions from $\mathbb{R}$ to $\mathbb{R}$ .

DefinitionRestriction and Extension

Let $f: A \to B$ be a function and $C \subseteq A$ .

The restriction of $f$ to $C$ is the function $f|_C: C \to B$ defined by:

f|_C = f \cap (C \times B) = \{(c, b) \in f : c \in C\}

Conversely, if $g: C \to B$ and $f: A \to B$ satisfy $g = f|_C$ , we say $f$ is an extension of $g$ to $A$ .

Remark

Restrictions always exist (by comprehension), but extensions may not be unique. Given $g: C \to B$ , there are typically many ways to extend it to a function $f: A \to B$ , unless additional constraints are imposed.

DefinitionProduct and Coproduct

Given families of functions $\{f_i: A \to B_i\}_{i \in I}$ , the product function is:

\prod_{i \in I} f_i: A \to \prod_{i \in I} B_i, \quad a \mapsto (f_i(a))_{i \in I}

Given families $\{f_i: A_i \to B\}_{i \in I}$ with disjoint domains, the coproduct function is:

\coprod_{i \in I} f_i: \coprod_{i \in I} A_i \to B, \quad (i, a) \mapsto f_i(a)

These constructions are fundamental in category theory and universal algebra.

ExampleCurry-Howard Correspondence

In type theory and logic, there is a deep correspondence:

Types correspond to sets
Terms correspond to elements
Function types $A \to B$ correspond to function spaces $B^A$
Composition corresponds to modus ponens
The identity corresponds to axioms of identity

This Curry-Howard correspondence connects set theory, type theory, and logic, showing that:

\text{Propositions} \leftrightarrow \text{Types} \leftrightarrow \text{Sets}

\text{Proofs} \leftrightarrow \text{Programs} \leftrightarrow \text{Functions}

TheoremExponential Laws

For sets $A$ , $B$ , $C$ :

$(B \times C)^A \cong B^A \times C^A$ (distributivity over products)
$(B^C)^A \cong B^{C \times A}$ (currying)
$B^{A + C} \cong B^A \times B^C$ where $A + C$ denotes disjoint union
$(B^A)^C \cong B^{A \times C}$ (uncurrying)

These isomorphisms explain why function space notation uses exponents.

The study of function spaces leads naturally to functional analysis, where we consider infinite-dimensional spaces of functions with topological and algebraic structure. Understanding composition, restriction, and these exponential laws provides the foundation for advanced mathematical constructions throughout pure and applied mathematics.