Proving the Properties of Order in Natural Numbers: A Beginner's Guide

[johnnyp]

..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++ <= bFor 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?

 

[Office_Shredder]

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

 

[johnnyp]

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 statements "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

 

[HallsofIvy]

..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.

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"?

--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?

 

[johnnyp]

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"?

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.

 

[HallsofIvy]

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"?'

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

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.

 

[johnnyp]

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.

 

[Office_Shredder]

hallsofivy, it could be that n = 0 (seeing how we just covered that).

 

[HallsofIvy]

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.

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!

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.

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.

 

[johnnyp]

Hi again. Thanks for taking the time in helping me through this, HallsofIvy! :)

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

Axiom I -- 0 is a natural number
Axiom II -- if n is a natural number, n++ is also a natural number
Axiom III -- 0 is not the successor of any natural number
Axiom IV -- Different natural numbers must have different successors
Axiom V -- Principle of Induction -> 0, n, n++ (simplified, but you get the idea)

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!

 

[johnnyp]

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?