O 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, i + j = j + i

2. The result is true for,
$\displaystyle 0+0=0+0$
Thus there is some $\displaystyle k_i,k_j$ such as,
$\displaystyle k_i+k_j=k_j+k_i$
If and only if,
$\displaystyle S(k_i+k_j)=S(k_j+k_i)$
If and only if,
$\displaystyle S(k_i)+k_j=k_j+S(k_i)$
If and only if,
$\displaystyle k_i+S(k_j)=S(k_j)+k_i$

From the two previous result we have induction.
Proved.

3. thank you so much. I will come back tomorrow for more help.

4. Hi ThePerfectHacker,

Thank you so much for helping me out on this problem, but then I can only use the axioms given to proof the law. Therefore, now I have to proof how you get from $\displaystyle S(k_i+k_j)$ to $\displaystyle S(k_i)+k_j$ and then I have to proof how you get from $\displaystyle S(k_i)+k_j$ to $\displaystyle k_i+S(k_j)$ but I do not know how. Will you please show me?

5. Originally Posted by jenjen
Hi ThePerfectHacker,

Thank you so much for helping me out on this problem, but then I can only use the axioms given to proof the law. Therefore, now I have to proof how you get from $\displaystyle S(k_i+k_j)$ to $\displaystyle S(k_i)+k_j$ and then I have to proof how you get from $\displaystyle S(k_i)+k_j$ to $\displaystyle k_i+S(k_j)$ but I do not know how. Will you please show me?
I was thinking those were part of the given axioms you gave, sorry. I need more time then.

6. Oh, it is okay, I was being unclear.

7. Originally Posted by jenjen
O 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;
This last "axiom" is redundant "addition" is defined by the next two "axioms"

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;
This last "axiom" is redundant "product" is defined by the next two "axioms"

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, i + j = j + i

8. hi captainblack!!!! ...so glad to see you on..i was waiting

I understand that I have to use those two axioms...but how....

9. Originally Posted by jenjen
O 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, i + j = j + i
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.

For any $\displaystyle x$ we proceed by induction on $\displaystyle y$. The base case is:

$\displaystyle x+0=0+x$,

which is true by Lemma A.

Now suppose for some $\displaystyle k$ that:

$\displaystyle x+y=y+x$

Now:

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

by Lemma B, also:

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

by assumption, and:

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

from Lemma B with $\displaystyle x$ and $\displaystyle y$ interchanged.

Hence we have proven that:

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

which allows us to conclude that for any $\displaystyle x$:

$\displaystyle x+y=y+x$

for all $\displaystyle y$

RonL

Proofs of the lemma to follow as I find time

10. Originally Posted by CaptainBlack
Lemma A: for all natural numbers $\displaystyle x,\ x+0=x=0+x$
To be proven later
We proceed by induction on $\displaystyle x$.

Base case: $\displaystyle 0+0=0=0+0$ - trivially true

Now suppose that for some natural number $\displaystyle x$:

$\displaystyle x+0=x=0+x$.

Now:

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

from the axiom $\displaystyle n+0=n$, but:

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

from the same axiom, so:

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

by assumption, and:

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

from the axiom n+(Sm)=S(n+m), so we have proven:

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

which allows us, with the base case, to conclude by induction that for
all natural numbers:

$\displaystyle x+0=0+x$.

RonL

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

12. I will check it over. Thank you so much Captainblack. You saved me a whooolleeee lot.

13. Nice job CaptainBlank +rep+

14. Originally Posted by ThePerfectHacker
Nice job CaptainBlank +rep+
Thank you.

Its satisfying to receive feed back on these, because of the incredible
amount of nit-picking work involved in trying to get them right

RonL