simple proof for principle of pigeons I must prove the principle of pigeons but the proofs I find in the internet are too complex. Here's what I can use:
Definition $$I_n = \{p\in \mathbb{N}; p\le n\}$$
The principle of the pigeons states that if $m>n$ then there can't exist an injective function $I_n\to I_m$.
I've proven before that if there is a bijection from $I_n$ to $I_m$ then $n=m$ but I'm unable to prove it for just an injection. Could you guys help me?
 A: Perhaps I will write something wrong? (This seems easy to me).
First of all, I think you mean there can't exist an injective function $f:I_m\to I_n$, for if $n<m$ there actually exists an injective $I_n\to I_m$ (the inclusion).
Suppose $n<m$ and $f:I_m\to I_n$ injective. Then $f:I_m\to f(I_m)$ is bijective, where $f(I_m)=\{f(1),...,f(m)\}$. Clearly $f(I_m)$ has $m$ elements, then $m\le n$ because $f(I_m)\subseteq I_n$.
A: Here is a proof that if $n<m$ are natural numbers then every function $f : I_m \to I_n$ is non-injective. The proof is by induction on $n$.
Consider first the base case $n=1$, and so $m \ge 2$. Then $f(1)=f(2)=1$ and so $f$ is not injective.
Now assume the induction hypothesis: the statement is true for $n=k$. We must prove the statement is true for $n=k+1$. Consider $m > k+1$ and any function $f : I_m \to I_{k+1}$. Arguing by contradiction, suppose that $f$ is injective. Consider $f(m) \in I_{k+1}$. Since $f$ is injective, the restriction $f | I_{m-1}$ is also injective, and the image of $f | I_{m-1}$ is contained in the set $I_{k+1}-\{f(m)\}$. There is a bijection 
$$g : I_{k+1}-\{f(m)\} \to I_k
$$
given by the formula
$$g(i) = \begin{cases} j & \quad \text{if $1 \le j < f(m)$} \\
   j-1 &\quad\text{if $f(m)<j\le k+1$}
\end{cases}
$$
We thus obtain an injection $g \circ (f | I_{m-1}) : I_{m-1} \to I_k$, contradicting the induction hypothesis.
