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 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?
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, we want to prove that given a set in there is a set in such that , right? But, think about it: this is just made up of a whole bunch of elements of . But, since is surjective each of those elements has something in which maps to them, right? So, if for each we take the element which we get a set whose image under is...
Maybe an example would be helpful.
Think about the function by . This is clearly surjective, right? Now, we can form a mapping where . So, why is this necessarily surjective? So, what I have to prove to you is that given I can find some such that .
But, for example let's take . Now, I know that for each element of (namely, ) I can find some element of that maps to it because is surjective. So, let's pick two of the elements. For example, if I pick then .
Now, generalize.