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
    9
    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
    9
    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
    9
    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, 02:23 PM
  2. Replies: 1
    Last Post: February 13th 2011, 11:03 AM
  3. Replies: 0
    Last Post: May 26th 2008, 09:16 PM
  4. Express in First Order Peano Arithmetic (FOPA)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 9th 2008, 08:35 PM
  5. More peano arithmetic.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 27th 2006, 07:54 AM

Search Tags


/mathhelpforum @mathhelpforum