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