7
$\begingroup$

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?

  • 0
    @AsafKaragila Next time I'll use your title ;)2012-10-04

2 Answers 2

5

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!

  • 0
    @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.2012-10-04
1

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

  • 0
    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 ?2012-10-04