# How to prove that monos are injective?

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?

-
I tried giving a meaningful title, but I didn't have any great idea... feel free to improve it! –  Asaf Karagila Oct 4 '12 at 21:06
This is much better than "function composition", thank you! –  M. L. Oct 4 '12 at 21:09
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. –  Apostolos Oct 4 '12 at 22:10
@Apostolos Thank you very much! Monomorphic functions are exactly what I was looking for. –  M. L. Oct 4 '12 at 22:56
The new title suggests that you have a syringe infected with mono and you want to inject it to someone! Help! :-) –  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!

-
Double bonus point: Prove this without using the law of excluded middle! –  Zhen Lin Oct 4 '12 at 23:00
@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... –  Asaf Karagila Oct 4 '12 at 23:01
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. –  Zhen Lin Oct 4 '12 at 23:08
@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. –  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$.

-
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 ? –  Andre Oct 4 '12 at 21:17