Thread: Pigeonhole principle?

Here is the problem as stated in my homework. I am going to state the proof that I have made in full and would like advice on my skills. I think I have it but I am not sure. Please be harsh if need be. I want the best proof skills that I can get. Thank you in advance.

Use the pigeonhole principle and proof by contradiction to prove this

Given non-empty finite sets X and Y with cardinality of X=cardinality of Y a function X to Y is an injection if and only if it is a surjection.

This is how I attacked it:

P implies Q states:

Given non-empty finite sets X and Y with cardinality X = cardinality of Y a function Xto Y is an injection. This means that for integers m and n there exist functions Natural Numbers(m) to X and Natural Numbers(n) to Y such that m=n. For contradiction lets say that it is not surjective. If it is not surjective then there exists and x in X such that y is not in Y. As a result m is not equal to n and we have reached our contradiction.


Now for Q implies P

Given non-empty finite sets X and Y with f:X to Y being surjective implies that cardinality of X= cardinality of Y and that f: X to Y is injective.

Now if f:X to Y is surjective then for all y in Y there exists an x in X. As a result the cardinality of Y is greater than or equal to X. Now for contradiction let's say that cardinality of X is not equal to cardinality of Y. If cardinality of X is not equal to Y then cardinality of X is less than cardinality of Y. The pegeonhole principle states that if this is the case then there are two values in y we will call y1 and y2 such that f(y1)=f(y2)implies y1 is not equal to y2. This is precisely what it means for f:Xto Y to not be injective. Hence we have reached our contradiction.

Frankly I cannot follow what are you doing. Where did you use the pigeonhole principle?
If we know that and is injective, then think of the points in Y as pigeonholes into which each goes for each . What would it mean if there were one hole empty?
No empty holes mean that is surjective.

Now can you turn the whole thing around?

Here is a big theorem from set theory.
The function is an injection if and only if there exist that is a surjrction.
You do see how that applies here?

Plato,

First off, thank you for your quick response. It is greatly appreciated. Now, I am going to answer each one of your questions the way I understand things. Here we go.


Frankly I cannot follow what are you doing. Where did you use the pigeonhole principle?

This might be where I lost you because it might be completely untrue. I stated in the converse that cardinality of Y is greater than cardinality of X. This is where I used the pigeonhole priniple. I did it by turning it around like you ask later on. I guess I am missing something.

If we know that and is injective, then think of the points in Y as pigeonholes into which each goes for each . What would it mean if there were one hole empty?

If one hole were empty then f: X to Y is not surjective.


No empty holes mean that is surjective.

Now can you turn the whole thing around?

Here is a big theorem from set theory.
The function is an injection if and only if there exist that is a surjrction.
You do see how that applies here?

I see how it applies. Doesn't this back up my point that card of Y is greater than cardinality of X.


Thanks again, hope I didn't lose you.
Today 07:22 AM

Here is what I hoped that you would see. Because |X|=|Y| there are exactly as many pigeons as pigeonholes. If one is empty then some other has two in it. But that would mean the function is not injective. Again to be surjective each hole must be used. But again the number of holes equals the number of pigeons thus a surjection implies injective.