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.

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 *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

Quote:

Originally Posted by

**daveclifford** Suppose *A* and *B* are finite sets and *f*:*A*→*B*. 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 *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.

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?