Results 1 to 2 of 2
Like Tree2Thanks
  • 2 Post By Plato

Math Help - Proving pigeonhole principle involving cardinality of finite sets

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    Malaysia
    Posts
    5

    Proving pigeonhole principle involving cardinality of finite sets

    Suppose A and B are finite sets and f:AB. Prove that if |A|>|B|, then f is not one-to-one.
    Scratch work:
    Since the goal is in negation, I try to prove it by contradiction and assume that f is one-to-one. Since A has more elements than B, it can't be the case that f is one-to-one because some aA has to share images with other. But other than the false assumption f is one-to-one, I have no other clue to proceed with the question. What technique should I apply? Please give hints and guidance. Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1

    Re: Proving pigeonhole principle involving cardinality of finite sets

    Quote Originally Posted by daveclifford View Post
    Suppose A and B are finite sets and f:AB. Prove that if |A|>|B|, then f is not one-to-one.
    Scratch work:
    Since the goal is in negation, I try to prove it by contradiction and assume that f is one-to-one. Since A has more elements than B, it can't be the case that f is one-to-one because some aA has to share images with other. But other than the false assumption f is one-to-one, I have no other clue to proceed with the question. What technique should I apply? Please give hints and guidance. Thanks in advance.
    Let $f(A)$ be the set of images. Then $f(A)\subseteq B$ so $|f(A)|\le |B|$.

    If $f$ is one-to-one then $|f(A)|=|A|$. What can you do with that?
    Thanks from HallsofIvy and daveclifford
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: December 17th 2012, 03:23 PM
  2. Proving cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 29th 2011, 09:54 AM
  3. cardinality of finite sets
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: January 6th 2010, 07:47 PM
  4. Proving finite sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 21st 2009, 09:11 AM
  5. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: July 22nd 2007, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum