# Pigeonhole principle?

• Dec 9th 2007, 07:22 AM
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.
• Dec 9th 2007, 08:21 AM
Plato
Frankly I cannot follow what are you doing. Where did you use the pigeonhole principle?
If we know that $\left| X \right| = \left| Y \right| < \infty$ and $f:X \mapsto Y$ is injective, then think of the points in Y as pigeonholes into which each $f(x)$ goes for each $x \in X$. What would it mean if there were one hole empty?
No empty holes mean that $f$ is surjective.

Now can you turn the whole thing around?

Here is a big theorem from set theory.
The function $f:X \mapsto Y$ is an injection if and only if there exist $g:Y \mapsto X$ that is a surjrction.
You do see how that applies here?
• Dec 9th 2007, 09:24 AM
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 http://www.mathhelpforum.com/math-he...c89a6234-1.gif and http://www.mathhelpforum.com/math-he...104e1150-1.gif is injective, then think of the points in Y as pigeonholes into which each http://www.mathhelpforum.com/math-he...a378be62-1.gif goes for each http://www.mathhelpforum.com/math-he...ec511b07-1.gif. 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 http://www.mathhelpforum.com/math-he...1929cce7-1.gif is surjective.

Now can you turn the whole thing around?

Here is a big theorem from set theory.
The function http://www.mathhelpforum.com/math-he...104e1150-1.gif is an injection if and only if there exist http://www.mathhelpforum.com/math-he...8cc66f36-1.gif 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
• Dec 9th 2007, 09:58 AM
Plato
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.