Peano axioms and Induction to prove $s(x) \cdot y = x \cdot y + y$

56 Views Asked by At

Using the following axioms

$A1: \forall x \in \mathbb{N}: x + 0 = x$

$A2: \forall x,y \in \mathbb{N}: x + s(y) = s(x+y)$

$M1: \forall x \in \mathbb{N}: x \cdot0 = 0$

$M2: \forall x,y \in \mathbb{N}: x \cdot s(y) = x \cdot y + x$

and the following consequences:

$C1: \forall x,y,z \in \mathbb{N}: (x + y) + z = x + (y + z)$

$C2: \forall x,y \in \mathbb{N}: s(x) + y = s(x +y)$

$C3: \forall x,y \in \mathbb{N}:$ x + y = y + x

I have to prove that:

$\forall x,y \in \mathbb{N}: s(x) \cdot y = x \cdot y + y$

I tried this using induction on $y$:

Base case: $y=0$

$s(x)\cdot 0 = 0$ by $M1$ and $x \cdot 0 + 0 = 0$ by $M1$ and $A1$.

Induction Step

Now $y \to y+1$

$s(x) \cdot (y+1)$. I can not use distributive law here, right? Then how can I proceed from here on?

1

There are 1 best solutions below

0
On

First, remember that $y+1$ is $s(y)$. Indeed, I am sure that the inductive axiom is defined in terms of $s(y)$ instead of $y + 1$.

So, for the inductive step you have to show $s(x) \cdot s(y) = x \cdot s(y) + s(y)$ where you can use the inductive hypothesis (I.H.) that $s(x) \cdot y = x \cdot y + y$

Here's a start: $s(x) \cdot s(y) \overset{M2}{=} s(x) \cdot y + s(x) \overset{I.H.}{=} (x \cdot y + y) + s(x) \overset{C1}{=} x \cdot y + (y + s(x)) \overset{C2}{=} x \cdot y + s(y+x) \overset{C3}{=} x \cdot y + s(x+y)$

... and I'll leave the rest to you