Results 1 to 2 of 2

Math Help - Proving countability from surjectivity

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    2

    Proving countability from surjectivity

    let f: S --> T be a surjective function
    if S is countable, prove that T is countable

    I see that f(S) = T, but and I know that there is a surjection from the natural numbers to S, and an injection from S to N, but I'm not really sure where to head to show that T is countable...Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,608
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by blackmustachio View Post
    let f: S --> T be a surjective function
    if S is countable, prove that T is countable.
    Though this answer is a bit late, it may help someone.
    This is a well known theorem: F:A \mapsto B is injective if and only if there is a surjection G:B \mapsto A.
    Because you are given that f:S \mapsto T is a surjection then by the theorem there is an injection h:T \mapsto S.
    Also because S is countable then there in an injection g:S \mapsto Z^ +.
    Hence g \circ h:T \mapsto Z^ +  is an injection, proving that T is countable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. surjectivity
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 5th 2010, 07:50 PM
  2. injectivity and surjectivity (onto and one-one)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 22nd 2009, 09:01 PM
  3. Surjectivity of (x^3) +5
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 3rd 2008, 07:24 AM
  4. urgent homework-proving surjectivity from conditions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 11th 2008, 11:26 AM
  5. Injectivity and Surjectivity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 24th 2007, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum