Let $A$ and $B$ be non-empty sets, and let $f\,:\,A\rightarrow B$ be a function.

$ \color{darkred}{\bf Theorem}$: The function $f$ is injective if and only if $f\circ g=f\circ h$ implies $g=h$ for all functions $g,h:\,Y\rightarrow A$ for all sets Y. ($f\,:\,A\, \rightarrowtail \,B$, $f$ is a monomorphism)

I want to prove this ${\bf {\it theorem}}$, but I get stuck.

$\color{darkred}{\bf proof\,\,}$:

$\Rightarrow$) Assume that $f$ is injective. Let $g,h:\,Y\rightarrow A$ be functions such that $f\circ g(y)=f\circ h(y),\,\,\,\,\,\,y\in Y$ it follows that $f(g(y))=f(h(y))$, and $f$ is injective, therefore $g(y)=h(y)$ for every $y\in Y$.

$\Leftarrow$) and here I get stuck, can’t figure out how to prove this.

Can someone help me with this proof?

  • $\begingroup$ I tried giving a meaningful title, but I didn't have any great idea... feel free to improve it! $\endgroup$ – Asaf Karagila Oct 4 '12 at 21:06
  • $\begingroup$ This is much better than "function composition", thank you! $\endgroup$ – evodam Oct 4 '12 at 21:09
  • $\begingroup$ In algebra they call these types of function monomorphic or monos. So maybe a title like "How to prove that monos are injective and vice versa" or something could also fit. $\endgroup$ – Apostolos Oct 4 '12 at 22:10
  • $\begingroup$ @Apostolos Thank you very much! Monomorphic functions are exactly what I was looking for. $\endgroup$ – evodam Oct 4 '12 at 22:56
  • $\begingroup$ The new title suggests that you have a syringe infected with mono and you want to inject it to someone! Help! :-) $\endgroup$ – Asaf Karagila Oct 4 '12 at 22:59

There is a simple way to prove this by contrapositive.

Assume the function is not injective, and find a counterexample. To find it use the fact that there are $u,w\in A$ such that $f(u)=f(w)$ and create two functions which behave differently on those values.

Define $h_u,h_w\colon\{\bullet\}\to A$ such that $h_u(\bullet)=u$ and $h_v(\bullet)=v$. Since $f(u)=f(v)$ we have that $f\circ h_u=f\circ h_v$ but $h_u\neq h_v$.
Bonus point: use this method to prove this directly and not by contrapositive!

  • 1
    $\begingroup$ Double bonus point: Prove this without using the law of excluded middle! $\endgroup$ – Zhen Lin Oct 4 '12 at 23:00
  • 1
    $\begingroup$ @Zhen: That is what I meant by a direct proof without contrapositive. I did not know that direct proofs use the law of excluded middle... $\endgroup$ – Asaf Karagila Oct 4 '12 at 23:01
  • $\begingroup$ Sorry, I was thinking of the right cancellation property and surjectivity, which has to be phrased in just the right way to avoid assuming the law of excluded middle. $\endgroup$ – Zhen Lin Oct 4 '12 at 23:08
  • $\begingroup$ @Zhen: That reminds another question of this vein which I have answered a few months ago (somewhere in May), regarding a similar property for surjective functions. $\endgroup$ – Asaf Karagila Oct 4 '12 at 23:14

assume $f(a) = f(b)$ with $a \neq b$. Then define $g,h: A \rightarrow A$ with $g(x) := b$ as $x=a$ and $g(x) := a$ as $x = b$ and $x$ else. Take for $h:= Id_A$. Then we have $f\circ g =f \circ h$ but $f \neq h$.

  • $\begingroup$ we also got $f \circ h = f \circ g$ if we take $f,g:= Id_A$. Then with $f(a) = f(b)$ we would have $f(g(a)) = f(h(b))$ such that $g(a) = h(b)$ and thus $a = b$. Am i right here ? $\endgroup$ – user42761 Oct 4 '12 at 21:17

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.