Originally Posted by

**jenjen** 0 is a natural number

For every natural number n, its sucessor Sn is a natural number.

For every natural number n, Sn is not equal to 0;

For every natural number n, for every natural number m, if Sn = Sm, then n = m;

The principle of mathematical induction;

For every natural number n, for every natural number m, their sum n + m is a natural number;

For every natural number n, n + 0 = n;

For every natural number n, for every natural number m, n + (Sm) = S(n + m);

For every natural number n, for every natural number m, their product nm is a natural number;

For every natural number n, n0 = 0; and

For every natural number n, for every natural number m, n(Sm) = (nm) + n.

**Using these axioms (and logic), prove the following law of algebra:**

1) For every natural number i, for every natural number j, for every natural number k, ( i + j ) + k = i + ( j + k )

from the other thread :
Lemma A: for all natural numbers $\displaystyle x,\ x+0=x=0+x$

To be proven later

Lemma B: for all natural numbers $\displaystyle x, y,\ x+S(y)=S(x+y)=S(x)+y$

To be proven later.

We will prove that for all $\displaystyle x,\ y,\ z\ \in \mathbb{N}$ that

$\displaystyle

(x+y)+z=x+(y+z)

$

by induction on $\displaystyle x$.

Base case:

For all $\displaystyle y,\ z \in \mathbb{N}$

$\displaystyle

(0+y)+z=y+z$, by Lemma A

$\displaystyle

=0+(y+z)

$, again by Lemma A

.

So the base case is true.

Induction step:

For any $\displaystyle y,\ z \in \mathbb{N}$, suppose there exists a $\displaystyle x$ such that:

$\displaystyle

(x+y)+z=x+(y+z)

$

Now look at the successor of the LHS:

$\displaystyle

S((x+y)+z)=S(x+y)+z=(S(x)+y)+z

$ double application of Lemma B

Now look at the successor of the RHS:

$\displaystyle

S((x+(y+z))=S(x)+(y+z)

$ again by Lemma B

So: $\displaystyle (S(x)+y)+z=S(x)+(y+z)$, so we have proven asociativity

for $\displaystyle S(x)$ from its assumption for $\displaystyle x$ which completes the induction step.

Hence for all $\displaystyle x,\ y,\ z \in \mathbb{N}$ we have proven:

$\displaystyle

(x+y)+z=x+(y+z)

$

by induction on $\displaystyle x$

RonL