peano arithmetic

• July 24th 2006, 08:52 PM
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
• July 24th 2006, 09:09 PM
ThePerfectHacker
The result is true for,
$0+0=0+0$
Thus there is some $k_i,k_j$ such as,
$k_i+k_j=k_j+k_i$
If and only if,
$S(k_i+k_j)=S(k_j+k_i)$
If and only if,
$S(k_i)+k_j=k_j+S(k_i)$
If and only if,
$k_i+S(k_j)=S(k_j)+k_i$

From the two previous result we have induction.
Proved.
• July 24th 2006, 09:21 PM
jenjen
thank you so much. I will come back tomorrow for more help.
• July 25th 2006, 04:28 PM
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 $S(k_i+k_j)$ to $S(k_i)+k_j$ and then I have to proof how you get from $S(k_i)+k_j$ to $k_i+S(k_j)$ but I do not know how. Will you please show me?
• July 25th 2006, 09:00 PM
ThePerfectHacker
Quote:

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 $S(k_i+k_j)$ to $S(k_i)+k_j$ and then I have to proof how you get from $S(k_i)+k_j$ to $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.
• July 25th 2006, 09:13 PM
jenjen
Oh, it is okay, I was being unclear.
• July 25th 2006, 10:16 PM
CaptainBlack
Quote:

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"

Quote:

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"

Quote:

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
• July 25th 2006, 10:43 PM
jenjen
hi captainblack!!!! :) ...so glad to see you on..i was waiting

I understand that I have to use those two axioms...but how....
• July 26th 2006, 01:19 AM
CaptainBlack
Quote:

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 $x, x+0=x=0+x$
To be proven later

Lemma B: for all natural numbers $x, y, x+S(y)=S(x+y)=S(x)+y$
To be proven later.

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

$
x+0=0+x
$
,

which is true by Lemma A.

Now suppose for some $k$ that:

$
x+y=y+x
$

Now:

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

by Lemma B, also:

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

by assumption, and:

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

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

Hence we have proven that:

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

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

$
x+y=y+x
$

for all $y$

RonL

Proofs of the lemma to follow as I find time :(
• July 26th 2006, 02:20 AM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
Lemma A: for all natural numbers $x,\ x+0=x=0+x$
To be proven later

We proceed by induction on $x$.

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

Now suppose that for some natural number $x$:

$
x+0=x=0+x
$
.

Now:

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

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

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

from the same axiom, so:

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

by assumption, and:

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

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

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

$
x+0=0+x
$
.

RonL
• July 26th 2006, 04:39 AM
CaptainBlack
Quote:

Originally Posted by CaptainBlack

Lemma B: for all natural numbers $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:

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

$
=S(x)+0$
by axiom: $n+0=n$
So the base case: $x+S(0)=S(x)=S(x)+0$ is true.

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

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

Now:

$
S(x+S(y))=x+S(S(y))
$
by axiom: $n+Sm=S(n+m)$.

Also:

$
S(x+S(y))=S(S(x)+y)
$
, by supposition.
$
=S(x)+S(y)
$
, by axiom $S(n+m)=n+S(m)$
.

So we have proven that:

$
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)
• July 26th 2006, 07:50 AM
jenjen
I will check it over. Thank you so much Captainblack. You saved me a whooolleeee lot.
• July 26th 2006, 12:16 PM
ThePerfectHacker
Nice job CaptainBlank +rep+
• July 26th 2006, 09:19 PM
CaptainBlack
Quote:

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 :confused:

RonL