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?

  • $\begingroup$ 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)$ $\endgroup$ – Thomas Andrews Apr 20 '11 at 19:56

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$.

  • $\begingroup$ Glad I could help. $\endgroup$ – yunone Apr 20 '11 at 20:06

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.

  • $\begingroup$ 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? $\endgroup$ – Francesco Turco Apr 20 '11 at 19:10
  • $\begingroup$ @Francesco: I assume that question is resolved by yunone's answer? $\endgroup$ – joriki Apr 20 '11 at 20:06
  • $\begingroup$ 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 :) $\endgroup$ – Francesco Turco Apr 20 '11 at 20:37

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.

  • $\begingroup$ Yes, I already proved $1\cdot a=a\cdot 1=a$ for any $a$. But unfortunately I cannot see how this can help me... $\endgroup$ – Francesco Turco Apr 20 '11 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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