1. ## 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.

2. 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.

3. 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?

4. Originally Posted by aman_cc
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.

5. 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?

6. 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.