Results 1 to 4 of 4

Math Help - Help with injective, surjective proof

  1. #1
    Dax
    Dax is offline
    Newbie
    Joined
    Sep 2009
    Posts
    4

    Help with injective, surjective proof

    Please help me with this, I'm not sure I understand it and don't know where to start

    Let A and B be finite sets with |A| = |B|. Suppose that f: A--->B. Prove that f is injective if and only if f is surjective
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by Dax View Post
    Let A and B be finite sets with |A| = |B|. Suppose that f: A--->B. Prove that f is injective if and only if f is surjective
    Suppose that f:A \mapsto B is injective but not surjective.
    Notation: f^{ - 1} (b) = \left\{ {x \in A:f(x) = b} \right\}
    \mathbb{F} = \left\{ {f^{ - 1} (b):b \in B} \right\}\;\& \,\left| \bigcup\mathbb{F} \right| = \left| A \right|
    But f is not surjective so \left( {\exists c \in B} \right)\left[ {f^{ - 1} (c) = \emptyset } \right].
    So what is the contradiction?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Dax
    Dax is offline
    Newbie
    Joined
    Sep 2009
    Posts
    4
    is there an easier way to explain that, none of that looks familiar, i'm only a few weeks into the class and that doesn't make sense to me at all
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by Dax View Post
    is there an easier way to explain that, none of that looks familiar, i'm only a few weeks into the class and that doesn't make sense to me at all
    Look, this is not a trivial problem. It usually makes use of the pigeon-hole principle.
    You are not going to find a trivial proof. Any proof is equivalent to proving a form of the pigeon-hole principle.

    That said, try this.
    Suppose that f:A \mapsto B is injective.
    \left( {\forall a \in A} \right)\left\{ {\{ f(a)\} } \right\} is collection of pair-wise disjoint subsets of B.
    But by the nature if functions \left| {\left\{ {\{ f(a)\} } \right\}} \right| = \left| A \right| = \left| B \right|.
    From that how can conclude that f is surjective?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. When will be this surjective or injective?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 27th 2011, 11:20 AM
  2. injective and surjective
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 12th 2010, 11:18 AM
  3. Injective/Surjective.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 31st 2009, 08:14 AM
  4. Proof of Injective and Surjective
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 23rd 2008, 01:47 PM
  5. Injective and surjective
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 13th 2008, 08:35 PM

Search Tags


/mathhelpforum @mathhelpforum