Injective functions and composition I'm trying to prove that a function $f \in A \to B $ is injective if and only if for all $C$, for all $g,h \in C \to A$: $f \circ g = f \circ h \to g = h$.
The $\to$ direction is proved as follows:
[$\to$]
Let $f$ be injective and suppose that $f \circ g = f \circ h$. It follows that $f(g(a)) = f(h(a))$ for any $a \in A$, whence, for all $a \in A: h(a) = g(a)$, by injectivity.
I cannot however derive the $\leftarrow$, by
Suppose for all $g,h \in C \to A$: $f \circ g = f \circ h \to g = h$ and that $f(a) = f(b)$ and, for contradiction, that $a \neq b$. It is not clear to me how to get the information that $a = b$ from these assumptions.
Can anyone help here?
 A: Since the condition says that if something happens for all choice of functions, then $f$ in one-to-one, the usual strategy is to find a clever/suitable choice of functions that will imply what you want. That is the situation here.
For the converse, suppose there exist $a,b\in A$ such that $f(a)=f(b)$. We want to show that $a=b$.
Let $C=\{x\}$ be a one element set. Define $g\colon C\to A$ by $g(x)=a$, and $h\colon C\to B$ by $h(x)=b$.
Note that $f\circ g = f\circ h$, since $f(a)=f(b)$. Now, our assumption is that this implies that $g=h$. So we conclude that $g=h$. Therefore, $a=g(x)=h(x)=b$, which proves that $a=b$, as desired.

I like that proof, but you can also proceed by contrapositive: prove that if $f$ is not injective, then there exist a choice of $C$ and $g,h\colon C\to A$ such that $f\circ g = f\circ h$, yet $g\neq h$.
If there exist $a,b\in A$ such that $a\neq b$ but $f(a)=f(b)$, then pick your favorite nonempty set $C$, and define $g\colon C\to A$ to be $g(c)=a$ for all $c$; and $h\colon C\to A$ to be $h(c)=b$ for all $c$. Then $f\circ g=f\circ h$, since $f(a)=f(b)$, but $g\neq h$ since $g(c)=a\neq b = h(c)$ for any $c\in C$ (which is nonempty).
A: Given that for all $C$ and $g,h : C \to A,$ we have $f \circ g = f \circ h \to g = h,$ we want to prove that for all $a, b \in A,$ $f(a) = f(b) \to a = b.$
Suppose we selected some arbitrary $a$ and $b$ from $A.$ Now, define functions $s: C\to A, s(c) = a$ and $t: C \to A, t(c) = b.$
Our premise that $f \circ g = f\circ h \to g = h$ applies to all functions $C \to A,$ so it must work for $s$ and $t.$ Therefore, $f \circ s = f \circ t \to s = t.$ Plugging in our values gives $f(a) = f(b) \to a = b,$ which was our objective.
Now, because this argument assumed nothing about $a$ and $b$ except that they were arbitrary elements of $A,$ this argument holds for all elements of $A.$ So, for all $a,b \in A,$ we've proven that $f(a) = f(b) \to a = b.$
