This is an old exercise I wrote up, but I'm unhappy with my solution. I assume only the basic properties of addition and multiplication for natural numbers as sets.
Assume that $m$ and $n$ are natural numbers with $m$ less than $n$. Show that there is some $p$ in $\omega$ for which $m+p^+=n$.
First see that $n\neq 0$, since $m\in n$. If $m=0$, then we can take $0+p^+=p^+=n$, and we know such a $p$ exists since $n$ is nonzero. Now suppose $k\in n$, and that for some $p$, $k+p^+=n$. Since $k\in n$, $k^+\ \underline{\in}\ n$. If $k^+=n$, then the conclusion holds trivially, since $k^+\not\in n$. If $k^+\in n$, then observe that $ k+p^+=(k+p)^+=k^++p=n. $ Since $k^+\neq n$, we have $p\neq 0$, and thus $p=q^+$ for some $q$. Hence $k^++q^+=n$, and thus conclusion holds for all $m\in n$. Essentially, since we know $0+n=n$, we can then find a $p$ such that $1+p^+=n$, and from this we can find a $q$ such that $2+q^+=n$, and so on for all $m\in n$. This must eventually terminate, as $n$ is finite.
But this feels more like an intuitive sketch than a real proof. I feel there should be a way to do this rigorously with induction, since pretty much all early set theory proofs dealing with naturals use induction. I don't know how to set it up though or what to induct on. Could someone show how to actually do this rigorously? Thanks.