Suppose \(f, g: A \to A\) are functions with \(f \circ g\) injective.
Prove that \(g\) must be injective.
Give an example to show that \(f\) need not be injective.
Solution
Part (a).
1. \(g\) is injective.
1.1. Suppose \(g(x) = g(y)\) for \(x, y \in A\).
take two elements with equal image under \(g\).
1.2. Then \((f \circ g)(x) = f(g(x)) = f(g(y)) = (f \circ g)(y)\).
apply \(f\) to both sides of \(g(x) = g(y)\).
1.3. Since \(f \circ g\) is injective, \(x = y\).
injectivity of \(f \circ g\) applied to 2.
1.4. Hence \(g(x) = g(y)\) implies \(x = y\), so \(g\) is injective.
<2>1–<2>3.
Part (b).
1. Take \(A = \NN\) (or any set with at least two elements), and define \(g(n) = 2n\) and \(f(n) = \lfloor n/2 \rfloor\).
1.1. \(g\) is injective.
\(2n = 2m\) implies \(n = m\).
1.2. \(f \circ g = \id_{\NN}\).
\((f \circ g)(n) = f(2n) = \lfloor 2n/2 \rfloor = n\).
1.3. Hence \(f \circ g\) is injective.
the identity is injective.
1.4. But \(f\) is not injective.
\(f(0) = 0\) and \(f(1) = 0\), yet \(0 \neq 1\).
2. Q.E.D.
1 gives an example where \(f \circ g\) is injective but \(f\) is not.