I have read a exercise that states as follows;
Use induction to prove that
$\forall n \in \mathbb{N}: \forall m \in \mathbb{N}: n<m \Rightarrow \exists r \in \mathbb{N}: n+r=m.$
Sugestion. Prove that the set $$B=\{n\in\mathbb{N}:\forall m \in \mathbb{N}:n<m \Rightarrow \exists r \in \mathbb{N}: n+r=m\}$$ is inductive.
My attempt was:
- If n=1 and m is a natural such that $1<m$, then $(m-1)$ is a natural number. Now we have that $1 +(m-1)=m$.
- Now suppose that for any fixed n, it follows that is m is a natural number, and if $n<m$, then exist an integer $z_0$ such that $n+z_0=m.$ (inductive hipothese).
- Now we want to prove that for n+1, if m is a natural number, and $n+1<m$, then exist an integer z such that $(n+1)+z=m$.
But we have that $n+1<m$, then $n<m-1$ so for induction hypothese we have that exist z such that $n+z=m-1$ so $(n+1)+z=m$.
BUT I don't know WHY we apply induction on n, and not on m. Is it wrong if I apply induction on m? Do I have to make induction on both n, and m?
Also I want to know if the steps are right please. Im not sure if I stated the hipothese clear enough from the logic.
Thanks for your help.
Hint
The question is a little bit "strange", because usually the formula $\exists x (m=S(x)+n)$ is the definition of $n < m$.
Thus, I suggest a tentative answer, based on induction on $n$.
i) basis : $n=1$
Thus, from $1 < m$, we have that $m=k+1$, for some $k$; thus $\exists r(m=r+1)$.
ii) induction step : assume that it holds for $n$ and prove it for $n+1$.
From $n+1 < m$, we have that $m=k+1$, for some $k$; thus $n+1 < k+1$, i.e. $n < k$.
We apply induction hypotheses to conclude that $\exists r(k=r+n)$, and from $k=r+n$ we have : $m=k+1=(r+n)+1=r+(n+1)$.
From this, we conclude that : $\exists r(m=r+(n+1))$.