# Math Help - Prove a function is onto

1. ## Prove a function is onto

I need to prove:

Let f:A->B be a function. We can generate a function from P(A) to P(B) using images. Define F: P(A)->P(B) by F(S)=f(S) for each S $\in$ P(A). Under what circumstances is F onto?

I know that F is onto when f is onto, but how do I go about proving this?

2. Originally Posted by kaypachu
I need to prove:

Let f:A->B be a function. We can generate a function from P(A) to P(B) using images. Define F: P(A)->P(B) by F(S)=f(S) for each S $\in$ P(A). Under what circumstances is F onto?

I know that F is onto when f is onto, but how do I go about proving this?
What do you think?

For the if part this is easy.

For the only if part note that if $f$ is not surjective then $f(A)\subsetneq B$

3. I don't understand what you are asking. I merely have to prove "F is onto when f is onto." There are no iff statements in this proof.

4. Originally Posted by kaypachu
I don't understand what you are asking. I merely have to prove "F is onto when f is onto." There are no iff statements in this proof.
The "when is it true" indicates to me it's an iff.

So what part are you having trouble with particularly?

5. I just have to prove that F is onto using the fact that f is onto somewhere in my proof.

I'm having trouble with how to start the proof. I know the standard way to start an onto proof, but the function F is throwing me off.

I also don't know what I should make S.

6. Originally Posted by kaypachu
I just have to prove that F is onto using the fact that f is onto somewhere in my proof.

I'm having trouble with how to start the proof. I know the standard way to start an onto proof, but the function F is throwing me off.

I also don't know what I should make S.
So, let me start you off. To prove that $F$ is surjective you must prove that $F(\mathcal{P}(A))=\mathcal{P}(B)$, right? But, think about it like this. Let $C\subseteq\mathcal{P}(B)$ then for each $c\in C$ there must exists some $x_c\in A$ such that $f(x_c)=c$. So, what is significant about $\bigcup_{c\in C}\{x_c\}$?

7. I'm not really sure. I'm a little confused.

8. Originally Posted by kaypachu
I'm not really sure. I'm a little confused.
So, we want to prove that given a set $V$ in $\mathcal{P}(B)$ there is a set $U$ in $\mathcal{P}(A)$ such that $F(U)=V$, right? But, think about it: this $V$ is just made up of a whole bunch of elements of $B$. But, since $f$ is surjective each of those elements has something in $A$ which maps to them, right? So, if for each $v\in V$ we take the element $x_v\in A$ which $f(x_v)=v$ we get a set $U$ whose image under $f$ is...

9. I think I get where you are going with that, but I'm still a bit unsure.

The set U would be a bunch of elements in A, right?

10. Originally Posted by kaypachu
I think I get where you are going with that, but I'm still a bit unsure.

The set U would be a bunch of elements in A, right?
Maybe an example would be helpful.

Think about the function $f:\{1,\cdots,10\}\to\{1,2,3\}$ by $f(1)=f(2)=f(6)=f(10)=1,f(3)=f(4)=f(5)=2,f(7)=f(8)= f(9)=3$. This is clearly surjective, right? Now, we can form a mapping $F:\mathcal{P}\left(\{1,\cdots,10\}\right)\to\mathc al{P}\left(\{1,2,3\}\right):U\mapsto f(U)$ where $f(U)=\left\{f(u):u\in U\right\}$. So, why is this necessarily surjective? So, what I have to prove to you is that given $V\in\mathcal{P}\left(\{1,2,3\}\right)$ I can find some $U\in\mathcal{P}\left(\{1,\cdots,10\}\right)$ such that $F(U)=f(U)=V$.

But, for example let's take $V=\{1,3\}$. Now, I know that for each element of $V$ (namely, $1,3$) I can find some element of $\{1,\cdots,10\}$ that maps to it because $f$ is surjective. So, let's pick two of the elements. For example, if I pick $U=\{1,2,9\}$ then $F(U)=f(U)=\left\{f(1),f(2),f(9)\right\}=\left\{1,3 \right\}=V$.

Now, generalize.

11. I think what I'm getting confused about is what to make U equal to when I move to generalized terms.

12. Originally Posted by kaypachu
I think what I'm getting confused about is what to make U equal to when I move to generalized terms.
So, you're going to give me some $V\in\mathcal{P}(B)$. For each $v\in V$ there exists some $u_v\in A$ such that $f(u_v)=v$. So, choosing $u_v$ for each $v\in V$ and making that into a set works.......right?

13. My professor wants me to provide a candidate (U) and show that it does what I want it to do (i.e. F(U)=f(U)=V). How do I define U?

14. This is probably totally wrong, but this is my first attempt at this proof:

Prove that F is onto when f is onto.

Let f be onto. Let $V \in \mathcal{P}(B)$. For each $v \in V$ there exists some $u_{v} \in A$ such that $f(u_{v})=v$. Let $U= \bigcup_{v \in V}{u_{v}}$. Then $F(\bigcup_{v \in V}{u_{v}})=f(\bigcup_{v \in V}{u_{v}})=V$.

15. Originally Posted by kaypachu
This is probably totally wrong,
Or so you'd think!

Except, you want $U=\bigcup_{v\in V}{\color{red}\{}u_v{\color{red}\}}$

Page 1 of 2 12 Last