Page 1 of 2 12 LastLast
Results 1 to 15 of 30

Math Help - Prove a function is onto

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    13

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    13
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    13
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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\}?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    Posts
    13
    I'm not really sure. I'm a little confused.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Apr 2010
    Posts
    13
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Apr 2010
    Posts
    13
    I think what I'm getting confused about is what to make U equal to when I move to generalized terms.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Apr 2010
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Apr 2010
    Posts
    13
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kaypachu View Post
    This is probably totally wrong,
    Or so you'd think!

    Except, you want U=\bigcup_{v\in V}{\color{red}\{}u_v{\color{red}\}}
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. How to prove x^2 is a function?
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: October 8th 2011, 03:18 AM
  2. Prove a function is Onto
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 7th 2010, 08:01 AM
  3. prove function is one-to-one
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 8th 2010, 12:45 PM
  4. Prove that f(x) is an odd function?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 21st 2009, 02:09 PM
  5. odd function prove
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 21st 2009, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum