# 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 $S$ and $T$ be finite sets and $f:S\to T$ be a bijection. The claim will be proven by induction^{} on $|S|$.

If $|S|=0$, then $S=\mathrm{\varnothing}$, and $f:\mathrm{\varnothing}\to T$ can only be surjective^{} if $T=\mathrm{\varnothing}$.

Assume the statement holds for any set $S$ with $|S|=n$. Let $|S|=n+1$. Let ${x}_{1},\mathrm{\dots},{x}_{n+1}\in S$ with $S=\{{x}_{1},\mathrm{\dots},{x}_{n+1}\}$. Let $R=S\setminus \{{x}_{n+1}\}$. Then $|R|=n$.

Define $g:R\to T\setminus \{f({x}_{n+1})\}$ by $g(x)=f(x)$. Since $R\subset S$, $f(x)\in T$ for all $x\in R$. Thus, to show that $g$ is well-defined, it only needs to be verified that $f(x)\ne f({x}_{n+1})$ for all $x\in R$. This follows immediately from the facts that ${x}_{n+1}\notin R$ and $f$ is injective^{}. 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 $y\in T\setminus \{f({x}_{n+1})\}$. Since $f$ is surjective, there exists $x\in S$ with $f(x)=y$. Since $f(x)=y\ne f({x}_{n+1})$ and $f$ is injective, $x\ne {x}_{n+1}$. Thus, $x\in R$. Hence, $g(x)=f(x)=y$. It follows that $g$ is a bijection.

By the induction hypothesis, $|R|=|T\setminus \{f({x}_{n+1})\}|$. Thus, $n=|R|=|T\setminus \{f({x}_{n+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 |