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<m$ , $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
Canonical name	AnotherProofOfPigeonholePrinciple
Date of creation	2013-03-22 16:02:12
Last modified on	2013-03-22 16:02:12
Owner	ratboy (4018)
Last modified by	ratboy (4018)
Numerical id	5
Author	ratboy (4018)
Entry type	Proof
Classification	msc 03E05