Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks Apostolos. I've actually proven that commutativity holds as well as $k^+\in m^+\implies k\in m$, thank you for these two options. –  user7805 Mar 4 '11 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.