Results 1 to 5 of 5

Math Help - Injection implied by Surjection

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Injection implied by Surjection

    Hey all, some help with the following proof would be appreciated:

    Let A and B be sets. There exists an injection from A to B if and only if there exists a surjection from B to A.

    Makes sense logically because this means no element of A is left out, but I'm not sure how to word it in a proof.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by jstarks44444 View Post
    Let A and B be sets. There exists an injection from A to B if and only if there exists a surjection from B to A.
    Leave out any nonsense about empty sets.
    Say that g:A\to B is injective.
    We want to find a surjection f:B\to A.

    The image set g[A]\subseteq B. So for each y\in B either y\in g[A]\text{ or not}.
    Because g is injective, if y\in g[A] there is a unique a_y\in A such that g\left( {a_y } \right) = y.
    Now select any b\in A. Fix it.
    We now define f:B\to A.
    f(z)=a_z\text{ if }z\in g[A]\text{, else }f(z)=b.
    That is a surjection. Prove it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    "if and only if" This means you have two implications. You did just one of them.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by veileen View Post
    "if and only if" This means you have two implications. You did just one of them.
    Of course I did only one of them.
    THIS IS NOT A HOMEWORK SERVICE!
    I will not do complete questions.

    What business is it of yours anyway?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    Well, you said nothing about the second implication and jstarks44444 could think that is the whole proof.

    "What business is it of yours anyway?" Uhm, what? o.o
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Injection/Surjection
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 17th 2010, 10:13 PM
  2. Injection and Surjection
    Posted in the Advanced Algebra Forum
    Replies: 15
    Last Post: January 7th 2010, 06:44 AM
  3. injection, surjection and bijection questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 7th 2009, 10:23 AM
  4. Prove injection and surjection
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 31st 2009, 07:48 PM
  5. injection & surjection proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 05:01 AM

Search Tags


/mathhelpforum @mathhelpforum