I am looking to prove the Pigeonhole Principle by proving the following claim:
Let $A$ be a set with $m$ elements, and let $B$ be a set with $n$ elements, where $m,n\in \omega$ and $m > n$. Suppose $f$ is a function from $A$ to $B$. Then $f$ is not injective.
I am looking to eventually show that $f$ is not a bijection from $A$ to $B$ by proving that $\require{cancel}A \cancel{\sim} B$ (in case that symbol is tough to read: $A$ is not equinumerous to $B$).
I am having trouble getting started though. I have that $\{1,...n\}\subset \{1,...,m\}$, but I am unsure where to go from here to get my desired result.
Any direction is appreciated!
An example would be:
A={1,2,3,4,5}; B={1,2,3,4}
If we say that $\forall a\in A, !\exists b\in B:b=a$, we have a=b=1;a=b=2;a=b=3;a=b=4 but we can't assign a new value that equals 5. so 5 is not able to be paired up. In essence, this is all the pigeonhole principle is saying. It can be restated as, if you have two sets, such that one set has a higher cardinality than the other, you can't pair the elements of these sets in a way that avoids pairing up the same value in the smaller set twice ( or n times for the general case). We call this smaller set the pigeonholes, and the larger one the pigeons.