another proof of pigeonhole principle

By induction on $n$. It is harmless to let $n$ = $m+1$, since $0$ lacks proper subsets. Suppose that $f:n\to n$ is injective.

To begin, note that $m\in f[n]$. Otherwise, $f[m]\subseteq m$, so that by the induction hypothesis, $f[m]=m$. Then $f[n]=f[m]$, since $f[n]\subseteq m$. Therefore, for some $k, $f(k)=f(m)$.

Let $g:f[n]\to f[n]$ transpose $m$ and $f(m)$. Then $h|_{m}:m\to m$ is injective, where $h=g\circ f$. By the induction hypothesis, $h|_{m}[m]=m$. Therefore:

 $\displaystyle f[n]$ $\displaystyle=g\circ h[n]$ $\displaystyle=h[n]$ $\displaystyle=m\cup\{m\}$ $\displaystyle=m+1$ $\displaystyle=n\text{.}$
Title another proof of pigeonhole principle AnotherProofOfPigeonholePrinciple 2013-03-22 16:02:12 2013-03-22 16:02:12 ratboy (4018) ratboy (4018) 5 ratboy (4018) Proof msc 03E05