Proof by induction regarding injections and part of the pigeonhole principle Prove the following implication by induction on $m$: 
If there exists an injection $N_m \rightarrow N_n$, then $m \le n$. 
$N_n$ and $N_m$ are sets with $n$ and $m$ elements, respectively.
I know how to do proofs by induction, I'm just struggling with the inductive step. So far I have the predicate P(n) = If there exists an injection $N_m \rightarrow N_n$, then $m \le n$.  
I proved the base case "P(1) = If there exists an injection $N_1 \rightarrow N_n$, then $1 \le n$" sloppily by saying no element in $N_n$ could be assigned to more than one element of $N_1$ because there is only a single element in $N_1$. There must at least one element in $N_n$ in order for it to be a function, so $1 \le n$.
So I know the inductive hypothesis is P(k) = If there exists an injection $N_k \rightarrow N_n$, then $k \le n$. Now I need to prove P(k+1) = If there exists an injection $N_{k+1} \rightarrow N_n$, then $k+1 \le n$, but I'm clueless about how to do this step.
 A: For any $f: N_m \rightarrow N_n$, if $m > n$ then by the Pigeonhole Principle (at least) two elements of $N_m$ must be sent to the same element of $N_n$. Then $f$ is not injective. Now take the contrapositive.
Factoid: (which I think is not well-known?) the Pigeonhole Principle is very similar to the Principle of Mathematical Induction. See, for example, this article. However, criticisms can be found here as well as in The complexity of the Pigeonhole Principle by M. Ajtai, in which PHP is shown to be (in some sense) stronger than PMI.
A: The statement is true for $m=1$: If there is a map $f:\{1\}\to N_n$ then necessarily $n\geq1$.
Assume that the statement is true for  $m\geq1$ and that we are given an injective map $f:\ [m+1]\to [n]$. We have to prove that $m+1\leq n$. We distinguish two cases:
(a) $\quad f(r)\ne n$ for all $r\in[m]$.
In this case restricting $f$ to $[m]$ provides an injective map $f':\ [m]\to[n-1]$. By the induction hypothesis it follows that $m\leq n-1$. Therefore we have $m+1\leq n$ in this case.
(b) $\quad f(r)=n$ for a unique $r\in[m]$.
In this case $f(m+1)<n$. Therefore the new function 
$$f'(k):=\cases{f(k) &$k\in[m], \ k\ne r$\cr f(m+1) &$(k=r)$\cr}$$
is an injective function $f':\ [m]\to[n-1]$. By the induction hypothesis it again follows that $m\leq n-1$, or $m+1\leq n$.
