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.

I'm trying to prove that $a\cdot b=b\cdot a$ when $a$ and $b$ are two natural numbers.

In the rest of this question I'm using $a'$ for the successor of $a$.

Addition is defined as:

  • $a+0=a$
  • $a+b'=(a+b)'$

Multiplication is defined as:

  • $a\cdot 0=0$
  • $a\cdot b'=a+ab$

I already proved commutativity and associativity for addition. I also proved that $a\cdot 1=1\cdot a=a$.

I tried with induction on $b$. I can easily show that $a\cdot 0=0\cdot a$. Then I suppose $a\cdot b=b\cdot a$ and try to show that $a\cdot b'=b'\cdot a$.

Here I can no longer go on. The main problem is I can't use distributivity laws since I haven't proved them yet. I hope to do that immediately after this problem is fixed. Also, $b'\cdot a$ is problematic because $b'$ is at the left.

Any hints?

share|improve this question
    
Proof distributive law first. In a sense, the distributive law is more "basic" because we will often want it to be true when we don't have commutativity. So First show that $a\cdot(b+0)=(a\cdot b) + (a\cdot 0)$ then proof the general case. Not sure if you'll also need to show right-distributivity: $(a+b)\cdot c=(a\cdot c) + (b\cdot c)$ –  Thomas Andrews Apr 20 '11 at 19:56
add comment

3 Answers

up vote 7 down vote accepted

This is how I would go about it, in three steps.

  1. Prove $0=m\cdot 0=0\cdot m$ for all $m\in\omega$. As you said, you can easily show this.

  2. Prove $m'n=mn+n$ for all $m,n\in\omega$. We can do this by induction. Let $$ K=\{n\in\omega\ |\ m'n=mn+n\} $$ By definition, $m'\cdot 0=0$, and $m\cdot 0+0=0+0=0$, so $0\in K$. Suppose $n\in K$. Then $$ m'n'=m'+m'n=m'+mn+n=m+mn+n'=mn'+n' $$ where I have used the second facts you listed for addition and multiplication, and I assume you know $a'+b=(a+b)'=a+b'$, which is usually used in proving the commutativity of addition. So $n'\in K$.

  3. We can now prove $mn=nm$ for all $m,n\in\omega$. Let $S=\{m\in\omega\ |\forall_{n\in\omega}\ mn=nm\}$. By Step 1, $0\in S$. Let $m\in S$. Then $$ m'n=mn+n=nm+n=n+nm=nm' $$ so $m'\in S$, so $S$ is inductive, and $S=\omega$.

share|improve this answer
    
Thank you yunone! –  Francesco Turco Apr 20 '11 at 20:02
    
Glad I could help. –  yunone Apr 20 '11 at 20:06
add comment

Assume commutativity of the products $ab$, $ab'$ and $a'b$. Then you can rewrite $b'a'$ and $a'b'$ in terms of $a$, $b$ and $ab$ using commutativity and associativity of addition and the induction hypothesis to show that they are equal. I'll be happy to provide more details, but you asked for hints.

share|improve this answer
    
If I assume $ab=ba$, $ab'=b'a$ and $a'b=ba'$ I can prove that $a'b'=b'a'$ the way you said, but I don't get how I can apply this fact to my initial problem. Can you provide some more details, please? –  Francesco Turco Apr 20 '11 at 19:10
    
@Francesco: I assume that question is resolved by yunone's answer? –  joriki Apr 20 '11 at 20:06
    
yunone completely answered my question. I tried to understand your proof but I failed, probably because I'm a little too tired now. I'll try again tomorrow. Anyway I would be happy if you could elaborate your answer a little bit. And yes, I know, you're right. I only asked for hints. But since I'm a newbie, I should have spoken differently :) –  Francesco Turco Apr 20 '11 at 20:37
add comment

Have you tried proving either associativity or the existence of an identity for multiplication?

(Identity: Define 1 = 0'. Show that 1⋅a = a⋅1 for all a)

I don't see the answer right now, but my guess is that you may need one of these before you can prove commutativity.

share|improve this answer
    
Yes, I already proved $1\cdot a=a\cdot 1=a$ for any $a$. But unfortunately I cannot see how this can help me... –  Francesco Turco Apr 20 '11 at 19:30
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.