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.