proof of pigeonhole principle


It will first be proven that, if a bijection exists between two finite setsMathworldPlanetmath, then the two sets have the same number of elements. Let S and T be finite sets and f:ST be a bijection. The claim will be proven by inductionMathworldPlanetmath on |S|.

If |S|=0, then S=, and f:T can only be surjectivePlanetmathPlanetmath if T=.

Assume the statement holds for any set S with |S|=n. Let |S|=n+1. Let x1,,xn+1S with S={x1,,xn+1}. Let R=S{xn+1}. Then |R|=n.

Define g:RT{f(xn+1)} by g(x)=f(x). Since RS, f(x)T for all xR. Thus, to show that g is well-defined, it only needs to be verified that f(x)f(xn+1) for all xR. This follows immediately from the facts that xn+1R and f is injectivePlanetmathPlanetmath. Therefore, g is well-defined.

Now it need to be proven that g is a bijection. The fact that g is injective follows immediately from the fact that f is injective. To verify that g is surjective, let yT{f(xn+1)}. Since f is surjective, there exists xS with f(x)=y. Since f(x)=yf(xn+1) and f is injective, xxn+1. Thus, xR. Hence, g(x)=f(x)=y. It follows that g is a bijection.

By the induction hypothesis, |R|=|T{f(xn+1)}|. Thus, n=|R|=|T{f(xn+1)}|=|T|-1. Therefore, |T|=n+1=|S|. ∎

Title proof of pigeonhole principle
Canonical name ProofOfPigeonholePrinciple
Date of creation 2013-03-22 13:31:09
Last modified on 2013-03-22 13:31:09
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 8
Author Wkbj79 (1863)
Entry type Proof
Classification msc 03E05