Results 1 to 11 of 11

Math Help - Well Ordering Property

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    9

    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?
    Last edited by evthim; October 4th 2012 at 01:57 PM. Reason: Replying to Answer
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Well Ordering Property

    Quote Originally Posted by evthim View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    9

    Re: Well Ordering Property

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

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Well Ordering Property

    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.)
    Last edited by johnsomeone; October 4th 2012 at 02:37 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Well Ordering Property

    Quote Originally Posted by evthim View Post
    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.

    Quote Originally Posted by johnsomeone View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13

    Re: Well Ordering Property

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

  7. #7
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

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

  8. #8
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Well Ordering Property

    Quote Originally Posted by MathoMan View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Well Ordering Property

    Quote Originally Posted by johnsomeone View Post
    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:
    Quote Originally Posted by johnsomeone View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Well Ordering Property

    Quote Originally Posted by emakarov View Post
    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...".
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,790
    Thanks
    1687
    Awards
    1

    Re: Well Ordering Property

    Quote Originally Posted by evthim View Post
    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 A of negative integers contains a greatest term.
    Define -A=\{-n|n\in A\}. Clearly -A is a set of positive integers.
    By well ordering the set -A contains a least integer, call it k.
    Show that -k\in A and for \forall n\in A we have n\le -k~.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ordering property of Z
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: January 16th 2012, 03:22 PM
  2. Mean Value Property Implies "Volume" Mean Value Property
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 16th 2011, 08:13 PM
  3. Replies: 1
    Last Post: November 16th 2010, 01:36 AM
  4. Well-Ordering Property
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 27th 2010, 01:06 PM
  5. Well ordering property and induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2009, 05:03 AM

Search Tags


/mathhelpforum @mathhelpforum