## You are here

Homeproof of pigeonhole principle

## Primary tabs

# 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\colon S\to T$ be a bijection. The claim will be proven by induction on $|S|$.

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

Assume the statement holds for any set $S$ with $|S|=n$. Let $|S|=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 $|R|=n$.

Define $g\colon 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)\neq 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\neq f(x_{{n+1}})$ and $f$ is injective, $x\neq 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|$. ∎

## Mathematics Subject Classification

03E05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier