Results 1 to 7 of 7

Math Help - pigeon-hole principle

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    pigeon-hole principle

    Statement 1 - If there are 'm' holes and 'n' pigeon's AND n>m then there is at least one hole with >1 pigeon

    Statement 2 - If there are 'm' holes and 'n' pigeon's AND n<m then there is at least one hole with 0 pigeon

    Are the above two statements equivalent?

    Sorry if this question is trivial but I'm just not able to put the two concepts together.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    First, it makes more sense to talk about equivalent predicates, or properties, not propositions. These two statements are equivalent because both are true, so they are equivalent to any true statement.

    A more interesting way to formulate the problem is this. Statement 1 says that |A| > |B| iff every function from A to B is not a injection. Statement 2 says that |A| < |B| iff every function from A to B is not a surjection. We can combine them to say that every function from A to B is not an injection iff every function from B to A is not a surjection.

    This is easy to prove if we note that a function is an injection iff it has a left inverse, and a function is a surjection iff it has a right inverse.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Thanks emakarov.

    Maybe I didn't formulate it properly but what I meant was

    Does Statement 1 imply Statement 2 AND Statement 2 => Statement 1?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Quote Originally Posted by aman_cc View Post
    Does Statement 1 imply Statement 2 AND Statement 2 => Statement 1?
    Of course, because both are true. In the same way, Statement 1 is equivalent to the fundamental theorem of algebra, or any other theorem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Sorry but I'm not following your argument.

    Let us say
    Statement 1 = 2 is a prime
    Statement 2 = 3 is a prime

    Now we know both are true. But I will not call them equivalent as as they one doesn't follow from the other and vice-a-versa . For me they are more like two independent true statements.

    Am I missing something?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    To be sure, you have a reasonable intuition. However, you still need to define "equivalent" or, rather, what it means for one statement to imply another. The standard definition says that the implication is true iff the premise if false or the conclusion is true. It does not require that the premise is used essentially in deriving the conclusion.

    There was work in logic and philosophy of mathematics to define other implications. See, for example, relevance logic.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Pigeon-Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 30th 2011, 02:48 AM
  2. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 04:24 AM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 03:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum