9
$\begingroup$

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?

  • 0
    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)$2011-04-20

3 Answers 3

0

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.

  • 0
    Yes, I already proved $1\cdot a=a\cdot 1=a$ for any $a$. But unfortunately I cannot see how this can help me...2011-04-20
8

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.

  • 0
    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 :)2011-04-20
8

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

  • 0
    Glad I could help.2011-04-20