Synopsis
In Exercise 4.23 of Enderton's Elements of Set Theory, we are asked to show that if $m \in n$, $\exists p \in \omega$ for which $m + p^+ = n$.
This seems like an obvious statement, but I wasn't sure how to prove it. I tried something similar to induction, but I wasn't sure how to introduce the condition of $m \in n$.
As such, I decided to search online for some help, and I came across this proof which was very similar to what I had already tried.
In this proof, I follow everything until the very last steps. I will copy and paste @user7805's proof here so it's easier to follow just where I get confused.
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.
The part where I get confused is the last paragraph, where he/she concludes that since $k^+ + q^+ = n$, the conclusion holds for all $m \in n$. I don't really understand how this works. It seems like something satisfying an inductive hypothesis but I don't see a set which we want to show coincides with $\omega$. Also, I don't understand the last two sentences at all with finding $p$ and $q$. How does knowing $0 + n = n$ lead to us being able to find a $p$ such that $1 + p^+ = n$ and a $q$ such that $2 + q^+ = n$? And what does this mean?
Thank you for any help you may give!
Prove : $\forall n(\forall m(m\in n\implies\exists p\in\omega, m+p^+=n))$.
Induction on $n$ :
1.$\ $$n=0$ : $\forall m , m\notin n(=0)$, so $(\forall m(m\in n\implies\exists p\in\omega, m+p^+=n))$ is vacuosly true.
2.$\ $Assume $(\forall m(m\in n\implies\exists p\in\omega, m+p^+=n))$ holds for $n\in\omega$. Let $m\in n^+=n\cup\{n\}$. Then $m\in n$ or $m=n$. If $m\in n, \exists p\in\omega, m+p^+=n$ by induction hypothesis. Then $(m+p^+)+1=n+1\implies m+(p^++1)=n^+\implies m+(p^+)^+=n^+$. If $m=n$, taking $p=0, m+0^+=n+1=n^+$.