PlanetMath: proof of pigeonhole principle

Proof. It will first be proven that, if a bijection exists between two finite sets, then the two sets have the same number of elements. Let

and

be finite sets and $f \colon S \to T$ be a bijection. The claim will be proven by induction on $\vert S\vert$ .

If $\vert S\vert=0$ , then $S=\emptyset$ , and $f \colon \emptyset \to T$ can only be surjective if $T=\emptyset$ .

Assume the statement holds for any set with $\vert S\vert=n$ . Let $\vert S\vert=n+1$ . Let $x_1, \dots , x_{n+1} \in S$ with $S=\{x_1, \dots , x_{n+1}\}$ . Let $R=S \setminus \{x_{n+1}\}$ . Then $\vert R\vert=n$ .

Define $g \colon R \to T \setminus \{f(x_{n+1})\}$ by . Since $R \subset S$ , $f(x) \in T$ for all $x \in R$ . Thus, to show that is well-defined, it only needs to be verified that $f(x) \neq f(x_{n+1})$ for all $x \in R$ . This follows immediately from the facts that $x_{n+1} \notin R$ and is injective. Therefore, is well-defined.

Now it need to be proven that is a bijection. The fact that is injective follows immediately from the fact that is injective. To verify that is surjective, let $y \in T \setminus \{f(x_{n+1})\}$ . Since is surjective, there exists $x \in S$ with . Since $f(x)=y \neq f(x_{n+1})$ and is injective, $x \neq x_{n+1}$ . Thus, $x \in R$ . Hence, . It follows that is a bijection.

By the induction hypothesis, $\vert R\vert=\vert T \setminus \{f(x_{n+1})\}\vert$ . Thus, $n=\vert R\vert=\vert T \setminus \{f(x_{n+1})\}\vert=\vert T\vert-1$ . Therefore, $\vert T\vert=n+1=\vert S\vert$ . $\qedsymbol$