# Thread: Proving pigeonhole principle involving cardinality of finite sets

1. ## 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.

2. ## Re: Proving pigeonhole principle involving cardinality of finite sets

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?