Proofs about Composite Functions

Glue two functions together and inspect the composite with tables and arrows. See what the composite's properties force onto each part.

If the composite is injective, the first function is injective too. If the composite is surjective, the second function is surjective. The converses fail, and the diagrams show why. Undoing a composite also reverses the order.

For example, pack a 📦 box, close the lid, then tie it with string. To open it, the string comes off first. The last step done is the first step undone. That is why inverses of composites reverse the order.

Examples & Exercises

Prove completely that if $g \circ f$ is injective then $f$ is injective.

Then use the scene's injective-chain tables ( $f = [0,1]$ , $g = [0,1,0]$ ) to confirm that this hypothesis guarantees nothing about $g$ itself ( $g(0) = g(2) = 0$ ).

f(a_1) = f(a_2) \;\Rightarrow\; g(f(a_1)) = g(f(a_2)) \;\Rightarrow\; a_1 = a_2

g \circ f = [0, 1] \text{ injective},\quad g(0) = g(2) = 0 \;\Rightarrow\; g \text{ not injective}

injective-chain:

A = [0,1]

B = [0,1,2]

C = [0,1]

f = [0,1]

g = [0,1,0]

, composition

g \circ f = [0,1]

(injective).

f

injective ✓,

g

injective ✗.

Show proof

Assume $f(a_1) = f(a_2)$ .
Applying $g$ to both sides gives $(g \circ f)(a_1) = g(f(a_1)) = g(f(a_2)) = (g \circ f)(a_2)$ .
By hypothesis $g \circ f$ is injective, so $a_1 = a_2$ — hence $f$ is injective.
In the picture: if the composite arrows recover the starting point uniquely, so do the first-stage arrows.
The converse fails: in the scene's tables, $g \circ f = [0,1]$ is injective and $f = [0,1]$ is injective, yet $g = [0,1,0]$ satisfies $g(0) = g(2) = 0$ and is not injective. The later map $g$ may collide freely outside the image of $f$ without affecting the composite's injectivity (here $2 \in B$ lies outside the image of $f$ ).

Prove completely that if $f$ and $g$ are both bijective then $g \circ f$ is bijective and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ , using associativity to show both products are the identity.

Also verify directly on the scene's bijective tables that $g \circ f$ comes out as the identity.

(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = \mathrm{id}

(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = \mathrm{id}

bijective:

A = B = C = [0,1,2]

f = [1,2,0]

g = [2,0,1]

, composition

g \circ f = [g(1), g(2), g(0)] = [0,1,2]

(the identity).

f^{-1} = [2,0,1]

g^{-1} = [1,2,0]

Show proof

First regroup $(f^{-1} \circ g^{-1}) \circ (g \circ f)$ by associativity: $(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f$ . Since $g$ is bijective, $g^{-1} \circ g = \mathrm{id}_{B}$ , and since $f$ is bijective, $f^{-1} \circ \mathrm{id}_{B} \circ f = f^{-1} \circ f = \mathrm{id}_{A}$ — a left inverse.
The other direction is the same: $(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ \mathrm{id}_{B} \circ g^{-1} = \mathrm{id}_{C}$ — a right inverse. Having both a left and a right inverse makes $g \circ f$ bijective with inverse $f^{-1} \circ g^{-1}$ (uniqueness of inverses).
Direct check on the scene's tables: with $f = [1,2,0]$ and $g = [2,0,1]$ , $(g \circ f)(0) = g(f(0)) = g(1) = 0$ , $(g \circ f)(1) = g(2) = 1$ , $(g \circ f)(2) = g(0) = 2$ , so $g \circ f = [0,1,2]$ — the identity. For the inverse tables $f^{-1} = [2,0,1]$ , $g^{-1} = [1,2,0]$ : $(f^{-1} \circ g^{-1})(0) = f^{-1}(g^{-1}(0)) = f^{-1}(1) = 0$ , then $f^{-1}(2) = 1$ at $(1)$ and $f^{-1}(0) = 2$ at $(2)$ — again $[0,1,2]$ , matching $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ as verified by brute force in the model.

Prove completely that if $g \circ f$ is surjective then $g$ is surjective.

Then use the scene's surjective-chain tables ( $f = [0,1]$ , $g = [0,1,0]$ , $B = [0,1,2]$ ) to check why $f$ fails to be surjective (it misses $2$ ) while the composition $g \circ f = [0,1]$ still covers all of $C$ .

c \in C \;\Rightarrow\; \exists a: g(f(a)) = c \;\Rightarrow\; b = f(a) \text{ has } g(b) = c

g \circ f = [0, 1] \text{ surjective onto } C,\quad 2 \notin f(A) \;\Rightarrow\; f \text{ not surjective}

surjective-chain:

A = [0,1]

B = [0,1,2]

C = [0,1]

f = [0,1]

(misses

2

— not surjective),

g = [0,1,0]

(surjective ✓), composition

g \circ f = [0,1]

(surjective ✓).

Show proof

Take any $c \in C$ .
Since $g \circ f$ is surjective, there is $a \in A$ with $g(f(a)) = c$ .
Setting $b = f(a) \in B$ gives $g(b) = g(f(a)) = c$ — so $c$ has a $g$ -preimage, and $g$ is surjective.
In the picture: if the composite arrows hit every point of $C$ , the later arrows must too.
The first map $f$ need not be surjective: in this example $f = [0,1]$ misses the element $2$ of $B$ and is not surjective, yet $g = [0,1,0]$ hits both elements of $C$ via $g(0) = 0$ , $g(1) = 1$ , so the composition $g \circ f = [0,1]$ is surjective. Whatever $g$ does outside the image of $f$ is invisible to the composition (here $g(2) = 0$ ).