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 ,$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 inductionhypothesis, ${h|}_m[m]=m$. Therefore:

$f[n]$$=g\circ h[n]$

$=h[n]$

$=m\cup \{m\}$

$=m+1$

$=n\text{.}$