Let $n$ and $m$ be two natural numbers. Show that if there is an injection from $n$ into $m$ then $n\leq m$. Definition. A set is said to be finite if there is a bijection between this set and some natural numbers.
Question. Let $n$ and $m$ be two natural numbers. Show that if there is an injection from $n$ into $m$ then $n\leq m$.
Proof. By induction on $n$. If $n=0$, it is trival.  Assume for $n$ holds. Then, we will show that $n+1$ holds.  Now, let $f:n+1\rightarrow m$ be an injection. Then, we can say that there is an injection such that $f:n\rightarrow m$. Hence, $n=m$ or $n<m$. Assume $n=m$. So, $f:n+1\rightarrow n$ is an injection. Then, we must find a contruduction. 
My question is: how can I find?
 A: Hint: You can prove (again) by induction that there is no injection from $\{1, \ldots, n+1\}$ to $\{1, \ldots n\}$. You just have to construct an injection between smaller sets. For that you can prove also the following lemma:
Lemma: There exists a bijection between $\{1, \ldots, n-1\}$ and $\{1, \ldots, n\}-\{x\}$ for all $x \in \{1, \ldots, n\}$.
A: However, there is a bijection $id : n \to n$. Since $n+1=n \cup \{n\}$, $n$ is a strict subset of $n+1$ (since $n \notin n$), so there is a bijection between a strict subset of $n+1$ and $n$. Since $n+1$ is finite, this means there can not possibly be an injection between $n+1$ and $n$, so we have a contradiction.
A: To prove if there is an injection from $\mathbb N_n$ to $\mathbb N_m$, then $n \leq m$:   
$(1)$ For $n =k+1$:  Suppose that $j: \mathbb N_{k+1} \to \mathbb N_m$ is an injection. Since, $ k+1 \geq 2$, it follows that $ m\neq 1$. So, $m = a+1$ for some natural number $a$. To show that $k+1\leq m =a+1$, we construct an injection $j^*: \mathbb N_k \to \mathbb N_a$ and use the induction hypothesis to conclude that $k\leq a$. There are two cases:   
Case $1$: Suppose that $j(x) \neq a+1 \forall x \in \mathbb N_k$. Then we let $j^*$ be the injection defined by $j^*(x) = j(x)$ for all $x\in \mathbb N_k$.    
Case $2$: Suppose that there is an $x \in \mathbb N_k$, such that $j(x) = a+1$. Then $j(k+1) = y$, where (since $j$ is an injection), $y \neq a+1$. In this case, define $j^*$ as: $$ j^*(x) = y, \space\space j^*(z) = j(z) \space\space\space (j\neq x)$$ It is easy to check $j^*$ is an injection. The proof then follows. Hope it helps.     

Reference: Discrete Mathematics, by Norman Biggs (pg. $47-48$)
