# One to one function proof

Let $A$ be a nonempty set and let $f:A\rightarrow B$ be a function. Prove that $f$ is one to one if and only if there exists a function $g:B\rightarrow A$ such that $g \circ f=i_a$ ($g \circ f$ is function composition and $i_a$ is the identity function.

Proof: ($\Rightarrow$) Assume that $f$ is one to one and $A$ is a nonempty set. Let set $C=$range $f$. Since f is one to one then every $b\in C$ there is a unique element call it $a\in A$ such that $f(a)=b$. Now we define a function $g$ where $g:B\rightarrow A$ as such: Since $C\subseteq B$ it follows that $|C|\leq |B|$. Then for each $a\in A$ we let $a=g(b)$ for some $b\in C$. Thus $g(b)=g(f(a))=a=1_A$. Since $C\subseteq B$ any element(s) call it $k$ where $k\in B$\ $C$ we can assign any $a_0\in A$ such that $g(k)=a_0$ since $k$ is not mapped by $f$.

($\Leftarrow$) Assume there exists a function $g:B\rightarrow A$ such that $g \circ f=i_a$ Let $a_1,a_2 \in A$ such that $a_1\neq a_2$ Then it follows that $g(f(a_1))=a_1$ and $g(f(a_2))=a_2$ Thus $g(f(a_1))\neq g(f(a_2))$ Thus $g \circ f$ is one to one. Let $x_1,x_2\in A$. Then it follow that $g(f(x_1))=g(f(x_2)) \implies$ that $x_1=x_2$ by definition of one to one. Thus it follow that $f(x_1)=f(x_2)$ Hence f is one to one.

How could I better this proof or what parts need fixing?

• In your argument for the forward direction, you have not actually defined $g$. – Trevor Wilson Sep 5 '13 at 5:35
• Oh yeah my foward direction is way off. I need to somehow define my function $g$. Well I know for the backwards direction that $g o f$ is one to one. – user60887 Sep 5 '13 at 5:39
• The first part is not right. For every $b$ in the range of $f$, let $g(b)$ be the unique $a$ such that $f(a)=b$. For every $b$ not in the range, let $g(b)=a_0$, where $a_0$ is some fixed element of $A$. – André Nicolas Sep 5 '13 at 5:41
• I think I understand your argument for the backwards direction now, but it's a little unclear. Maybe you should say that if $f(x_1) = f(x_2)$, then $g(f(x_1)) = g(f(x_2))$, so $x_1 = x_2$. – Trevor Wilson Sep 5 '13 at 5:42
• For the second part, it would be better to say this. If $f$ is not one to one, let $a_1,a_2$ with $a_1\ne a_2$ such that $f(a_1)=f(a_2)=b$. Then argue that $g\circ f$ cannot be $i_A$. – André Nicolas Sep 5 '13 at 5:48

Your second part is fine, but your first part doesn't really work, since you took $g$ to be an arbitrary function $B\to A$. You do seem to have something close to the right idea about how $g$ should be defined, though. We'll need to define $g$ in a specific way only on the range of $f$ (why?)--which may not be all of $B$--but letting $C$ be the range of $f,$ for all $b\in C,$ we can define $g(b)$ to be the unique $a\in A$ such that $f(a)=b$, and for $b\in B\setminus C,$ you can define $g(b)$ to be any element of $A$ that you like. That should do the trick for you (so long as you can prove that this is well-defined, which shouldn't be tough).

Added: Your fixed proof looks good, largely, but could be simpler. In the forward direction, you could instead simply say (after your first two sentences):

Since $f$ is one-to-one, then for every $b\in C$ there is a unique $a\in A$ such that $f(a)=b,$ call it $g(b)$. Fixing any $a_0\in A,$ for each $b\in B\setminus C$, let $g(b)=a_0.$ Then $g:B\to A$, and taking any $a\in A,$ we have $f(a)\in C$, so $a=g\bigl(f(a)\bigr)=(g\circ f)(a)$ by definition of $g$. Hence, $g\circ f=i_A.$

In the backward direction, after you note that $g(f(a_1))\ne g(f(a_2)),$ we can immediately conclude from the fact that $g$ is a function that $f(a_1)\ne f(a_2)$. Thus, $f$ is one-to-one.

• Does it matter that I talk about for any $b\in B$ \ $C$? – user60887 Sep 5 '13 at 5:52
• Oh what I mean for any $b$ outside the range of $f$. – user60887 Sep 5 '13 at 5:55
• Well, we have to talk about any $b\in B\setminus C$ that there happen to be, if we want to have $g$ defined on all of $B$. Fortunately, the way we define $g$ on $B\setminus C$ won't make any difference when we need to prove that $g\circ f=i_A.$ Can you see why? – Cameron Buie Sep 5 '13 at 5:57
• Because the range of $f$ is the domain of $g$? – user60887 Sep 5 '13 at 6:00
• @user60887: I took a look, and edited my answer with some tips to refine it. – Cameron Buie Sep 8 '13 at 16:34