0
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ How did $S(a)×S(b)=a×S(b)+S(b)$ follow from the inductive hypothesis? $\endgroup$ – Air Conditioner Mar 28 '18 at 13:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Salech Alhasov Mar 28 '18 at 13:51
  • 1
    $\begingroup$ I think it's the successor function $\endgroup$ – Air Conditioner Mar 28 '18 at 13:51
  • $\begingroup$ $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. $\endgroup$ – user525966 Mar 28 '18 at 13:51
  • 1
    $\begingroup$ 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).$ $\endgroup$ – Air Conditioner Mar 28 '18 at 14:14
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I had cross-posted an answer of my own -- is my new work correct as well? $\endgroup$ – user525966 Mar 28 '18 at 14:48
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Correct............... $\endgroup$ – Mauro ALLEGRANZA Mar 28 '18 at 14:51

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.