Proving pigeonhole principle involving cardinality of finite sets
Suppose A and B are finite sets and f:A→B. Prove that if |A|>|B|, then f is not one-to-one.
Since the goal is in negation, I try to prove it by contradiction and assume that f is one-to-one. Since A has more elements than B, it can't be the case that f is one-to-one because some a∈A has to share images with other. But other than the false assumption f is one-to-one, I have no other clue to proceed with the question. What technique should I apply? Please give hints and guidance. Thanks in advance.
Re: Proving pigeonhole principle involving cardinality of finite sets
Let $f(A)$ be the set of images. Then $f(A)\subseteq B$ so $|f(A)|\le |B|$.
Originally Posted by daveclifford
If $f$ is one-to-one then $|f(A)|=|A|$. What can you do with that?