1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

TWO properties of order that

  1. Oct 23, 2006 #1
    ..i failed to prove. [real analysis class, we've just begun and we're defining the natural numbers rigoriously as to aid us in proof writing for more difficult concepts later on]

    Let a and b be natural numbers.

    3. If a>= b and b >=a then a = b
    5. a < b if and only if a++ <= b


    For 3, I have:

    Assume a >= b and b >=a. Then by definition of order a = b + m for some natural number m, and b = a + n for some natural number n. Since a >= b, then a = (a+n) + m, which, by associativity, implies a = a + (n+m). By Lemma 1, a = a + 0, thus a + 0 = a + (n+m), so that 0 = (n+m) by the cancellation law. --no idea what to do next, or if i even did things correctly here. I had another idea here but it was circularly reasoned--

    For 5, I have:

    a<b then a++ <= b

    Assume a < b. Then b > a. By definition, b = a + m for some natural number m, provided that b != a. Now we have to show that a++ <= b, or b >= a++. Then, by definition, it would suffice to show that b = (a++) + n for some natural number n. By definition of addition, b = (a+n)++. --stuck here--

    Help?
     
    Last edited by a moderator: Oct 23, 2006
  2. jcsd
  3. Oct 23, 2006 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    what are your order axioms? There are a number of different versions used, write the list down so we can work with the same ones you're using
     
  4. Oct 23, 2006 #3
    we don't have any order axioms--just a definition. we first outlined the peano axioms for the natural numbers, and then postulated the existence of a number system N, whose elements obey the peano axioms. then we defined addition, and derived commutativity, associativity, and the cancellation law. we also defined a natural number m to be positive iff it is not zero, and proved the statments "If a is positive and b is a natural number, then a + b is positive" and "If a and b are natural numbers such that a + b = 0, then a = 0 and b = 0."

    at this point, we defined the following: "Let n and m be natural numbers. We say that n is greater than or equal to m, and write n >= m or m <= n, iff we have n = m + a for some natural number a. We say that n is strictly greater than m, and write n > m or m < n, iff n >= m and n is not equal to m."

    that's all we did thus far. now we were presented with a proposition listing all the basic properties of order, and having the proof relegated to the homework. I'm only clueless about the third and fifth properties above.

    thanks
     
  5. Oct 23, 2006 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Is it possible for the sum of two natural numbers to be zero? In fact, since you are working entirely within the set of natural numbers, do you even have a "0"?

     
  6. Oct 23, 2006 #5
    haha i failed to realize that. well, the sum of two natural numbers can be zero iff both natural numbers are zero and we proved that. and 0 is part of N in my course, at least (see my latest post above yours), as it is the first peano axiom. now that you have reminded me of the fact that two natural numbers equal to zero must both equal to zero, i think i see where the proof should be heading--thanks!

    however, i have absolutely no idea where to even start with the second property.
     
    Last edited by a moderator: Oct 23, 2006
  7. Oct 23, 2006 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Interesting. While Peano originally included 0, most modern treatments of natural numbers start with 1. That' why I asked 'do you even have a "0"?'

    Is "a++" the "next natural number" or "successor function"? Then, by definition of addition, a++= a+ 1, where 1 itself is defined as 0++.
    If b> a then b= n+ a for some non-zero n. It is NOT true, then that b= (a+n)++! You have no idea how large b might be. What is true is that a++= a+1<=a+ n since 1<= n.
     
  8. Oct 23, 2006 #7
    a++ is simply the next natural number--it doesn't redefine a.

    i'm not sure i fully understand what you're saying, though. :( what is not true? that b = n + a for some non-zero n? tiny bit confused from that point onwards.

    ps. that fifth property was equiped with the following hint: "it may be helpful to prove the folowing auxiliary result: every natural number is either equal to zere, or is the successor of a natural number" which i fail to see its value yet, but i'm sure you would instantly recognize its relevence.
     
  9. Oct 23, 2006 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    hallsofivy, it could be that n = 0 (seeing how we just covered that).
     
  10. Oct 23, 2006 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    My mistake. I went back and reread you original post. You said "since a< b, b= a+ m" and then later said that it would suffice to prove b= a++ + n for some n which is the same as b= (a+n)++. I confused n with m!

    Yep. if a< b, then b CANNOT be 0 and so must be the sucessor of some natural number: b= c++ for some c. a< b means a<= c so a++<= c++= b. Now, as to proving that if b is not 0, b= c++ for some c, exactly what version of Peano's axioms are you using. The ones I am used to say:
    The natural number stystem consists of a set of objects, N, called "natural numbers" of course, together with a "successor function" s(n) (your n++) such that there is a unique member of N, called "0" so that
    1) s is a one-to-one, onto, function from N to N\{0}.
    2) If X is a subset of N such that
    a) 0 is in X
    b) whenever n is in X, s(n) is also in X,
    then X= N.
    The "onto" part of (1) immediately implies that every natural number, except 0, is the successor of some natural number.
     
  11. Oct 24, 2006 #10
    Hi again. Thanks for taking the time in helping me through this, HallsofIvy! :)

    Here are the Peano Axioms that we assumed in my course.


    I think I get what you're saying now. I came up with the following proof, but I think I may have missed something:

    b>a iff b >= a++

    We prove the first part: if b>a then b>= a++. Assume b>a. Since b>a, and a is any natural number, then b can be denoted as c++ (b := c++), ie. b can't be zero by Axiom III. Then c >= a so a++ <= c++, and since c++ = b, then b >= a++ as desired. Now for the second part (if b>= a++, then b>a), assume b >= a++. Then by definition, b = (a++) + m for some natural number m, and by definition of addition, b = (a+m)++. b can't be zero by Axiom III, so b can be denoted as c++ for some natural number c. Then c>=a, so c++ = (a+m)++, which implies c = a+m by the contrapositive of Axiom IV, which leads to c >= a as desired.

    Any holes or circular reasoning? Sorry--still new to this!
     
  12. Oct 25, 2006 #11
    I refined (and corrected) the proof, but I don't think I'm satisfied with it yet.

    We first prove that if a++ <= b, then a < b. Assume a++<=b. Then b >= a++. By definition, b = (a++)+m for some natural number m. By definition of addition, b = (a+m)++. b can't be zero so it is the successor of some number, which we denote as c (b := c++), so b > c (is it obvious enough, or should this be proven?). c++ = (a+m)++, so c = a + m, and therefore c >= a, but since b>c, then b>a (I guess this also needs to be proven?) and we're done.


    Now we prove that if a < b, then then a++ <= b. Assume a<b. Then b > a. Since b > a, then b is not zero, and can be denoted as the successor of some natural number c (b := c++). So b > c, and c++ > a, which implies c >= a (I sort of understand why strict inequality mustn't stay here because we're uncertain whether it really is larger or equal to a, but is this fact obvious enough?). This implies c++ >= a++, which implies b >= a++, and we're done.

    Haha, I guess this begs the question, how logically rigorous should one's proof be? As a beginner I seem to think that every single statement HAS to be proven, but is this always so?
     
    Last edited by a moderator: Oct 25, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?