Thread: Well Ordering Property

The Well-Ordering property states that every nonempty set of positive integers has a least element.

This is common sense, but what if you were told to prove that every nonempty set of negative integers has a greatest element.

Is this a suitable proof?:

The statement that every nonempty set of negative integers has a greatest element is true because we can say what that element is. -1 is the greatest negative integer in the set of all positive integers.

____________
Sorry, I'm new to this site and I don't know how to ask a follow up question and have it known that there is a follow up question.

Reply to first response:
The well ordering principal works because the set of all positive integers, an infinite set, has a least element.

Can we use the fact that the set of all negative integers, an infinite set, has a greatest element as proof that every subset of the set of all negative integers must then have a greatest element?

Originally Posted by evthim

The statement that every nonempty set of negative integers has a greatest element is true because we can say what that element is. -1 is the greatest negative integer in the set of all positive integers.

You probably mean that -1 is the greatest negative integer in the set of all negative integers. Even so, it is not true that -1 is an element of every set of negative integers. That is, for every set of negative integers, -1 is an upper bound, but not necessarily a maximum.

My reply didn't show, so I'll submit it again.

The well ordering principal works because the set of all positive integers, an infinite set, has a least element.

Can we use the fact that the set of all negative integers, an infinite set, has a greatest element as proof that every subset of the set of all negative integers must then have a greatest element?

The well-ordering property isn't about having a lower bound, or a greatest lower bound. It's about the fact that that greatest lower bound is in the set.

Compare, the positive rationals have "just as many" elements as the postive integers. And also, any subset A of the postive rationals will have a greatest lower bound. But it's possible that A's greatest lower bound is not in A.
Example: A = positive rationals strictly greater than 1. It's greatest lower bound is 1, but 1 is not in A.

That's the scenario that cannot happen with positive INTEGERS, because the positive integers are well-ordered. If B is a subset of positive INTEGERS, then the greatest lower bound of B is always actually an element of B. That's what well ordering means.

So, yes, -1 is an upper bound on all negative integers, and hence for every subset of the negative integers. But that doesn't prove that the set of negative integers are "well-ordered from above". (They are, but that's not the reason.)

Originally Posted by evthim

The well ordering principal works because the set of all positive integers, an infinite set, has a least element.

No, not every set with the least element is well-ordered.Take the set of negative integers and add a element that is less than all of them.

Originally Posted by johnsomeone

Example: A = positive rationals strictly greater than 1. It's greatest lower bound is 1, but 1 is not in A.

Actually, even the set of rationals greater than or equal to 1 is not well-ordered.

I'm not the expert so I was wondering whether this could pass as a proof?

If A is such a set of negative integers that it doesn't have a greatest element then a set B=-A would be a set of positive integers that it doesn't have a least element which is contradicting to well ordering property.

Yes, because well ordering is a property about subsets. But that wasn't the purpose of my example.

My point was to prove that the positive rationals are not well ordered. To do that, I needed to produce just one subset of the positive rationals that did not contain a least element. The set of rationals strictly greater than 1 does not have a least element. Therefore, the positive rationals are not well ordered (under the usual ordering, of course).

Originally Posted by MathoMan

If A is such a set of negative integers that it doesn't have a greatest element then a set B=-A would be a set of positive integers that it doesn't have a least element which is contradicting to well ordering property.

Yes. You might want to write it out in a little fuller detail if doing it for a class, but that's exactly the right insight. Well done.

Originally Posted by johnsomeone

Yes, because well ordering is a property about subsets. But that wasn't the purpose of my example.

My point was to prove that the positive rationals are not well ordered. To do that, I needed to produce just one subset of the positive rationals that did not contain a least element. The set of rationals strictly greater than 1 does not have a least element. Therefore, the positive rationals are not well ordered (under the usual ordering, of course).

The error that the OP made was not related to checking whether the greater lower or the least upper bound of the whole set is in the whole set. The OP wrote that the every set of negative integers has the greatest element because it is bounded from above by -1. The issue is not whether -1 is in the set of all negative integers (of course it is); the issue is that every subset has to have its own greatest element in that subset.

When you said the following:

Originally Posted by johnsomeone

The well-ordering property isn't about having a lower bound, or a greatest lower bound. It's about the fact that that greatest lower bound is in the set.

I thought that you drew attention to the fact that the greatest lower bound of the whole set must belong to the whole set, but you did not emphasize subsets.

Originally Posted by emakarov

I thought that you drew attention to the fact that the greatest lower bound of the whole set must belong to the whole set, but you did not emphasize subsets.

Yes, you're quite right. I was so interested in emphasizing containment that I forgot to include the opening clause about subsets "for every (non-empty) subset...".

Originally Posted by evthim

The Well-Ordering property states that every nonempty set of positive integers has a least element.
The statement that every nonempty set of negative integers has a greatest element.

I did not respond before now because the university inventory audit system had my computer. I frankly do not follow the replies so far.

The point is that any subset of negative integers contains a greatest term.
Define . Clearly is a set of positive integers.
By well ordering the set contains a least integer, call it .
Show that and for we have