Originally Posted by

**CaptainBlack**

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

To be proven later.

For any natural number x we proceed by induction on y.

Base case:

$\displaystyle x+S(0)=S(x+0)$ by axiom: $\displaystyle n+S(m)=S(n+m)$

$\displaystyle

=S(x)$ by axiom: $\displaystyle n+0=n$

$\displaystyle

=S(x)+0$ by axiom: $\displaystyle n+0=n$

So the base case: $\displaystyle x+S(0)=S(x)=S(x)+0$ is true.

Now suppose for natural number $\displaystyle x$ there exists a natural number $\displaystyle y$ such that:

$\displaystyle x+S(y)=S(x+y)=S(x)+y $

Now:

$\displaystyle

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

$ by axiom: $\displaystyle n+Sm=S(n+m)$.

Also:

$\displaystyle

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

$, by supposition.

$\displaystyle

=S(x)+S(y)

$, by axiom $\displaystyle S(n+m)=n+S(m)$

.

So we have proven that:

$\displaystyle

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

$

which proves the induction step, hence0 with the base case the lemma is proven by induction.

RonL

(You should check this carefully as there is a lot of transcription from scraps

of paper to TeX, which is very prone to error)