Tracking Target Values Through Two Functions
Let \(f:A\to B\) and \(g:B\to C\). The composition \(g\circ f:A\to C\) applies \(f\) first and then applies \(g\), so $$ (g\circ f)(x)=g(f(x)) \qquad (x\in A). $$ A function from \(A\) to \(C\) is surjective when every element of \(C\) is the output of the function at some input in \(A\). Thus, to test whether \(g\circ f\) is surjective, begin with an arbitrary target \(c\in C\) and ask whether there is an \(x\in A\) such that \(g(f(x))=c\).
The earlier tutorial “Composition of Functions” established that if both functions are surjective, then their composition is surjective. That gives a useful sufficient condition. But it is not the only way a composite can be surjective: \(f\) may fail to reach some elements of \(B\), provided it still reaches enough inputs for \(g\) to produce every element of \(C\).
For \(c\in C\), the fiber of \(g\) over \(c\) is the set of inputs in \(B\) that \(g\) maps to \(c\). In terms of the preimage notation introduced earlier, this fiber is $$ g^{-1}[\{c\}]=\{b\in B:g(b)=c\}. $$ Here \(g^{-1}[\{c\}]\) denotes a preimage of a set; it does not assume that \(g\) has an inverse function.
The Exact Fiber Criterion
The target \(c\) is attained by the composite precisely when at least one input in the fiber of \(g\) over \(c\) is itself attained by \(f\). This observation gives an exact characterization, rather than just a sufficient condition.
Theorem (Surjectivity Criterion for a Composite). Let \(f:A\to B\) and \(g:B\to C\). Then \(g\circ f\) is surjective if and only if, for every \(c\in C\), $$ \operatorname{ran}(f)\cap g^{-1}[\{c\}]\ne\varnothing. $$ Equivalently, every fiber of \(g\) over an element of \(C\) contains at least one value in \(\operatorname{ran}(f)\).
Proof. First suppose \(g\circ f\) is surjective. Let \(c\in C\) be arbitrary. By surjectivity, there is an \(x\in A\) such that $$ (g\circ f)(x)=c. $$ By the definition of composition, \(g(f(x))=c\). The value \(f(x)\) belongs to \(\operatorname{ran}(f)\), and the equality \(g(f(x))=c\) means \(f(x)\in g^{-1}[\{c\}]\). Therefore $$ f(x)\in\operatorname{ran}(f)\cap g^{-1}[\{c\}], $$ so this intersection is nonempty. Since \(c\) was arbitrary, the condition holds for every \(c\in C\).
Conversely, suppose that for every \(c\in C\), the set \(\operatorname{ran}(f)\cap g^{-1}[\{c\}]\) is nonempty. Let \(c\in C\) be arbitrary. Choose \(b\) in this intersection. Since \(b\in\operatorname{ran}(f)\), there exists \(x\in A\) with \(f(x)=b\). Since \(b\in g^{-1}[\{c\}]\), we also have \(g(b)=c\). Consequently, $$ (g\circ f)(x)=g(f(x))=g(b)=c. $$ Thus every \(c\in C\) is attained by \(g\circ f\), so \(g\circ f\) is surjective. \(\square\)
The proof follows the definition in both directions: a preimage \(x\) for the composite produces an attained intermediate value in the appropriate fiber, and an attained intermediate value in that fiber produces a preimage for the composite. This also handles the case \(C=\varnothing\): the condition over all \(c\in C\) is vacuous, and a function with empty codomain is surjective by definition.
Worked Example: Surjective Composite Without a Surjective First Function
Let \(A=\{1,2\}\), \(B=\{a,b,c\}\), and \(C=\{0,1\}\). Define \(f:A\to B\) and \(g:B\to C\) by $$ f(1)=a,\qquad f(2)=b, $$ and $$ g(a)=0,\qquad g(b)=1,\qquad g(c)=1. $$ The range of \(f\) is \(\{a,b\}\), so \(f\) is not surjective onto \(B\), since \(c\notin\operatorname{ran}(f)\). Nevertheless, the fiber of \(g\) over \(0\) contains \(a\), and the fiber over \(1\) contains \(b\). Both values lie in \(\operatorname{ran}(f)\). Explicitly, $$ (g\circ f)(1)=g(a)=0,\qquad (g\circ f)(2)=g(b)=1. $$ The composite is therefore surjective onto \(C\). The first function does not have to reach every element of \(B\); it must reach at least one input of \(g\) for each target in \(C\).
What Surjectivity of the Composite Forces
The fiber criterion also shows that if \(g\circ f\) is surjective, then \(g\) must be surjective. Indeed, for every \(c\in C\), the criterion supplies a \(b\in B\) with \(g(b)=c\). This is consistent with the earlier result “Surjective Precomposition Preserves the Range”: precomposing \(g\) with a surjective \(f\) leaves the range of \(g\) unchanged. The composite being surjective is stronger than merely knowing that \(g\) is surjective, however. It requires that the values \(f\) actually reaches include an input from every fiber of \(g\).
Worked Example: A Surjective Second Function Is Not Enough
Let \(A=\{1\}\), \(B=\{u,v\}\), and \(C=\{0,1\}\). Define $$ f(1)=u,\qquad g(u)=0,\qquad g(v)=1. $$ The function \(g:B\to C\) is surjective because it reaches both \(0\) and \(1\). But \(\operatorname{ran}(f)=\{u\}\), and this range does not meet the fiber \(g^{-1}[\{1\}]=\{v\}\). The composite has only one input value: $$ (g\circ f)(1)=g(u)=0. $$ Hence \(g\circ f\) is not surjective onto \(C\). Surjectivity of \(g\) guarantees that its fibers are nonempty; it does not guarantee that \(f\) reaches those fibers.
In the other direction, if \(f\) is surjective onto \(B\), then every input of \(g\) is available as an intermediate value. The earlier proposition “Surjective Precomposition Preserves the Range” gives $$ \operatorname{ran}(g\circ f)=\operatorname{ran}(g). $$ Thus, when \(f\) is surjective, the composite is surjective exactly when \(g\) is surjective. Without surjectivity of \(f\), the full range of \(g\) may include outputs that the composite cannot attain.
| Information available | What it tells us about \(g\circ f\) |
|---|---|
| \(f\) and \(g\) are both surjective | The composite is surjective, by the earlier Composition of Surjective Functions result. |
| \(g\circ f\) is surjective | \(g\) is surjective, and \(\operatorname{ran}(f)\) meets every fiber of \(g\). |
| \(g\) is surjective | This alone does not guarantee that the composite is surjective. |
| \(f\) is not surjective | The composite may still be surjective if the attained values meet every fiber of \(g\). |
When the Second Function Is Injective
There is a useful special case in which the first function must be surjective. If \(g\) is injective, it cannot send two different intermediate values to the same target. Therefore, for the composite to reach every target produced by \(g\), the first function must reach every possible input of \(g\).
Theorem (Surjectivity Through an Injective Second Function). Let \(f:A\to B\) and \(g:B\to C\), and suppose \(g\) is injective. If \(g\circ f\) is surjective, then \(f\) is surjective.
Proof. Let \(b\in B\) be arbitrary. We will show that \(b\in\operatorname{ran}(f)\). Since \(g(b)\in C\) and \(g\circ f\) is surjective onto \(C\), there exists \(x\in A\) such that $$ (g\circ f)(x)=g(b). $$ By the definition of composition, this gives $$ g(f(x))=g(b). $$ Both \(f(x)\) and \(b\) belong to \(B\). Since \(g\) is injective, equality of their \(g\)-values implies \(f(x)=b\). Thus \(b\) is in the range of \(f\). As \(b\) was arbitrary, every element of \(B\) belongs to \(\operatorname{ran}(f)\), and \(f\) is surjective. \(\square\)
This conclusion does not assert that \(g\) is surjective onto all of \(C\); an injective function \(g:B\to C\) need not reach every element of \(C\). Rather, surjectivity of the composite says that \(g\) does reach all of \(C\), and the proof uses injectivity to show that every \(b\in B\) must already be reached by \(f\).
Worked Example: Injectivity Prevents Skipping Intermediate Inputs
Let \(B=\{r,s\}\), \(C=\{0,1\}\), and define \(g:B\to C\) by \(g(r)=0\) and \(g(s)=1\). This \(g\) is injective. If \(f:A\to B\) has range \(\{r\}\), then every composite output equals $$ g(r)=0. $$ So \(g\circ f\) cannot be surjective onto \(C\), because it never outputs \(1\). More generally, the theorem proves that any \(f\) for which \(g\circ f\) is surjective must reach both \(r\) and \(s\), and hence must be surjective onto \(B\). The distinct outputs of \(g\) make each target correspond to exactly one intermediate input.
A Reliable Proof Strategy
When proving that \(g\circ f\) is surjective, start with an arbitrary element \(c\) of the final codomain \(C\). The goal is to construct an \(x\in A\) for which \(g(f(x))=c\). It is often helpful to separate this into two tasks: find an intermediate value \(b\in B\) with \(g(b)=c\), and then find an input \(x\in A\) with \(f(x)=b\). The fiber criterion states exactly when those tasks can both be completed.
A common mistake is to conclude that surjectivity of \(g\) alone makes \(g\circ f\) surjective. That conclusion overlooks the intermediate step: even if \(g\) has an input mapping to each target, the first function may not reach those inputs. Another mistake is to insist that \(f\) must be surjective onto \(B\). That condition guarantees enough intermediate values, but it can be stronger than needed; the exact requirement is that \(\operatorname{ran}(f)\) meet every fiber of \(g\).
Check Your Understanding
- State the Surjectivity Criterion for a Composite using \(\operatorname{ran}(f)\) and the fibers of \(g\).
- Why does surjectivity of \(g\circ f\) imply that \(g\) is surjective?
- Can \(g\circ f\) be surjective even if \(f\) is not surjective onto \(B\)? What must be true of \(\operatorname{ran}(f)\)?
- If \(g\) is surjective, is \(g\circ f\) necessarily surjective? Explain which additional condition is needed.
- Suppose \(g\) is injective and \(g\circ f\) is surjective. What can be concluded about \(f\), and where is injectivity used?