1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ No it does not imply $g$ is injective, because that would require the statement $g(x') = g(y')$. What you have is that $f(x')=f(y') = z$ and then $g(z)=g(z)$ is a tautology. $\endgroup$ – Chris Gerig Dec 21 '16 at 20:53
  • $\begingroup$ Because there are counterexamples. $\endgroup$ – Michael Hoppe Dec 21 '16 at 20:55
1
$\begingroup$

Let $X=\{0\}$, $Y=\{1,2\}$ and $Z=\{3\}$. Define \begin{align} f\colon X&\to Y, & f(0)&=1,\\ g\colon Y&\to Z, & g(1)&=g(2)=3 \end{align} Then $g\circ f$ is injective, but $g$ is not.

Thus there's no way to prove that $g\circ f$ injective implies $g$ injective.


Your proof is good, but has some redundant parts.

Suppose $g\circ f$ is injective and that $f(x)=f(y)$; then $g\circ f(x)=g\circ f(y)$ and, by injectivity of $g\circ f$, we conclude $x=y$. Therefore $f$ is injective.

There's nothing more to prove.

But, as you see from the example, $g$ need not be injective: you just use the obvious fact that, if $a=b$, then $g(a)=g(b)$. In this case $a=f(x)$ and $b=f(y)$, which are equal by assumption.

$\endgroup$
  • $\begingroup$ Thanks. Any input regarding the rest of the question? $\endgroup$ – BenL Dec 21 '16 at 20:53
  • 1
    $\begingroup$ @BenL I added some comments $\endgroup$ – egreg Dec 21 '16 at 20:58
1
$\begingroup$

First you don't have to assume $g\circ f$ is injective because it is not stated that $g\circ f$ is injective if and only if $f$ is. What is stated is ‘only if’.

Second, if $f$ is not injective: you prove that $g\circ f$ cannot possibly be injective. This is not a proof by contradiction, but a proof by contrapositive (the assertion $A\implies B$ is logically equivalent to the assertion $\neg B\implies \neg A$).

$\endgroup$
  • $\begingroup$ No; the statement of the theorem in my text (And in my professor's notes) is "Show that if $g \circ f $ is injective then so is $f$. I'm also not clear how this isn't proof by contradiction. I suppose the opposite is true; then show that this assumption leads to a contradiction of my initial assumptions. That seems like proof by contradiction to me. Could you elaborate? $\endgroup$ – BenL Dec 21 '16 at 20:56
  • $\begingroup$ ‘No’ what? I explained you proved this in the second part by proving that if $f$ is not injective ($\neg B$), then $g\circ f$ is not ($\neg A$). In other words you proved $\neg B\implies\neg A$, which is equivalent to $A\implies B$). $\endgroup$ – Bernard Dec 21 '16 at 21:02
  • $\begingroup$ "No" as in you misread or misunderstood the statement I was trying to prove. I was proving injectivty of $f$ as an implication of injectivty of $g \circ f$. That is different from an 'only if' statement, and it makes perfect sense in such a case to start out assuming the conditional statement is true. $\endgroup$ – BenL Dec 21 '16 at 21:05
  • $\begingroup$ But only if (̓$\Rightarrow$) means precisely that, as opposed to if ($\Leftarrow$). $\endgroup$ – Bernard Dec 21 '16 at 21:10
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.