I'm trying to prove that if $g \circ f$ is injective, then f must also be injective. I have written a proof, which I believe has a bad step in it, and I would like feedback.
Assume $g \circ f$ is injective. Now suppose $g\circ f(x) = g\circ f(y)$ for some $x, y$ in the domain of $f$ (call it $X$). Because the composition is injective, $x = y$.
Now suppose $f$ were not injective. Then for some $x', y' \in X, ~f(x') = f(y')$ but $x' \neq y'$. Thus $g \circ f(x') = g \circ f(y')$ but $y' \ne x'$ This implies $g \circ f$ is not injective, which is a contradiction. Therefore $f$ must be injective. $\Box $
This seems spurious to me, because it implies that $g$ itself needs to be injective (I feel but cannot state rigorously that this is implicit in the step that derives the contradiction) and I know that $g$ need not be injective itself (though again, I know this heuristically and cannot think of an example).
Here is another question that is identical (Composition of functions injective implies one of them is injective?) but it seems like the same assumption is being made; which is that the fact that $~f(x') = f(y') \Rightarrow g \circ f(x') = g \circ f(y')$ and that this contradicts the injectivity of $g$ as $x' \ne y'$
Can anyone help clarify my thinking here?
Best Answer
Think of an injective function as one that preserves difference. If $f$ collapses two points into each other, so that $f(a)=f(b)$, then there is no way for $g$ to unentangle them; $g\circ f$ must also collapse $a$ and $b$.
But $g\circ f$ can still be injective even if $g$ collapses points as long as it doesn't collapse points in the range of $f$. For example, suppose that $g(u)=g(v)$, but there is no solution to $f(x)=u$. Then the fact that $g$ fails to distinguish between $u$ and $v$ is not important for the function $g\circ f$, since the point $u$ is irrelevant.
For a concrete example, suppose that $f$ maps a set of children to the month of their birth, and $g$ maps each month to the number of days in the month. Then $f$ will be injective as long as no two children have the same birth month. $g$ is clearly not injective, as $g(\textrm{January})=g(\textrm{March})=31$. But $g\circ f$ might be injective, depending on the set of children. If there are only three children, Alice, Bob, and Cathy (born in January, February, and April respectively), then $g\circ f$ will be injective.
Formally, if $f:X\to $ and $g:Y\to Z$, then $g\circ f$ will be injective if and only if $f$ and $g\vert_{R(f)}$ are injective, where $R(f)\subseteq Y$ is the range of $f$.