simple proof for principle of pigeons

Question

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?

Answer 1

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

Answer 2

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.