another proof of pigeonhole principle

By inductionMathworldPlanetmath on n. It is harmless to let n = m+1, since 0 lacks proper subsetsMathworldPlanetmathPlanetmath. Suppose that f:nn is injectivePlanetmathPlanetmath.

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

Let g:f[n]f[n] transpose m and f(m). Then h|m:mm is injective, where h=gf. By the induction hypothesis, h|m[m]=m. Therefore:

f[n] =gh[n]
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