# peano arithmetic

• Jul 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
• Jul 24th 2006, 09:09 PM
ThePerfectHacker
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.
• Jul 24th 2006, 09:21 PM
jenjen
thank you so much. I will come back tomorrow for more help.
• Jul 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 \$\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?
• Jul 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 \$\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.
• Jul 25th 2006, 09:13 PM
jenjen
Oh, it is okay, I was being unclear.
• Jul 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
• Jul 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....
• Jul 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 \$\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 :(
• Jul 26th 2006, 02:20 AM
CaptainBlack
Quote:

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
• Jul 26th 2006, 04:39 AM
CaptainBlack
Quote:

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