Prove a statement using Peano's Axioms

[supermiedos]

Homework Statement

Let, m, n be natural numbers and S(n) the succesor of n.
If S(n)*m = nm + m
Prove that m*S(n) = nm + m

Homework Equations

The Attempt at a Solution

 

[stevendaryl]

Hmm. It seems more straight-forward to prove

$m \cdot S(n) = m \cdot n + m$

 

[supermiedos]

Hmm. It seems more straight-forward to prove

$m \cdot S(n) = m \cdot n + m$

But since S(n)*m = nm + m I'd like to prove that also m*S(n) = nm + m, thus S(n)*m = m*S(n), meaning that nm = mn

 

[stevendaryl]

But since S(n)*m = nm + m I'd like to prove that also m*S(n) = nm + m, thus S(n)*m = m*S(n), meaning that nm = mn

I understand that, but it's easier to prove $m \cdot S(n) = m \cdot n + m$ than it is to prove $m \cdot S(n) = n \cdot m + m$. Then you can use this lemma to prove that $m \cdot n = n \cdot m$.

Suppose that you want to prove that $m \cdot n = n \cdot m$ by induction on $m$.

1. Prove $0 \cdot n = n \cdot 0$
2. Assuming $m \cdot n = n \cdot m$, prove $S(m) \cdot n = n \cdot S(m)$

Sketch:

1. We're trying to prove $S(m) \cdot n = n \cdot S(m)$
2. We can use the rules for multiplication to rewrite the left-hand side: $S(m) \cdot n = m \cdot n + n$.
3. Then we can use our inductive hypothesis to write $m \cdot n = n \cdot m$. So the left hand side becomes: $n \cdot m + n$
4. So switching left and right sides, we need to show: $n \cdot S(m) = n \cdot m + n$. That's true by my "lemma".

 

[supermiedos]

Wait, so in this case we have like "two inductions" into one?

We're assuming that m⋅n = n⋅m
but also we're assuming that n⋅S(m) = n⋅m +n in the same proof?

 

[stevendaryl]

Wait, so in this case we have like "two inductions" into one?

We're assuming that m⋅n = n⋅m
but also we're assuming that n⋅S(m) = n⋅m +n in the same proof?

No, first you prove by induction that $n \cdot S(m) = n \cdot m + n$.

Then you prove by induction that $m \cdot n = n \cdot m$. In the second proof, you assume $m \cdot n = n \cdot m$ and use that to prove $S(m) \cdot n = n \cdot S(m)$.

 

[supermiedos]

No, first you prove by induction that $n \cdot S(m) = n \cdot m + n$.

Then you prove by induction that $m \cdot n = n \cdot m$. In the second proof, you assume $m \cdot n = n \cdot m$ and use that to prove $S(m) \cdot n = n \cdot S(m)$.

Of course. I get it now. Thanks