2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ In your argument for the forward direction, you have not actually defined $g$. $\endgroup$ – Trevor Wilson Sep 5 '13 at 5:35
  • $\begingroup$ 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. $\endgroup$ – user60887 Sep 5 '13 at 5:39
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Sep 5 '13 at 5:41
  • $\begingroup$ 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$. $\endgroup$ – Trevor Wilson Sep 5 '13 at 5:42
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Sep 5 '13 at 5:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does it matter that I talk about for any $b\in B$ \ $C $? $\endgroup$ – user60887 Sep 5 '13 at 5:52
  • $\begingroup$ Oh what I mean for any $b$ outside the range of $f$. $\endgroup$ – user60887 Sep 5 '13 at 5:55
  • $\begingroup$ 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? $\endgroup$ – Cameron Buie Sep 5 '13 at 5:57
  • $\begingroup$ Because the range of $f$ is the domain of $g$? $\endgroup$ – user60887 Sep 5 '13 at 6:00
  • 1
    $\begingroup$ @user60887: I took a look, and edited my answer with some tips to refine it. $\endgroup$ – Cameron Buie Sep 8 '13 at 16:34

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.