Can Recursion Define Natural Number Addition?

[evinda]

Hello! (Wave)

For each pair of natural numbers $m \in \omega, n \in \omega$ we define:

$$m+0=m\\m+n'=(m+n)'$$

We fix a $m$ and recursively the operation $m+n$ is defined for any $n \in \omega$.

Knowing for example that $m+0=m$ we can conclude what $m+1$ means.
$$m+1=m+0'=(m+0)'=m'$$
and respectively we have
$$m+2=m+1'=(m+1)'=(m')'$$

Now we can easily verify all the known properties of addition between natural numbers, i.e. if $m \in \omega, n \in \omega, k \in \omega$ then:

• $m+n=n+m$
  $$$$
• $(m+n)+k=m+(n+k)$
  $$$$
• If $m \leq n$ then there is a $l \in \omega$ such that $n=m+l$.

So, can we prove the properties using the above definition? (Thinking)

 

[Evgeny.Makarov]

So, can we prove the properties using the above definition?

You surely cannot prove these properties without this definition!

In fact, proving them requires several applications of induction. For example, commutativity of addition requires three inductions: first you prove $0+n=n$, then $m'+n=(m+n)'$ and finally $m+n=n+m$. In all three cases the proof is by induction on $n$. At least that's how you would do it abstracting away from the definition of the operation $(\cdot)'$ and using only the definition of addition above. That is, if you don't use the particular definition of natural numbers as sets.

 

[evinda]

You surely cannot prove these properties without this definition!

In fact, proving them requires several applications of induction. For example, commutativity of addition requires three inductions: first you prove $0+n=n$, then $m'+n=(m+n)'$ and finally $m+n=n+m$. In all three cases the proof is by induction on $n$. At least that's how you would do it abstracting away from the definition of the operation $(\cdot)'$ and using only the definition of addition above. That is, if you don't use the particular definition of natural numbers as sets.

So if we use the definition of addition do we have to prove that $0+n=n$ and $m'+n=(m+n)'$? (Thinking)

 

[Evgeny.Makarov]

Do you not trust your eyes while reading?

 

[evinda]

Do you not trust your eyes while reading?

I thought that we don't have to prove these two properties, because they are given by the definition.
I asked because you said that we have to prove them... (Blush)

 

[Evgeny.Makarov]

They are not given by the definition.

 

[evinda]

They are not given by the definition.

We are given the following:

For each pair of natural numbers $m \in \omega, n \in \omega$ we define:

$$m+0=m\\m+n'=(m+n)'$$We want to prove for example that $mn=nm$ for any natural numbers $m, n \in \omega$. So why can't we use that $m+0=m$ and $m+n'=(m+n)'$ but we have to prove these two properties?

 

[Evgeny.Makarov]

So why can't we use that $m+0=m$ and $m+n'=(m+n)'$ but we have to prove these two properties?

I never said we have to prove $m+0=m$ and $m+n'=(m+n)'$. Look at post #2 again.

 

[evinda]

I never said we have to prove $m+0=m$ and $m+n'=(m+n)'$. Look at post #2 again.

A ok... I am sorry!

So, with this:

That is, if you don't use the particular definition of natural numbers as sets.

you mean this definition:

For each pair of natural numbers $m \in \omega, n \in \omega$ we define:
$$m+0=0\\m+n'=(m+n)'$$

right?

And so it remains to show by induction that $m+n=n+m$ in order to prove the first property, right?

 

[Evgeny.Makarov]

you mean this definition:

For each pair of natural numbers $m \in \omega, n \in \omega$ we define:
$$m+0=0\\m+n'=(m+n)'$$

right?

No. Please re-read post #2.

And so it remains to show by induction that $m+n=n+m$ in order to prove the first property, right?

No. Please re-read post #2.

 

[evinda]

I am really sorry...So we have to show that it holds for $n=0$, i.e. that $m+0=0+m=m$ that is true by definition, and then we assume that for $m,n \in \omega: m+n=n+m$ and we want to show that $m+n'=n'+m$.

We have that $m+n'=(m+n)'=(n+m)'$ and we want it to be equal to $n'+m$, so we have to prove the equality $(n+m)'=n'+m$.Or am I wrong again? (Sweating)

 

[Evgeny.Makarov]

Or am I wrong again?

Yes, you are. You keep ignoring what I said in post #2 about the need to prove two additional lemmas before proving commutativity. And $0+m=m$ does not hold by definition.

In order not to cater to your tendency to ignore parts of explanations you don't understand, I'll take a time-out for today in this thread. Please use this time to read my explanation, and in case you don't understand something, to explain why it does not make sense to you. I'll come back to this thread tomorrow.

 

[evinda]

Yes, you are. You keep ignoring what I said in post #2 about the need to prove two additional lemmas before proving commutativity. And $0+m=m$ does not hold by definition.

We know that for each pair of natural numbers $m \in \omega, n \in \omega$:
$$m+0=m\\m+n'=(m+n)'$$

We want to show the commutativity between natural numbers.
We know that $m+0=m$ and we want to show that $m+0=0+m$, so it suffices to show that $0+m=m$.
Also we know that $m+n'=(m+n)'$ and we want to show that $m+n'=n'+m$, so it suffices to show that $n'+m=(m+n)'$.
Then it remains to show by induction that $m+n=n+m$.Am I right now?

 

[Evgeny.Makarov]

We want to show the commutativity between natural numbers.

Commutativity of addition on natural numbers.

Also we know that $m+n'=(m+n)'$ and we want to show that $m+n'=n'+m$, so it suffices to show that $n'+m=(m+n)'$.

I did not say anything about $m+n'=n'+m$ or $n'+m=(m+n)'$.

 

[evinda]

I did not say anything about $m+n'=n'+m$ or $n'+m=(m+n)'$.

We want to show the commutativity of addition on natural numbers and we know that $m+n'=(m+n)'$ for any pair of natural numbers $m \in \omega, n \in \omega$.

So that the commutativity of addition on natural numbers holds doesn't it have to hold that $n'+m=m+n'$ ?
Or am I wrong? (Worried)

 

[Evgeny.Makarov]

So that the commutativity of addition on natural numbers holds doesn't it have to hold that $n'+m=m+n'$ ?

Yes, it does. In post #2, I merely suggested an outline of the proof of commutativity that requires two lemmas. This plan does not require you to come up with some response, which you seem to be doing starting with post #3. You can either simply follow it or not. Of course, there are infinitely many other true properties of natural numbers that are related to commutativity in some way.

 

[Evgeny.Makarov]

I am having another look at this thread. You were right in https://driven2services.com/staging/mh/index.php?posts/66182/.

then we assume that for $m,n \in \omega: m+n=n+m$ and we want to show that $m+n'=n'+m$.

We have that $m+n'=(m+n)'=(n+m)'$ and we want it to be equal to $n'+m$, so we have to prove the equality $(n+m)'=n'+m$.

Indeed, when we prove $m+n=n+m$ by induction on $n$, in the inductive step we have to show $m+n'=n'+m$, and this would follow from $(n+m)'=n'+m$. The latter is the same equality (up to switching $m$ and $n$) that I suggested in https://driven2services.com/staging/mh/index.php?posts/66173/. Sorry for missing that.

Also, you need to prove $m+0=0$ by induction on $m$. This is used in the base case of the proof of $m+n=n+m$.

But I hope you see the difference between $(n+m)'=n'+m$ or $(m+n)'=m'+n$ (which is a necessary lemma) from $(n+m)'=n+m'$ (definition) and $n'+m=(m+n)'$ (https://driven2services.com/staging/mh/index.php?posts/66184/).