Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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!

share|improve this answer
1  
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$.

share|improve this answer
    
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 ? –  André Oct 4 '12 at 21:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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