Let $f:A \rightarrow B$ be a map of sets. Prove that $f$ is injective if and only if given any set $C$ and any two set map $g_i:C \rightarrow A, i =1,2$, with compositions $f \circ g_1 = f \circ g_2$, then $g_1 = g_2$.

So I have proved the forward direction, which was quite easy. For the other direction, I am unsure if my approach is correct:

$(\Leftarrow):$ suppose that $f \circ g_1 = f \circ g_2$ implies $g_1 = g_2$ for any $g_1$ and $g_2$. And suppose that $f$ is not injective.

i.e. there exist $g_1(x)$ and $g_2(x)$ such that $f(g_1(x)) = f(g_2(x))$ and $g_1(x) \neq g_2(x)$

since $f(g_1(x)) = f(g_2(x))=f \circ g_1(x) = f \circ g_2(x)$, but our assumption $g_1=g_2$, and thus $g_1(x) = g_2(x)$, which is a contradiction.

  • 1
    $\begingroup$ Say what $C$ you are using and how you get $g_1, g_2$. $\endgroup$ – GEdgar Oct 9 '15 at 19:26

You are assuming more than you need to. You are going for a contradiction, but the contrapositive works just fine.

Assume $f$ is not injective, so there exists $a_1\neq a_2$ such that $f(a_1)=f(a_2)$. Now, consider a set $C=\{*\}$ with one element. Can you construct $g_1,g_2:C\to A$ such that $f(g_1(*))=f(g_2(*))$?

  • $\begingroup$ Good point! Thanks $\endgroup$ – user112358 Oct 9 '15 at 19:37

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.