2

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?

user60887
  • 2,935
  • In your argument for the forward direction, you have not actually defined $g$. – Trevor Wilson Sep 05 '13 at 05: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 05 '13 at 05: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 05 '13 at 05: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 05 '13 at 05: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 05 '13 at 05:48

1 Answers1

2

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.

Cameron Buie
  • 102,994
  • Does it matter that I talk about for any $b\in B$ \ $C $? – user60887 Sep 05 '13 at 05:52
  • Oh what I mean for any $b$ outside the range of $f$. – user60887 Sep 05 '13 at 05: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 05 '13 at 05:57
  • Because the range of $f$ is the domain of $g$? – user60887 Sep 05 '13 at 06:00
  • Not quite. Rather, the range of $f$ is the only part of the domain of $g$ that matters to $g\circ f$. Any ideas on how you might define $g:B\to A$? – Cameron Buie Sep 05 '13 at 06:03
  • Oh I get it. The range of $f$ can be a small portion of the domain of $g$. Not really. – user60887 Sep 05 '13 at 06:05
  • Absolutely! Let me give you (most of) a concrete example. Let $A$ be the real interval $[0,1]$ and $B=\Bbb R,$ and define $f:A\to B$ by $$f(x)=\frac1{3x+1}$$ (just to make it a bit interesting). Now, $C=\left[\frac14,1\right],$ but there's a lot of $B$ that isn't covered. We're in luck, though...that doesn't actually matter. Fix any $r\in A$. For $b\in B\setminus C,$ we'll let $g(b)=r.$ For $b\in C,$ we *must* put $$g(b)=???$$ – Cameron Buie Sep 05 '13 at 06:13
  • In other words: At some point of the proof you should make use o fthe given fact that $A$ is nonempty ... – Hagen von Eitzen Sep 05 '13 at 06:16
  • @Hagen: Thank you. I should have made that explicit. – Cameron Buie Sep 05 '13 at 06:16
  • @user60887: Do you see what Hagen is talking about (i.e.: where I used the fact that $A$ is nonempty)? – Cameron Buie Sep 05 '13 at 06:18
  • g(b)=a for some unique a in A? – user60887 Sep 05 '13 at 06:28
  • It seems I need a function g that is part one to one. – user60887 Sep 05 '13 at 06:29
  • @user60887: Actually, we don't require $A$ to be nonempty in order to say "for all $b\in C$, we can define $g(b)$ to be the unique element of $A$ such that $f(a)=b$"--indeed, this statement is vacuously true if $A$ is empty. Likewise, if $A$ is empty, then $C$ is empty, and so we vacuously have for all $b\in C$ that $g(b)=a$ for some unique $a\in A$. The kicker is the "fix any $r\in A$" part. We can't do this if $A$ is empty. – Cameron Buie Sep 05 '13 at 06:33
  • Hmm I need to think about this more tomorrow. I'll post' new comments here when I have it figured out if that's fine? Thanks for your help though. – user60887 Sep 05 '13 at 06:43
  • Of course that's fine. – Cameron Buie Sep 05 '13 at 06:43
  • So where I say "Since $f$ is one to one by assumption then for every $a\in A$ there is a unique element $b \in B$ such that $f(a)=b$. Then $(g \circ f)(a)=g(f(a))=g(b)$ such that $g(b)=a\in A$ " is somewhat correct but i'm missing the fact that range of $f$ which is set $C$ is a subset of the codomain of $g$. Then any elements outside which are $B$ \ $C$ I can fix any element in A to them. From what I understand we are doing this because the only elements that really matter are the ones in $C$ because those are the ones that are getting mapped to by $f$ and we want a function to return those. – user60887 Sep 06 '13 at 00:18
  • @user60887: Oh, my goodness! I'm not sure how I missed the error in the first sentence of your first part. Since $f:A\to B$ is a function, then for every $a\in A$, there is a unique $b\in B$ such that $f(a)=b$. That has nothing to do with the fact that $f$ is one to one. Now, since $f$ is one to one and has range $C$, the for each $b\in C$ there is a unique element $a\in A$ such that $f(a)=b,$ and we will to call this $a$ by the name $g(b)$ for each $b\in C$. – Cameron Buie Sep 06 '13 at 03:20
  • As for why we can fix any $a_0\in A$ and set $g(b)=a_0$ for $b\in B\setminus C,$ I think you've understood it correctly. There's only one way that we can define $g$ on $C$ to get the desired result, but we can define $g$ however we like on $B\setminus C$, so long as $g(b)\in A$ for all $b\in B\setminus C$. – Cameron Buie Sep 06 '13 at 03:21
  • Oops yes I had my one to one definition backwards. Thanks for your help though. I can take it from here since I now understand what is going on. – user60887 Sep 06 '13 at 05:10
  • If you want to edit your proof once you've made your corrections (and then alert me with a comment), I'd be glad to take a look and make sure it's all okay. – Cameron Buie Sep 06 '13 at 05:26
  • Ok I've edited the proof you can check it now if its all correct. – user60887 Sep 07 '13 at 19:00
  • 1
    @user60887: I took a look, and edited my answer with some tips to refine it. – Cameron Buie Sep 08 '13 at 16:34