Results 1 to 14 of 14

Math Help - peano arithmetic

  1. #1
    Member
    Joined
    Mar 2006
    Posts
    82

    PLease help me..i am losing all my hairss....

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2006
    Posts
    82
    thank you so much. I will come back tomorrow for more help.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2006
    Posts
    82
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2006
    Posts
    82
    Oh, it is okay, I was being unclear.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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"

    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2006
    Posts
    82
    hi captainblack!!!! ...so glad to see you on..i was waiting


    I understand that I have to use those two axioms...but how....
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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:

    <br />
x+0=0+x<br />
,

    which is true by Lemma A.

    Now suppose for some k that:

    <br />
x+y=y+x<br />

    Now:

    <br />
S(x+y)=x+S(y)<br />

    by Lemma B, also:

    <br />
S(x+y)=S(y+x)<br />

    by assumption, and:

    <br />
S(x+y)=S(y+x)=S(y)+x<br />

    from Lemma B with x and y interchanged.

    Hence we have proven that:

    <br />
x+S(y)=S(y)+x<br />

    which allows us to conclude that for any x:

    <br />
x+y=y+x<br />

    for all y

    RonL

    Proofs of the lemma to follow as I find time
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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:

    <br />
x+0=x=0+x<br />
.

    Now:

    <br />
S(x)+0=S(x)<br />

    from the axiom n+0=n, but:

    <br />
S(x)+0=S(x)=S(x+0)<br />

    from the same axiom, so:

    <br />
S(x)+0=S(x)=S(x+0)=S(0+x)<br />

    by assumption, and:

    <br />
S(x)+0=S(x)=S(x+0)=S(0+x)=0+S(x)<br />

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

    <br />
S(x)+0=0+S(x)<br />

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

    <br />
x+0=0+x<br />
.

    RonL
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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)
    <br />
=S(x) by axiom: n+0=n

    <br />
=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:

    <br />
S(x+S(y))=x+S(S(y))<br />
by axiom: n+Sm=S(n+m).

    Also:

    <br />
S(x+S(y))=S(S(x)+y)<br />
, by supposition.
    <br />
=S(x)+S(y)<br />
, by axiom S(n+m)=n+S(m)
    .

    So we have proven that:

    <br />
x+S(S(y))=S(x+S(y))=S(x)+S(y)<br />

    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)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Mar 2006
    Posts
    82
    I will check it over. Thank you so much Captainblack. You saved me a whooolleeee lot.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Nice job CaptainBlank +rep+
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to write this in first order peano arithmetic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 3rd 2011, 03:23 PM
  2. Replies: 1
    Last Post: February 13th 2011, 12:03 PM
  3. Replies: 0
    Last Post: May 26th 2008, 10:16 PM
  4. Express in First Order Peano Arithmetic (FOPA)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 9th 2008, 09:35 PM
  5. More peano arithmetic.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 27th 2006, 08:54 AM

Search Tags


/mathhelpforum @mathhelpforum