Results 1 to 2 of 2

Math Help - Proofs: pigeonhole principle and functions

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Proofs: pigeonhole principle and functions

    I need help with two proofs.

    First, I must prove the pigeon hole principle.

    Second, Let f: A --> B be an injection between two finite sets of the same size. From this, Prove the f is a bijection.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by jzellt View Post
    I need help with two proofs.

    First, I must prove the pigeon hole principle.
    see here, or here

    Second, Let f: A --> B be an injection between two finite sets of the same size. From this, Prove the f is a bijection.
    a proof by contradiction should work. you may use the first proof to help you.

    assume to the contrary that f:A --> B is an injection between sets A and B with |A|=|B|, but f is NOT an bijection. then it would mean that either f is not injective, or not surjective. by assumption, it is injective, so it must be the case that it is not surjective, that is, not onto. but that would mean .....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. PigeonHole Principle
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 13th 2011, 05:25 AM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2008, 09:09 AM
  4. pigeonhole principle
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 12th 2008, 07:01 AM
  5. 2.b Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 7th 2008, 01:17 AM

Search Tags


/mathhelpforum @mathhelpforum