Proof of the associativity of function composition

Introduction

First, let's define function composition.

Let \(A\), \(B\) and \(C\) be sets, and let \(f\) and \(g\) be functions defined as:

\[ \begin{align} f: A \to B\\ g: B \to C\\ \end{align} \]

We define function composition (denoted with a composition operator \(\circ\)) as a function that takes two functions, \(f\) and \(g\), and returns a new function, \(h: A \to C\), such that

\[ \begin{align} \forall x \in A,\ \ h(x) = (g \circ f)(x) = g(f(x)) \end{align} \]

You can think of (or pronounce) \(\circ\) as "follows". So, \(g \circ f\) is "\(g\) follows \(f\)". You first apply \(f\) to \(x\), and then \(g\) to the output of applying \(f\) to \(x\).

Naturally, composition \(g \circ f\) is only valid/meaningful \(iff\) the codomain (output) of \(f\) equals the domain (input) of \(g\) (or at least if the the former is an improper subset of the latter).

Now, let's prove that function composition is associative.

Let \(A\), \(B\), \(C\), \(D\) be sets, and let \(f\), \(g\), \(h\) be functions defined as:

\[ \begin{align} f: A \to B\\ g: B \to C\\ h: C \to D \end{align} \]

then

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

Proof:

Let \(x \in A\). Then

\[ \begin{align} (h \circ (g \circ f))(x)\\ = h((g \circ f)(x))\\ = h(g(f(x))) \end{align} \]

Now let

\[ y = f(x) \]

and put that back in

\[ \begin{align} h(g(f(x)))\\ =h(g(y))\\ =(h \circ g)(y)\\ \end{align} \]

Now lets define a temporary function \(e: B \to D\) as

\[ e = h \circ g \]

Let's put that back in and also replace \(y\) with \(f(x)\)

\[ \begin{align} (h \circ g)(y)\\ =e(y)\\ =e(f(x))\\ =(e \circ f)(x)\\ \end{align} \]

Let's now replace \(e\) with \(h \circ g\)

\[ \begin{align} (e \circ f)(x)\\ =((h \circ g) \circ f)(x)\\ \\ \blacksquare \end{align} \]

Naturally, the presented proof is only one of many possible proofs; another, shorter, is:

Let \(A\), \(B\), \(C\), \(D\) be sets, and let \(f\), \(g\), \(h\) be functions defined as:

\[ \begin{align} f: A \to B\\ g: B \to C\\ h: C \to D \end{align} \]

Then

\[ \begin{align} \forall x \in A\\ \\ (h \circ (g \circ f))(x) = h((g \circ f)(x)) = h(g(f(x)))\\ \\ ((h \circ g) \circ f)(x) = (h \circ g)(f(x)) = h(g(f(x)))\\ \\ \blacksquare \end{align} \]

All this is to prove the essence of associativity - where you place the parentheses doesn't matter.

\[ \begin{align} \forall x \in A\\ \\ (h \circ (g \circ f))(x) = ((h \circ g) \circ f)(x) = (h \circ g \circ f)(x) = h(g(f(x))) \end{align} \]

This is it for today. I hope you find this article useful. As per usual, if you find any errors, send me a mail at luka [at] ljudi [dot] org. Cheers!