Lecture 20 — Composition of Functions
Pre-work: Video 026 (Composition of functions). The reference note is composition-of-functions; the properties it builds on are in one-to-one-and-onto-functions and inverse-functions. The order here: the one-to-one and onto templates again, two worked examples on inverses, then the composition results.
Date. On the schedule this is the Thursday 10/09 lecture; on the one-ahead reading explained under math1061 it is Tuesday 08/09.
Learning goals
- Review definitions of injective and surjective functions.
- Investigate conditions for a composition of functions to be one-to-one, onto.
The picture to keep in mind has three sets \(X\), \(Y\), \(Z\). \(f\) sends \(x \mapsto f(x)\), a hop \(X \to Y\). \(g\) sends \(f(x) \mapsto g(f(x))\), a hop \(Y \to Z\). \(g \circ f\) goes from \(x\) straight to \(g(f(x))\).
Worked: is \(f \circ g\) also a bijection?
If \(f : X \to Y\) and \(g : Y \to Z\) are both bijective functions, then the composition \(g \circ f : X \to Z\) is also a bijection. In this case, is \(f \circ g\) also a bijection?
For \(f \circ g\) to be defined, we need \(X = Z\). With that, yes, \(f \circ g\) is a bijection.
\(f \circ g\) means \(g\) first, then \(f\): \(Y \xrightarrow{\;g\;} Z \xrightarrow{\;f\;} Y\), with \(Z = X\). So \(g\)’s outputs — elements of \(Z\) — have to be things \(f\) accepts — elements of \(X\). Unless \(Z = X\) the expression is not meaningless-but-false; it is simply undefined. Composition is not commutative, and most of the time the other order does not even exist.
The one-to-one and onto templates
The four templates were first met in 2026-09-07-functions-one-to-one-onto-inverse. Going backwards along \(f\) shows the two ways an inverse fails. When \(f\) is not one-to-one, the shared value \(f(x_1) = f(x_2)\) leads back to two sources. When \(f\) is not onto, the unreached element of \(Y\) has nothing to lead back to.
Injective (one-to-one): to show, suppose \(f(x_1) = f(x_2)\) and show \(x_1 = x_2\); to show not, find \(x_1 \neq x_2\) with \(f(x_1) = f(x_2)\).
Surjective (onto): to show, suppose \(y \in Y\) and find \(x \in X\) with \(f(x) = y\); to show not, find \(y \in Y\) with \(f(x) \neq y\) for all \(x\).
Bijective: both. A bijection \(f : X \to Y\) has an inverse function \(f^{-1} : Y \to X\), with \(f^{-1}(y) = x\) where \(x\) is the unique element in \(X\) such that \(f(x) = y\). The converse holds too, which makes it an equivalence:
\[f \text{ has an inverse} \iff f \text{ is a bijection.}\]
Worked: the largest prime divisor
Consider the function \(f : \mathbb{Z} - \{-1, 0, 1\} \to \mathbb{Z}^{>1}\) defined by \(f(x) = p\), where \(p\) is the largest prime divisor of \(x\).
Some values first, to see what the function does: \(f(2) = 2\), \(f(10) = 5\), \(f(-6) = 3\). Removing \(-1\), \(0\), \(1\) from the domain is what makes it a function at all: \(\pm 1\) have no prime divisor, and \(0\) is divisible by every prime, so it has no largest one.
(a) Is \(f\) an injection? \(f(10) = 5\), \(f(15) = 5\) and \(10 \neq 15\). Not injective.
(b) Is \(f\) a surjection? No. \(4 \in \mathbb{Z}^{>1}\) but \(4 = 2 \cdot 2\) is not prime, so \(\nexists\, x \in \mathbb{Z} - \{-1,0,1\}\) s.t. \(f(x) = 4\).
(c) Is \(f\) a bijection? If it exists, determine \(f^{-1}\). No. \(f^{-1}\) does not exist (d.n.e.).
The two disproofs are both single witnesses, as the templates say they should be. For (b) the witness is any composite number — the range of \(f\) is the primes, and \(\mathbb{Z}^{>1}\) has far more in it.
Worked: reading \(f^{-1}\) off the onto proof
The function \(f : \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) defined by \(f((x,y)) = (y + 1, 2x)\) is both one-to-one and onto (proved in 2026-09-07-functions-one-to-one-onto-inverse). Determine \(f^{-1}\).
The onto half of that proof is the part to use. The candidate it named was \(\left(\frac{b}{2}, a - 1\right)\). That candidate is the inverse:
\[f^{-1} : \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}, \qquad f^{-1}((a,b)) = \left(\tfrac{b}{2}, \; a - 1\right),\]
or, renaming the variables to the usual ones, \(f^{-1}((x,y)) = \left(\frac{y}{2}, \; x - 1\right)\).
Sense check: \(f \circ f^{-1}((x,y)) = (x,y)\) and \(f^{-1} \circ f((x,y)) = (x,y)\). Run one of them: \[f\!\left(f^{-1}((x,y))\right) = f\!\left(\left(\tfrac{y}{2}, x - 1\right)\right) = \left((x - 1) + 1, \; 2 \cdot \tfrac{y}{2}\right) = (x, y). \;\checkmark\]
The method is the one to remember: the onto proof already computes the inverse. Showing \(f\) is onto means, for an arbitrary \((a,b)\), finding the \((x,y)\) that maps to it — and the formula for that \((x,y)\) in terms of \((a,b)\) is \(f^{-1}\). The formula is a function in its own right; one-to-one is what makes it the inverse — it guarantees the candidate is the only preimage, so that \(f^{-1} \circ f\) is the identity as well as \(f \circ f^{-1}\). There is no separate “find the inverse” technique.
Composition of functions
Let \(f : X \to Y\) and \(g : Y \to Z\) be functions. Then the composition of \(f\) and \(g\) is the function \(g \circ f : X \to Z\) defined by the rule \[(g \circ f)(x) = g(f(x)) \quad\text{for all } x \in X.\]
Read \(g \circ f\) right to left: \(f\) acts first, then \(g\). The name is in the “wrong” order because the formula \(g(f(x))\) is.
Two properties pass from \(f\) and \(g\) to the composite:
- \(f\) and \(g\) both onto \(\;\rightarrow\; g \circ f\) is onto
- \(f\) and \(g\) both one-to-one \(\;\rightarrow\; g \circ f\) is one-to-one
\(g \circ f\) has domain equal to the domain of \(f\), which is \(X\), and co-domain equal to the co-domain of \(g\), which is \(Z\). The middle set \(Y\) disappears from the type of the composite.
Figure 1: The composition \(g \circ f\). \(X\) (blue outline) is the domain of \(g \circ f\) because it is the domain of \(f\), and \(Z\) (red outline) is its co-domain because it is the co-domain of \(g\). The middle set \(Y\) is where \(f\) lands and \(g\) starts, and it does not appear in \(g \circ f : X \to Z\) at all.
The converse: from \(g \circ f\) back to \(f\) and \(g\)
Those two facts go one way. The converse asks which of the two ingredients must have a property when the composite has it.
For all functions \(f : X \to Y\) and \(g : Y \to Z\):
- Find a counterexample that disproves: if \(g \circ f\) is onto, then \(f\) is onto.
- Prove that: if \(g \circ f\) is onto, then \(g\) is onto. (Proof by contraposition.)
- Prove that: if \(g \circ f\) is one-to-one, then \(f\) is one-to-one.
- Find a counterexample that disproves: if \(g \circ f\) is one-to-one, then \(g\) is one-to-one.
Statements (1) and (2) have the same hypothesis, if \(g \circ f\) is onto, and two different conclusions, one false and one true. The four results, in one table:
| If \(g \circ f\) is … | then \(f\) is … | then \(g\) is … |
|---|---|---|
| onto | not necessarily — (1) | onto — (2) |
| one-to-one | one-to-one — (3) | not necessarily — (4) |
The property propagates to the function on the same side as the property’s quantifier: onto is about reaching everything in \(Z\), and it is \(g\) that lands in \(Z\); one-to-one is about not merging anything from \(X\), and it is \(f\) that leaves \(X\).
(1) Counterexample
Let \(X = \{a,b\}\), \(Y = \{0,1,2\}\), \(Z = \{v,w\}\). Define \(f : X \to Y\) and \(g : Y \to Z\) by \[f = \{(a,0), (b,1)\}, \qquad g = \{(0,v), (1,w), (2,w)\}.\] \(f\) is not onto (since \(2 \in Y\) but \(\nexists\, x \in X\) s.t. \(f(x) = 2\)). Then \(g \circ f = \{(a,v), (b,w)\}\), which is onto (since \(v \in Z\) and \(g \circ f(a) = v\); \(w \in Z\) and \(g \circ f(b) = w\)).
Figure 2 draws it, with yellow highlights on the elements that matter.
Figure 2: The counterexample for (1). \(f\) misses 2, so \(f\) is not onto; but \(g\) sends 1 and 2 to the same place, so the miss never shows: \(g \circ f\) still reaches both \(v\) and \(w\). The yellow highlights are on \(a\), \(b\), \(0\), \(1\), \(v\), \(w\) — every element the composite actually touches — and 2 is left plain. The function \(g\) has covered for \(f\)’s gap.
(2) Proof
We prove the contrapositive statement: \(\forall\) functions \(f : X \to Y\) and \(g : Y \to Z\), if \(g\) is not onto then \(g \circ f\) is not onto.
Let \(f : X \to Y\) and \(g : Y \to Z\) be functions and suppose \(g\) is not onto. Then \(\exists\, z \in Z\) such that \(z\) is not in the range of \(g\). Thus \(\nexists\, x \in X\) with \(g(f(x)) = z\), i.e. \(z\) is not in the range of \(g \circ f\).
(why? Since if there were such an \(x \in X\) we could take \(y = f(x)\) to give \(g(y) = z\) \((\Rightarrow\Leftarrow)\))
\(\therefore g \circ f\) is not onto. \(\square\)
The contrapositive is the natural shape because not onto hands you a concrete object — a missed \(z\) — to work with, where onto would hand you only a hypothesis about every \(z\). The bracketed why? is a tiny proof by contradiction nested inside: anything \(g \circ f\) reaches, \(g\) reaches too (via \(y = f(x)\)), so a \(z\) that \(g\) misses, \(g \circ f\) misses. Figure 3 shows it: the range of \(g\) is hatched at the top of \(Z\), where \(g\)’s arrow lands, and the lone dot \(z\) sits below it, outside the hatching.
Figure 3: The proof of (2) as a picture. \(g\)’s arrow lands in the hatched region, its range; the dot \(z\) sits outside it. Whatever \(f\) does, \(g \circ f\) can only land where \(g\) lands, so \(z\) is outside the range of \(g \circ f\) too. The mirror of the picture for (3): there a collision in \(f\) survives \(g\), here a gap in \(g\) survives \(f\).
(3) Proof
We prove the contrapositive: \(\forall\) functions \(f : X \to Y\) and \(g : Y \to Z\), if \(f\) is not one-to-one then \(g \circ f\) is not one-to-one.
Let \(f : X \to Y\) and \(g : Y \to Z\) be functions and suppose \(f\) is not one-to-one. Then \(\exists\, x_1, x_2 \in X\) such that \(x_1 \neq x_2\) and \(f(x_1) = f(x_2)\). Hence \[g \circ f(x_1) = g(f(x_1)) = g(f(x_2)) = g \circ f(x_2),\] and since \(x_1 \neq x_2\), \(g \circ f\) is not one-to-one. \(\square\)
Same shape as (2), mirrored. Not one-to-one hands you a concrete collision \(x_1 \neq x_2\), and the collision survives applying \(g\) because \(g\) is a function: equal inputs give equal outputs. Figure 4 shows the collision.
Figure 4: The proof of (3) as a picture. Two different \(x\)’s collide under \(f\) at one \(y\); \(g\) then has only one \(y\) to act on, so it can only send them both to the same \(z\). A collision in \(f\) is a collision in \(g \circ f\), whatever \(g\) does.
(4) Counterexample
Let \(X = \{a,b\}\), \(Y = \{1,2,3\}\), \(Z = \{u,v\}\). Define \(f : X \to Y\) and \(g : Y \to Z\) by \[f = \{(a,1), (b,2)\}, \qquad g = \{(1,u), (2,v), (3,v)\}.\] Then \(g\) is not one-to-one (since \(2 \neq 3\) and \(g(2) = g(3)\)). Now \(g \circ f : X \to Z\) is given by \(\{(a,u), (b,v)\}\), which is one-to-one.
Figure 5: The counterexample for (4). \(g\) merges 2 and 3, so \(g\) is not one-to-one — but \(f\) never sends anything to 3, so the merge is never exercised: \(g \circ f\) sends \(a\) and \(b\) to different places.
The two counterexamples are mirror images and were built the same way. In (1), \(f\) has a gap and \(g\) merges so the gap does not reach \(Z\). In (4), \(g\) merges and \(f\) has a gap so the merge is never fed. In both, the middle set \(Y\) has one more element than it needs — the element that \(f\) misses — and that spare element is where the bad behaviour is parked. Small sets, one thing wrong, the wrong thing hidden: that is how to build a counterexample to order.
See also
- composition-of-functions — the definition, the four converse results as theorems, and how to build the counterexamples
- one-to-one-and-onto-functions · inverse-functions — the properties being composed
- proof-techniques — contraposition, which both proofs use
- 2026-09-07-functions-one-to-one-onto-inverse — Lecture 19
- practice-problems — §26, with full worked solutions