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.
Your proof is essentially correct, but you mixed up the induction hypothesis a bit.
You should have written: Assume that if $k\in n$ there exists a $p$ such that $k+p^+=n$. Now we want to prove it for $k^+$. So let $k^+\in n$. Because of this we have $n=m^+$ such that $k\in m$. By the induction hypothesis we have that there exists a $p$ such that $k+p^+=m$ or $(p^++k)^+=m^+$ (here I used the commutativity of addition) or $p^++k^+=n$ or $k^++p^+=n$.
This proof though, uses commutativity and the fact $k^+\in m^+\Rightarrow k\in m$. To avoid these you can use induction on $n$ (it's a good idea to use induction on the right-most term because of how addition and multiplication are defined):
First of all if $n=0$ it is vacuously true.
Assume that it's true for $n$ and let $m<n^+$. This means that $m=n$ or $m<n$. If $m=n$ then $p=0$ (this is trivial). If $m<n$ then, because of the induction hypothesis there is a $p$ such that $m+p^+=n$. This means that $(m+p^+)^+=n^+$ or (by the definition of addition) $m+(p^+)^+=n^+$, so $p^+$ is the number we are looking for.