Proofs about Composite Functions

Proofs about composite functions, tested on concrete tables: g∘fg \circ f injective forces ff injective, g∘fg \circ f surjective forces gg surjective — and the arrow diagrams show exactly why the converses fail (gg need not be injective, ff need not be surjective). For bijections, (g∘f)−1=f−1∘g−1(g \circ f)^{-1} = f^{-1} \circ g^{-1} is computed out loud.

f(a1)=f(a2)  ⟹  g(f(a1))=g(f(a2))f(a_1) = f(a_2) \implies g(f(a_1)) = g(f(a_2))
(g∘f)−1=f−1∘g−1(g \circ f)^{-1} = f^{-1} \circ g^{-1}

Examples & Exercises

Prove completely that if g∘fg \circ f is injective then ff is injective. Then use the scene's injective-chain tables (f=[0,1]f = [0,1], g=[0,1,0]g = [0,1,0]) to confirm that this hypothesis guarantees nothing about gg itself (g(0)=g(2)=0g(0) = g(2) = 0).

f(a1)=f(a2)  ⇒  g(f(a1))=g(f(a2))  ⇒  a1=a2f(a_1) = f(a_2) \;\Rightarrow\; g(f(a_1)) = g(f(a_2)) \;\Rightarrow\; a_1 = a_2
g∘f=[0,1] injective,g(0)=g(2)=0  ⇒  g not injectiveg \circ f = [0, 1] \text{ injective},\quad g(0) = g(2) = 0 \;\Rightarrow\; g \text{ not injective}
injective-chain: A=[0,1]A = [0,1], B=[0,1,2]B = [0,1,2], C=[0,1]C = [0,1], f=[0,1]f = [0,1], g=[0,1,0]g = [0,1,0], composition g∘f=[0,1]g \circ f = [0,1] (injective). ff injective ✓, gg injective ✗.
Show proof
  1. Assume f(a1)=f(a2)f(a_1) = f(a_2). Applying gg to both sides gives (g∘f)(a1)=g(f(a1))=g(f(a2))=(g∘f)(a2)(g \circ f)(a_1) = g(f(a_1)) = g(f(a_2)) = (g \circ f)(a_2). By hypothesis g∘fg \circ f is injective, so a1=a2a_1 = a_2 — hence ff is injective. In the picture: if the composite arrows recover the starting point uniquely, so do the first-stage arrows.
  2. The converse fails: in the scene's tables, g∘f=[0,1]g \circ f = [0,1] is injective and f=[0,1]f = [0,1] is injective, yet g=[0,1,0]g = [0,1,0] satisfies g(0)=g(2)=0g(0) = g(2) = 0 and is not injective. The later map gg may collide freely outside the image of ff without affecting the composite's injectivity (here 2∈B2 \in B lies outside the image of ff).

Prove completely that if ff and gg are both bijective then g∘fg \circ f is bijective and (g∘f)−1=f−1∘g−1(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∘fg \circ f comes out as the identity.

(f−1∘g−1)∘(g∘f)=f−1∘(g−1∘g)∘f=id(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = \mathrm{id}
(g∘f)∘(f−1∘g−1)=g∘(f∘f−1)∘g−1=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]A = B = C = [0,1,2], f=[1,2,0]f = [1,2,0], g=[2,0,1]g = [2,0,1], composition g∘f=[g(1),g(2),g(0)]=[0,1,2]g \circ f = [g(1), g(2), g(0)] = [0,1,2] (the identity). f−1=[2,0,1]f^{-1} = [2,0,1], g−1=[1,2,0]g^{-1} = [1,2,0].
Show proof
  1. First regroup (f−1∘g−1)∘(g∘f)(f^{-1} \circ g^{-1}) \circ (g \circ f) by associativity: (f−1∘g−1)∘(g∘f)=f−1∘(g−1∘g)∘f(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f. Since gg is bijective, g−1∘g=idBg^{-1} \circ g = \mathrm{id}_{B}, and since ff is bijective, f−1∘idB∘f=f−1∘f=idAf^{-1} \circ \mathrm{id}_{B} \circ f = f^{-1} \circ f = \mathrm{id}_{A} — a left inverse.
  2. The other direction is the same: (g∘f)∘(f−1∘g−1)=g∘(f∘f−1)∘g−1=g∘idB∘g−1=idC(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∘fg \circ f bijective with inverse f−1∘g−1f^{-1} \circ g^{-1} (uniqueness of inverses).
  3. Direct check on the scene's tables: with f=[1,2,0]f = [1,2,0] and g=[2,0,1]g = [2,0,1], (g∘f)(0)=g(f(0))=g(1)=0(g \circ f)(0) = g(f(0)) = g(1) = 0, (g∘f)(1)=g(2)=1(g \circ f)(1) = g(2) = 1, (g∘f)(2)=g(0)=2(g \circ f)(2) = g(0) = 2, so g∘f=[0,1,2]g \circ f = [0,1,2] — the identity. For the inverse tables f−1=[2,0,1]f^{-1} = [2,0,1], g−1=[1,2,0]g^{-1} = [1,2,0]: (f−1∘g−1)(0)=f−1(g−1(0))=f−1(1)=0(f^{-1} \circ g^{-1})(0) = f^{-1}(g^{-1}(0)) = f^{-1}(1) = 0, then f−1(2)=1f^{-1}(2) = 1 at (1)(1) and f−1(0)=2f^{-1}(0) = 2 at (2)(2) — again [0,1,2][0,1,2], matching (g∘f)−1=f−1∘g−1(g \circ f)^{-1} = f^{-1} \circ g^{-1} as verified by brute force in the model.

Prove completely that if g∘fg \circ f is surjective then gg is surjective. Then use the scene's surjective-chain tables (f=[0,1]f = [0,1], g=[0,1,0]g = [0,1,0], B=[0,1,2]B = [0,1,2]) to check why ff fails to be surjective (it misses 22) while the composition g∘f=[0,1]g \circ f = [0,1] still covers all of CC.

c∈C  ⇒  ∃a:g(f(a))=c  ⇒  b=f(a) has g(b)=cc \in C \;\Rightarrow\; \exists a: g(f(a)) = c \;\Rightarrow\; b = f(a) \text{ has } g(b) = c
g∘f=[0,1] surjective onto C,2∉f(A)  ⇒  f not surjectiveg \circ f = [0, 1] \text{ surjective onto } C,\quad 2 \notin f(A) \;\Rightarrow\; f \text{ not surjective}
surjective-chain: A=[0,1]A = [0,1], B=[0,1,2]B = [0,1,2], C=[0,1]C = [0,1], f=[0,1]f = [0,1] (misses 22 — not surjective), g=[0,1,0]g = [0,1,0] (surjective ✓), composition g∘f=[0,1]g \circ f = [0,1] (surjective ✓).
Show proof
  1. Take any c∈Cc \in C. Since g∘fg \circ f is surjective, there is a∈Aa \in A with g(f(a))=cg(f(a)) = c. Setting b=f(a)∈Bb = f(a) \in B gives g(b)=g(f(a))=cg(b) = g(f(a)) = c — so cc has a gg-preimage, and gg is surjective. In the picture: if the composite arrows hit every point of CC, the later arrows must too.
  2. The first map ff need not be surjective: in this example f=[0,1]f = [0,1] misses the element 22 of BB and is not surjective, yet g=[0,1,0]g = [0,1,0] hits both elements of CC via g(0)=0g(0) = 0, g(1)=1g(1) = 1, so the composition g∘f=[0,1]g \circ f = [0,1] is surjective. Whatever gg does outside the image of ff is invisible to the composition (here g(2)=0g(2) = 0).

1. Foundations of Proof