Next: The Pigeonhole Principle, surjective Up: Finiteness09february2012 Previous: Definition of finiteness

The Pigeonhole Principle, injective version

We need to prove that the number of elements of a finite set is unambiguous.
We prove the Pigeonhole Principle:
• (J)
For and positive integers, let be an injection.
Then .
• (K) Also if , then is a bijection.
Proof:
For (J), assume that the proposition is false.
So for some integers and with , we have an injection .
We want to reach a contradiction.
First we observe that since if is a map and , then, since , we have and , so , yet , so cannot be injective.
Now take to be the smallest positive integer, so that the proposition is false; this exists by POW.
Let .
Using the (injective) switching map , define .
Then is a well-defined map from to and is a composition of injections, so is injective.
Also we have .
Since is injective, if is an integer, such that , we have so , so .
Now define by the formula: , for each .
Then since , for any the map is well-defined.
Also if , for and in , we have , so .
So is an injection from and .
This is contrary to the definition of , so theorem (J) is proved.

For (K), for some let an injection be given, which is not a bijection.
By theorem (A), proved above, if is not a bijection, then and there is an injection .
But this contradicts theorem (J), just proved above.
So is a bijection and we are done.

Next: The Pigeonhole Principle, surjective Up: Finiteness09february2012 Previous: Definition of finiteness
George A. J. Sparling 2012-02-09