Composition of Functions

definitions
discrete-math
set-theory
functions
proof

Chaining two functions into one, and which properties survive the chaining — in both directions. First met in 2026-09-08-composition-of-functions; the properties are defined in one-to-one-and-onto-functions and inverse-functions.

Definition

Let \(f : X \to Y\) and \(g : Y \to Z\) be functions. The composition of \(f\) and \(g\) is the function \(g \circ f : X \to Z\) defined by \[(g \circ f)(x) = g(f(x)) \quad\text{for all } x \in X.\]

Three things to read off the definition:

  • Right to left. \(g \circ f\) applies \(f\) first, then \(g\). The order of the symbols matches the formula \(g(f(x))\), not the order of events.
  • The domain of \(g \circ f\) is the domain of \(f\); the co-domain is the co-domain of \(g\). The middle set \(Y\) vanishes from the type.
  • It is defined only when \(f\)’s co-domain is \(g\)’s domain. \(g \circ f\) makes sense because \(f\) lands in \(Y\) and \(g\) eats \(Y\). The other composite, \(f \circ g\), would need \(g\)’s outputs (in \(Z\)) to be inputs to \(f\) (from \(X\)), so it exists only if \(Z = X\).

Figure 1: Why \(g \circ f\) exists and \(f \circ g\) usually does not. Top: \(f\) then \(g\) chains because \(f\) lands exactly where \(g\) starts. Bottom: \(g\) then \(f\) would need \(g\)’s outputs, in \(Z\), to be acceptable inputs to \(f\), which come from \(X\) — so it is defined only if \(Z = X\).

The composition itself is drawn in 2026-09-08-composition-of-functions: three ellipses, \(x \mapsto f(x) \mapsto g(f(x))\), with the long arrow \(g \circ f\) beneath.

Composition is not commutative. Even when both orders exist (\(X = Y = Z\)), \(g \circ f\) and \(f \circ g\) are generally different functions: with \(f(x) = x + 1\) and \(g(x) = 2x\) on \(\mathbb{R}\), \((g \circ f)(x) = 2x + 2\) but \((f \circ g)(x) = 2x + 1\).

Inverses and composition

For a bijection \(f : X \to Y\) with inverse \(f^{-1} : Y \to X\) (inverse-functions), both composites exist and both do nothing:

\[(f^{-1} \circ f)(x) = x \text{ for all } x \in X, \qquad (f \circ f^{-1})(y) = y \text{ for all } y \in Y.\]

This is the sense check on a computed inverse: for \(f((x,y)) = (y+1, 2x)\) and the claimed \(f^{-1}((x,y)) = \left(\frac{y}{2}, x - 1\right)\), \[f\!\left(f^{-1}((x,y))\right) = f\!\left(\left(\tfrac{y}{2}, x-1\right)\right) = (x, y). \;\checkmark\]

Which properties compose

Two facts:

If \(f\) and \(g\) are both onto, then \(g \circ f\) is onto. If \(f\) and \(g\) are both one-to-one, then \(g \circ f\) is one-to-one.

So both bijective gives \(g \circ f\) bijective. The proofs are short:

  • Onto. Let \(z \in Z\). Since \(g\) is onto, \(\exists\, y \in Y\) with \(g(y) = z\). Since \(f\) is onto, \(\exists\, x \in X\) with \(f(x) = y\). Then \(g(f(x)) = z\). \(\square\)
  • One-to-one. Suppose \(g(f(x_1)) = g(f(x_2))\). Since \(g\) is one-to-one, \(f(x_1) = f(x_2)\). Since \(f\) is one-to-one, \(x_1 = x_2\). \(\square\)

Which properties come back

The converse asks which ingredient must have a property when the composite has it. The answer is asymmetric:

If \(g \circ f\) is … then \(f\) must be … then \(g\) must be …
onto not necessarily onto
one-to-one one-to-one not necessarily

The property comes back to the function on its own side. Onto is about covering \(Z\), and \(g\) is the function that lands in \(Z\). One-to-one is about not merging elements of \(X\), and \(f\) is the function that leaves \(X\). The other ingredient can misbehave in the middle set \(Y\) without the composite noticing, as long as the misbehaviour is never exercised.

The two theorems, by contraposition

If \(g \circ f\) is onto, then \(g\) is onto.

Proof. We prove the contrapositive: if \(g\) is not onto then \(g \circ f\) is not onto. Suppose \(g\) is not onto. Then \(\exists\, z \in Z\) not in the range of \(g\). Then no \(x \in X\) has \(g(f(x)) = z\) — for if one did, \(y = f(x)\) would have \(g(y) = z\), a contradiction. So \(z\) is not in the range of \(g \circ f\), and \(g \circ f\) is not onto. \(\square\)

If \(g \circ f\) is one-to-one, then \(f\) is one-to-one.

Proof. We prove the contrapositive: if \(f\) is not one-to-one then \(g \circ f\) is not one-to-one. Suppose \(f\) is not one-to-one. Then \(\exists\, x_1 \neq x_2 \in X\) with \(f(x_1) = f(x_2)\). Hence \(g(f(x_1)) = g(f(x_2))\), i.e. \((g \circ f)(x_1) = (g \circ f)(x_2)\) with \(x_1 \neq x_2\), so \(g \circ f\) is not one-to-one. \(\square\)

Both go by contraposition (proof-techniques) for the same reason: not onto and not one-to-one are existential and hand you a concrete witness — a missed \(z\), a colliding pair — to push through the composite. The positive forms are universal and give nothing to hold onto. Anything the composite reaches, \(g\) reaches; anything \(f\) merges, the composite merges.

The two counterexamples, to order

\(g \circ f\) onto does not force \(f\) onto. \(X = \{a,b\}\), \(Y = \{0,1,2\}\), \(Z = \{v,w\}\); \(f = \{(a,0),(b,1)\}\), \(g = \{(0,v),(1,w),(2,w)\}\). Then \(f\) misses \(2\), but \(g \circ f = \{(a,v),(b,w)\}\) is onto.

\(g \circ f\) one-to-one does not force \(g\) one-to-one. \(X = \{a,b\}\), \(Y = \{1,2,3\}\), \(Z = \{u,v\}\); \(f = \{(a,1),(b,2)\}\), \(g = \{(1,u),(2,v),(3,v)\}\). Then \(g(2) = g(3)\), but \(g \circ f = \{(a,u),(b,v)\}\) is one-to-one.

Both are drawn in 2026-09-08-composition-of-functions, as (1) and (4) there, and both are built by the same recipe, which is the transferable skill:

  1. Make \(Y\) one element bigger than it needs to be. That spare element is where the defect will live.
  2. Give the defect to the function on the wrong side. For (1) \(f\) must miss the spare element; for (4) \(g\) must merge the spare element with another.
  3. Make sure the composite never touches it. In (1), \(g\) sends the missed element somewhere already covered, so the gap is invisible from \(Z\). In (4), \(f\) never lands on the merged element, so the collision is never fed.
  4. Use small sets. Two-element \(X\) and \(Z\) with a three-element \(Y\), as above, is enough; even smaller works. A counterexample is a witness; it does not need to be interesting.

The mirror symmetry is exact: (1) is gap in \(f\), hidden by a merge in \(g\); (4) is merge in \(g\), hidden by a gap in \(f\).

See also