Suppose \(f\) and \(g\) are injective maps of a set \(S\) into itself. Show that the composite function \(f\circ g\) is also injective.
Solution
Lemma: \(f\) is injective \(\iff f\) has a left inverse \(\inverseof{f}\) satisfying \(\inverseof{f} f(a) = a\).
Suppose \(f,g: A \to A\) are injective and \(x,y \in A\), we want to show that \((f\circ g)(x) = (f\circ g)(y) \implies x = y\). So suppose \(f(g(x)) = f(g(y))\). Since \(f\) is injective, \(f\) has a left inverse, so \(g(x) = g(y)\), and since \(g\) is injective \(x = y\). \(\qed\)
Solution
Goal: Prove that if \(A\) is a set and \(f, g: A \to A\) are injective functions, then their composition \(f \circ g: A \to A\) is injective.
1. Definition: A function \(h: A \to A\) is injective if for all \(x, y \in A\), \(h(x) = h(y) \implies x = y\).
By the standard definition of injectivity.
2. Assume \(f: A \to A\) and \(g: A \to A\) are injective functions.Let \(x, y \in A\) and assume \((f \circ g)(x) = (f \circ g)(y)\).
By setting up the hypothesis of the implication in 1 for \(h = f \circ g\).
3. \(f(g(x)) = f(g(y))\).
By definition of function composition, \((f \circ g)(x) = f(g(x))\) and \((f \circ g)(y) = f(g(y))\), so this follows from 2.
4. \(g(x) = g(y)\).
By 2, \(f\) is injective.
Applying the definition of injectivity to the elements \(g(x), g(y) \in A\) with \(f(g(x)) = f(g(y))\) from 3 yields \(g(x) = g(y)\).
5. \(x = y\).
By 2, \(g\) is injective.
Applying the definition of injectivity to \(x, y \in A\) with \(g(x) = g(y)\) from 4 yields \(x = y\).
6. Conclusion: \(f \circ g\) is injective.
We showed in <1>2–<1>5 that for all \(x, y \in A\), \((f \circ g)(x) = (f \circ g)(y) \implies x = y\).
By 1, \(f \circ g\) is injective. Q.E.D.