# Proving pigeonhole principle involving cardinality of finite sets

• Feb 26th 2014, 04:16 AM
daveclifford
Proving pigeonhole principle involving cardinality of finite sets
Suppose A and B are finite sets and f:AB. Prove that if |A|>|B|, then f is not one-to-one.
Scratch work:
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 aA 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.
• Feb 26th 2014, 05:37 AM
Plato
Re: Proving pigeonhole principle involving cardinality of finite sets
Quote:

Originally Posted by daveclifford
Suppose A and B are finite sets and f:AB. Prove that if |A|>|B|, then f is not one-to-one.
Scratch work:
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 aA 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.

Let $f(A)$ be the set of images. Then $f(A)\subseteq B$ so $|f(A)|\le |B|$.

If $f$ is one-to-one then $|f(A)|=|A|$. What can you do with that?