I'm trying to prove that composition of injections is an injection. I want to know if this is a good proof:

Composition of injections is an injection.

Let $f:S_1\rightarrow S_2$ and $g:S_2\rightarrow S_3$ be injections by the definitions:

$1.~\forall x_1, x_2:x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)\\2.~\forall y_1, y_2:y_1\ne y_2\Rightarrow g(y_1)\ne g(y_2)$

then composition $g\circ f(x)$ is an injection.

We have to prove:

$\forall x_1, x_2:x_1\ne x_2\Rightarrow g\circ f(x_1)\ne g\circ f(x_2)$.

Let $x_1, x_2\in S_1$ and $x_1\ne x_2$, then by the first definition of injectivity of $f$, $f(x_1)\ne f(x_2)$. Let $f(x_1)=y_1$ and $f(x_2)=y_2$. It follows that $y_1\ne y_2$. Then by the second definition of injectivity of $g$, $g(y_1)\ne g(y_2)$.

Equations imply:$$g(y_1)\ne g(y_2)\\g[f(x_1)]\ne g[f(x_2)]\\g\circ f(x_1)\ne g\circ f(x_2).$$ Since we started with general $x_1$ and $x_2$ this is proved.

Or without the introduction of $y_1$ and $y_2$, so just "... By the second definition of injectivity: $f(x_1)\ne f(x_2)$ then $g[f(x_1)]\ne g[f(x_2)]$. Therefore $x_1\ne x_2$ imply $g\circ f(x_1)\ne g\circ f(x_2)$."


Looks great. Adding in the $y_1$ and $y_2$ is extraneous, and some people would leave that out of the proof.

  • $\begingroup$ Would it still be correct if I included that on my exam? $\endgroup$ – zoid Jul 19 '14 at 17:10
  • $\begingroup$ That's difficult to answer. I cannot say what your instructor will or will not accept. However, it is very clear and straightforward, so my thinking is that it would do well. $\endgroup$ – Andrew Jul 19 '14 at 17:11

It's good, but proving injectivity is often easier with the contrapositive:

if $f(x_1)=f(x_2)$, then $x_1=x_2$.

So, assume $f$ and $g$ are injective and suppose $$ g\circ f(x_1)=g\circ f(x_2). $$ This means $$ g(f(x_1))=g(f(x_2)) $$ that, by the injectivity of $g$, implies $$ f(x_1)=f(x_2). $$ Injectivity of $f$ allows us to argue that $$ x_1=x_2. $$

As you clearly see, these are the same steps as in your proof; but dealing with equality is psychologically easier than dealing with inequalities.


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.