Let $m; n \in N$ with $m > n$. Then there does not exist an injection from $N_m$ into $N_n$.
We will do this by induction on $n$. Let's formulate the inductive hypothesis $P(k)$ is if $f : N_m \to N_k$ and $m > k$ then $f$ is not an injection.
Base case: $k = 1$: then $f(1)=f(2)=...=f(m)=1$. So, $f$ is not an injection. Inductive step: Suppose, $P(k)$ is true. Let's show that $P(k+1)$ is true.
Let $h: N_m \to N_{k+1}$. We can have $2$ cases:
- case 1: $h(N_m) \subseteq N_k \subseteq N_{k+1}$, then $h$ is not an injection to $N_k$, by our inductive hypothesis. Hence, it is not an injection to $N_{k+1}$.
- case 2: $h(N_m) \not\subseteq N_{k}$. If there are more than one elements in $N_{m}$ that map to $k+1$ then $h$ is not an injection. So, suppose there is only one $p \in N_m$ such that $h(p) = k+1$. We now defined $h_1(i) = h(i)$ if $i = 1, 2, ... p-1$ and $h_1(i) = h(i+1)$ if $i = p, ..., m - 1$. So, that $h_1 : N_{m-1} \to N_k$.
Now it is argued that $h_1$ is not an injection by our induction hypothesis and then it is obvious to see that $h$ is not an injection either. However, I am struggling to see why this is the case. I think, that we can't apply the inductive hypothesis on $h_1$ since we don't know if $m-1 > k$. We only know that $m > k$ since we assumed that $P(k)$ is true. Can you help me to see what I can't see? What is it that I am missing here?
We just need prove: for $\ k = 1,2,3,...,m-1 $,the propositon is true. So $\ k+1 \leq m-1$ , and that means $\ k < m-1 $. ( If $\ k+1 > m-1$, then $\ k \geq m $, which contradicts the precondition.)
And the inductive step should be modified as below:
Suppose for $\ \forall j \leq k, \ P(j)$ is true. Let's show that $\ P(k+1)$ is true.
This is because in case 1 $\ h(N_m) \subset N_k$, so for any subset of $\ N_k$,say $\ N_j(j \leq k)$,there should not exist an injection from $\ N_m$ to $\ N_j$.