# Thread: 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$\displaystyle \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$\displaystyle \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 $\displaystyle f$ is not surjective then $\displaystyle 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 $\displaystyle F$ is surjective you must prove that $\displaystyle F(\mathcal{P}(A))=\mathcal{P}(B)$, right? But, think about it like this. Let $\displaystyle C\subseteq\mathcal{P}(B)$ then for each $\displaystyle c\in C$ there must exists some $\displaystyle x_c\in A$ such that $\displaystyle f(x_c)=c$. So, what is significant about $\displaystyle \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 $\displaystyle V$ in $\displaystyle \mathcal{P}(B)$ there is a set $\displaystyle U$ in $\displaystyle \mathcal{P}(A)$ such that $\displaystyle F(U)=V$, right? But, think about it: this $\displaystyle V$ is just made up of a whole bunch of elements of $\displaystyle B$. But, since $\displaystyle f$ is surjective each of those elements has something in $\displaystyle A$ which maps to them, right? So, if for each $\displaystyle v\in V$ we take the element $\displaystyle x_v\in A$ which $\displaystyle f(x_v)=v$ we get a set $\displaystyle U$ whose image under $\displaystyle 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 $\displaystyle f:\{1,\cdots,10\}\to\{1,2,3\}$ by $\displaystyle 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 $\displaystyle F:\mathcal{P}\left(\{1,\cdots,10\}\right)\to\mathc al{P}\left(\{1,2,3\}\right):U\mapsto f(U)$ where $\displaystyle 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 $\displaystyle V\in\mathcal{P}\left(\{1,2,3\}\right)$ I can find some $\displaystyle U\in\mathcal{P}\left(\{1,\cdots,10\}\right)$ such that $\displaystyle F(U)=f(U)=V$.

But, for example let's take $\displaystyle V=\{1,3\}$. Now, I know that for each element of $\displaystyle V$ (namely, $\displaystyle 1,3$) I can find some element of $\displaystyle \{1,\cdots,10\}$ that maps to it because $\displaystyle f$ is surjective. So, let's pick two of the elements. For example, if I pick $\displaystyle U=\{1,2,9\}$ then $\displaystyle 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 $\displaystyle V\in\mathcal{P}(B)$. For each $\displaystyle v\in V$ there exists some $\displaystyle u_v\in A$ such that $\displaystyle f(u_v)=v$. So, choosing $\displaystyle u_v$ for each $\displaystyle 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 $\displaystyle V \in \mathcal{P}(B)$. For each $\displaystyle v \in V$ there exists some $\displaystyle u_{v} \in A$ such that $\displaystyle f(u_{v})=v$. Let $\displaystyle U= \bigcup_{v \in V}{u_{v}}$. Then $\displaystyle 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 $\displaystyle U=\bigcup_{v\in V}{\color{red}\{}u_v{\color{red}\}}$

Page 1 of 2 12 Last