Inductive proof that if there is an injection $\mathbb{N_m} \rightarrow \mathbb{N}_n$ then $m\le n$

Question

The statement to prove is:

If there exists an injection $\mathbb{N_m} \rightarrow \mathbb{N}_n$ then $m\le n$

The solution says to prove by induction on $n$.

I just need help on the inductive step:

$P(k): \forall m \in \mathbb{Z}^+(\exists \text{ injection } \mathbb{N}_m\rightarrow \mathbb{N}k) \Rightarrow m \le k$

$P(k+1): \forall m \in \mathbb{Z}^+(\exists \text{ injection } \mathbb{N}_m\rightarrow \mathbb{N}_{k+1}) \Rightarrow m \le k+1$

This can be summarized as:

Given:

• $\forall m \in \mathbb{Z}^+(\exists \text{ injection } \mathbb{N}_m\rightarrow >\mathbb{N}k) \Rightarrow m \le k$,
• $m_1\in \mathbb{Z}^+$, and
• injection $f:\mathbb{N}_{m_1}\rightarrow \mathbb{N}_{k+1}$

We need to show that this implies:

• $m_1 \le k+1$

Case 1 Suppose that $f(i) < k+1 $ for all $i\in \mathbb{N_m}$. Then we can restrict the codomain and define a function $f_1:\mathbb{N}_{m_1}\rightarrow\mathbb{N}_k$ by $f_1(i)=f(i)$. The function $f_1$ is also an injection and so, by inductive hypothesis, $m_1\le k$ and so certainly $m_1\le k+1$ as required.

Case 2 Suppose that $k+1$ is a value of $f$, say $f(i_0)=k+1$ where $i_0\in \mathbb{N}_{m_1}$. In this case we can define an injection $g:\mathbb{N}_{{m_1}-1}\rightarrow \mathbb{N}_{m_1}$ by:

$g(i) = \left\{ \begin{align} i & \text {, for } i<i_0 \\ i+1 & \text{, for } i \ge i_0 \end{align}\right.$

Then, we can define $f_1=f \circ g: \mathbb{N}_{{m_1}-1} \rightarrow \mathbb{N}_k$, which is an injection too. So, by the inductive hypothesis, $m_1-1 \le k$, which means $m_1 \le k+1$, as required.

Questions

1. Given an injection $f:\mathbb{N}_{m_1} \rightarrow \mathbb{N}_{k+1}$. why do we need to break it into the two cases? Do the cases cover all possibilities of $f$ being an injection from $N_\mathbb{m_1}$ to $\mathbb{N_{k+1}}$?

2. It seems the strategy of this is to show that given an injection $f:\mathbb{N}_{m_1} \rightarrow \mathbb{N}_{k+1}$, this implies an injection $f:\mathbb{N}_{x} \rightarrow \mathbb{N}_{k}$, where $x$ a function of $m_1$, which we can then use the induction hypothesis to eventually conclude that $m_1<k+1$, as required. Is my understanding of this proof correct?

3. My attempt:

   Given an injection $f:\mathbb{N}_{m_1} \rightarrow \mathbb{N}_{k+1}$, I will immediately call the induction hypothesis to conclude that $m_1\le k+1$. What is wrong with this answer? Is it because the codomain is different (given injection is $\mathbb{N}_{k+1}$ vs induction hypothesis is $\mathbb{N}_k$)that this kind of reasoning is wrong?

4. Suppose we need to prove:

   For all positive integers $n$, we have the inequality $n\le 2^n$

   Then for the inductive step, the inductive hypothesis is $k\le 2^k$ and we need to prove that this implies $k+1 \le 2^{k+1}$.

   How would the proof for this inductive step look like if the kind of error in point 3 is repeated here?

EDIT:

$\mathbb{N}_m = \{1,2,\dots, m\}$

Answer 1

1. It is a matter of doing things in an orderly manner. Yes, this covers all cases: either the image is contained in $[k]$, or it maps to $k+1$.

2. Induction is made over $k$; not $m$. Careful.

3. This is wrong. Induction is being made over $k$, and your induction hypothesis is that if $[m]\to [k]$ is an injection, $m\leqslant k$. You don't know anything about $k+1$.

4. You're assuming what you want to prove. You would simply say "by induction, $k+1\leqslant 2^{k+1}$; instead of, by induction $k+1\leqslant 2^k+1\leqslant 2^k+2^k=2^{k+1}$.

We may assume $m>1$. Assume the claim proven for every $k\leqslant n$, that is, we have already proven $$P(k)=\text{ if there is an injection }[m]\to [k],m\leqslant k$$ Suppose that we have an injection $[m]\to [n]$. Then $f(1)=j$ for some $j\in [n]$, and we may assume by reordering that $f(1)=1$. Deleting $1$ from each set, we get an injection $[m-1]\to [n-1]$. By induction, $m-1\leqslant n-1$, so $m\leqslant n$.