Composition of Functions

Composition of functions is the operational glue behind the Symmetric Group: the set of all bijections from a set $A$ to itself, under composition, forms a group precisely because of the Theorem proved here — associativity holds automatically, the identity function is the neutral element by part (5), and part (4) guarantees the composite of two bijections is again a bijection (closure), while inverses exist by the theory of Bijections and Inverse Functions. This single algebraic structure underlies the study of permutations, Galois theory, and crystallographic symmetry groups in physics and chemistry. In computer science, function composition is the semantic backbone of functional programming: pipelines built from `map`, `filter`, and user-defined transformations are literally composites of functions, and compilers rely on associativity to reorder or fuse composed operations for optimization without changing program behavior. In category theory, the associativity and identity laws proved above for composition of functions are abstracted into the defining axioms of a category, where "functions" are replaced by arbitrary morphisms between objects — matrices under multiplication, continuous maps between topological spaces, or measurable maps between probability spaces are all instances. In analysis, the chain rule for differentiation is precisely a statement about how differentiability interacts with composition, $(g\circ f)'(a) = g'(f(a))\cdot f'(a)$, and the injectivity-preservation fact underlies the construction of inverse functions locally (via the Inverse Function Theorem). In cryptography, block ciphers are built as long composites of simple, invertible round functions; the fact that a composite of bijections is a bijection (part 4 of the Theorem) is exactly what guarantees that encryption remains reversible after many rounds, while associativity guarantees the encryption pipeline can be re-associated or parallelized without changing the ciphertext produced. In statistics and measure theory, composing a random variable (a measurable function) with a further measurable function produces a new random variable, and questions about which distributional properties are preserved under such composition parallel exactly the injectivity/surjectivity analysis given here.

Ask the tutor: If $g \circ f$ is both injective and surjective, exactly which of $f$ and $g$ can I conclude are individually bijective, and what extra assumption would let me conclude both are?

Think of a function as a machine with an input slot and an output chute, labeled by its domain and codomain. Composition is physically bolting two machines together: the output chute of the first machine ($f$) is welded to the input slot of the second ($g$), so that whatever comes out of $f$ immediately becomes the input fed into $g$. The welding only makes physical sense if the shapes match — the codomain of $f$ must be (a subset of, or exactly) the domain of $g$. That is why $g \circ f$ requires $f: A \to B$ and $g : B \to C$ to share the middle set $B$. The notation $g \circ f$ is read "$g$ after $f$" or "$g$ compose $f$", and it is written in the opposite order from how you'd describe the process in English: you apply $f$ first, then $g$, but $f$ appears on the right, closest to the input variable $a$ in $(g\circ f)(a) = g(f(a))$. This ordering convention matches ordinary function notation and is the price paid for writing $g(f(a))$ instead of $(a)f g$. Associativity says that when you chain three machines $f$, $g$, $h$, it does not matter whether you first bolt $f$ to $g$ and then attach $h$, or first bolt $g$ to $h$ and then prepend $f$ — the final three-stage machine is identical either way. This is not a deep fact about functions specifically; it follows because both sides compute $h(g(f(a)))$ pointwise. But it is exactly what allows us to write $h \circ g \circ f$ without parentheses, and it is the algebraic bedrock underlying associative structures throughout mathematics, from matrix multiplication to the composition law in a category.

Example 1 (asymmetric domains, tracking injectivity and surjectivity through a chain). Let $A = \{1,2,3\}$, $B = \{p,q,r,s\}$, $C = \{x,y\}$. Define

Here $f$ is injective (three distinct inputs, three distinct outputs $p,q,r$) but not surjective onto $B$ (the element $s$ is missed). The function $g$ is surjective onto $C$ (both $x$ and $y$ are hit) but not injective ($p$ and $q$ both map to $x$). Compute $g \circ f : A \to C$:

Observe $(g\circ f)(1) = (g \circ f)(2) = x$ with $1 \neq 2$, so $g \circ f$ is not injective, even though $f$ alone is injective. This is consistent with the Theorem: preservation of injectivity requires both $f$ and $g$ injective, and here $g$ fails to be injective, so there is no contradiction. It also illustrates the asymmetric converse fact stated in the summary: since $g \circ f$ is (in this example) not injective, the theorem gives no information forcing $g$ to be injective — indeed $g$ is not. Meanwhile $g \circ f$ is surjective onto $C = \{x,y\}$ (both $x$ and $y$ occur as values), consistent with $g$ being surjective even though $f$ is not. This example shows the two preservation directions are independent: injectivity of the composite is controlled by injectivity of the inner function chain in a way that critically needs the outer function $g$ to not collapse distinct values, while surjectivity of the composite is driven by the outer function $g$'s surjectivity, needing the inner function $f$ to reach enough of $B$ to feed $g$'s full range — but as this example shows, $f$ need not be surjective onto all of $B$, only onto enough of $B$ to hit a preimage of every element of $C$ under $g$.

Example 2 (verifying associativity concretely with three genuinely different finite functions). Let $A = \{1,2\}$, $B = \{a,b,c\}$, $C = \{u,v\}$, $D = \{\alpha,\beta,\gamma\}$. Define

Compute $g \circ f : A \to C$ first:

Then compute $h \circ (g\circ f) : A \to D$:

Now compute the other grouping. First $h \circ g : B \to D$:

Then $(h\circ g)\circ f : A \to D$:

Both computations give the function $A \to D$ sending $1 \mapsto \gamma$ and $2 \mapsto \gamma$, confirming

in this concrete case, exactly as the Theorem guarantees. Note also that $g \circ f$ collapses $1$ and $2$ to the common value $v$ — since $f(1)=a \ne c=f(2)$ but $g(a)=g(c)=v$ — again illustrating that $g \circ f$ can fail injectivity even when $f$ is injective, because $g$ itself is not injective on $\{a,c\}$.