# Proving multiplication is commutative

Having some issues with this proof. Assume we've already proven addition, etc.

Definition of multiplication:

$a \times S(b) = a \times b + a$ (the "definition of multiplication")

$a \times 0 = 0$ (the "zero property of multiplication")

First, some supporting proofs:

Claim: $0 \times a = 0$

Base Case: We induct on $a$. Let $a=0$. See that $0 \times 0 = 0$ by definition of zero property of multiplication.

Inductive Step: Suppose $0 \times a = 0$. We must show that $0 \times S(a) = 0$. By definition of multiplication we have $0 \times S(a) = 0 \times a + 0 = 0 \times a$ which is just $0$ by the inductive hypothesis.

Claim: $a \times b = b \times a$

Base Case: We induct on $a$. Let $a=0$. See that $0 \times b = 0 = b \times 0$ by zero property of multiplication.

Inductive Step: Suppose $a \times b = b \times a$. We must show that $S(a) \times b = b \times S(a)$. By definition of multiplication we have $S(a) \times b = a \times b + b$ which is $b \times a + b$ by inductive hypothesis. Then by definition of multiplication $b \times a + b = b \times S(a)$ and we are done.

Now technically I used a proof there I haven't derived yet. But that's where I am having trouble.

Claim: $S(a) \times b = a \times b + b$

Base Case: We induct on $b$. Let $b=0$. See that $S(a) \times 0 = 0 = a \times 0 + 0$ by zero property of multiplication and additive identity.

Inductive Step: Suppose $S(a) \times b = a \times b + b$. We must show that $S(a) \times S(b) = a \times S(b) + S(b)$. By inductive hypothesis we have $S(a) \times S(b) = a \times S(b) + S(b)$ and we are done.

Is this correct? I feel like I am making a mistake somewhere. I only needed to use the inductive hypothesis to get what I needed?

• How did $S(a)×S(b)=a×S(b)+S(b)$ follow from the inductive hypothesis? – Air Conditioner Mar 28 '18 at 13:48
• Maybe I'm missing something, but anyways, what is $S(b)$? Also, when you define multiplication of $a$ by $S(b)$ with $\times$ sign, you make the use that same sign again. Can you please, maybe, share some context for this question? Thank you. – Salech Alhasov Mar 28 '18 at 13:51
• I think it's the successor function – Air Conditioner Mar 28 '18 at 13:51
• $S$ is known as the successor function, basically $S(n) = n + 1$. So $3 \times 3 = 3 \times 2 + 3 = 3 \times 1 + 3 + 3 = 3 \times 0 + 3 + 3 + 3 = 0 + 3 + 3 + 3 = 9$. It's a recursive definition that bottoms out when it reaches $0$ which is why there are two pieces to the definition. – user525966 Mar 28 '18 at 13:51
• This may not be the best way to go about it, but this may work: $S(a)\times S(b)=S(a)\times b+S(a)=a\times b+b+S(a)$(using the definition of multiplication and the inductive hypothesis, respectively). If you can use $b+S(a)=S(b)+a$, this can be rearranged into $a\times b+S(b)+a=a\times b+a+S(b)=a\times S(b)+S(b).$ – Air Conditioner Mar 28 '18 at 14:14

Long comment

Last Claim : the induction is on $b$ with $S(a)$ fixed.

Basis : $b=0$. It's Ok.

Induction hypothesis : $S(a)b=ab+b$ and we want to show that $S(a)S(b)=aS(b)+S(b)$.

Thus: $S(a)S(b)=S(a)b+S(a)$ (by axiom for mult) $=(ab+b)+S(a)$ (by ind.hy.) $=ab+(b+S(a))=ab+S(b+a)=ab+S(a+b)=ab+(a+S(b))=(ab+a)+S(b)=aS(b)+S(b).$

• I had cross-posted an answer of my own -- is my new work correct as well? – user525966 Mar 28 '18 at 14:48

I think it's fixed now:

Claim: $S(a) \times b = a \times b + b$

Base Case: We induct on $b$. Let $b=0$. See that $S(a) \times 0 = 0 = a \times 0 + 0$ by zero property of multiplication and additive identity.

Inductive Step: Suppose $S(a) \times b = a \times b + b$. We must show that $S(a) \times S(b) = a \times S(b) + S(b)$.

\begin{align}S(a) \times S(b) &= S(a) \times b + S(a) \tag{definition of multiplication} \\ &= a \times b + b + S(a) \tag{inductive hypothesis} \\ &= a \times b + S(b + a) \tag{definition of addition} \\ &= a \times b + S(a + b) \tag{commutative property of addition} \\ &= a \times b + a + S(b) \tag{definition of addition} \\ &= a \times S(b) + S(b) \tag{definition of multiplication} \\ \end{align}

• Correct............... – Mauro ALLEGRANZA Mar 28 '18 at 14:51