Proving multiplication is commutative

Question

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?

Answer 1

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

Answer 2

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