# 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 induction hypothesis, ${h|}_{m}[m]=m$. Therefore:

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

$=h[n]$ | |||

$=m\cup \{m\}$ | |||

$=m+1$ | |||

$=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 |