Results 1 to 5 of 5

Math Help - Well-ordering of >

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    10

    Well-ordering of >

    I've been having problems understanding the idea of 'greatest' and 'maximal' elements of an ordered set in general for a bit, and I thought I'd figured it out until some apparent inconsistencies have shown themselves today.

    The way I understand them is that for an arbitrary order R, the maximal element is any element (can be more than one) m of the domain of the order where, for all other elements x of the domain, m R x holds.

    Similarly for the greatest element but m must be unique.

    This has given me the standpoint that the greatest element of any arbitrary total order R is the first such x where x R y holds and therefore holds for all other elements of the domain by transitivity i.e. the greatest element of the < strict total order is 0 since 0 holds for all other elements of the domain; it can be applied to more elements of the domain than any other element of the domain.

    Is this route of thinking correct?

    This is the problem that I started thinking about that made me doubt my understanding:

    Is the standard strict total order > (understood as greater than) well-ordered? I'm thinking yes because for every subset, there is a >-least element e.g {5,4,3,2,1,0}, {4,3,2,1,0}, where the >-least elements are 0 and 0 respectively. Even the case {inf,inf-1,inf-2,...} seems as if it would terminate since it's descending down to 0, and hence its own >-least element would also be 0. But with this understanding, does that then mean that < is not well-ordered, since it appears that not every subset has a <-least element e.g. {0,1,2,...}?

    If I've been too vague, I'll try to clarify my problem, just let me know.

    Cheers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,881
    Thanks
    697

    Re: Well-ordering of >

    Hey TimsWorth.

    Not all sets are well-ordered: well-ordering requires a least element.

    For example the natural numbers are well ordered but the normal integers are not (even though you can create a mapping that generates the integers from the naturals).

    Any set regardless of what it is and how it was created (either through property specifications and constraints or through set-theoretic operations like unions and intersections) is not well ordered if it doesn't have a least element.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    10

    Re: Well-ordering of >

    That's how I was thinking about it before. As in, a well-ordered set is a set where every non-empty subset has a least element in the traditional sense. I think my understanding of what it means to be a least element in the general case is halting my progress here.

    However, is my understanding of a greatest/maximal element with respect to arbitrary orderings correct (and then dually for <-least)?
    That is, with the example of <-greatest being 0 rather than nothing (infinity), because it's the one element that holds for all other elements by transitivity. The next greatest would be 1, then 2 etc.

    I suppose it's another way of asking, or even pondering whether the requirement for a set to be well-ordered is that its elements range over the domain of the natural numbers. Can a set of names be well-ordered if it's ordered lexicographically? e.g. is {adder,bird,cat,dog} well-ordered, since all non-empty subsets appear to have a 'least' element in terms of spelling? Are we relying on an intuitive notion of 'least' rather than any specific general definition?

    Cheers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,824
    Thanks
    1717
    Awards
    1

    Re: Well-ordering of >

    Quote Originally Posted by Timsworth View Post
    However, is my understanding of a greatest/maximal element with respect to arbitrary orderings correct (and then dually for <-least)?
    That is, with the example of <-greatest being 0 rather than nothing (infinity), because it's the one element that holds for all other elements by transitivity. The next greatest would be 1, then 2 etc.
    I suppose it's another way of asking, or even pondering whether the requirement for a set to be well-ordered is that its elements range over the domain of the natural numbers. Can a set of names be well-ordered if it's ordered lexicographically? e.g. is {adder,bird,cat,dog} well-ordered, since all non-empty subsets appear to have a 'least' element in terms of spelling? Are we relying on an intuitive notion of 'least' rather than any specific general definition?
    Any set can be well ordered. The problem is however, we do not know what that well ordering looks like (i.e. it may not be the usual order).

    Now any finite set can be well ordered in any way you wish to do it.

    Yes, well order is defined as an order on a set such that each non-empty subset has a first term.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    Posts
    10

    Re: Well-ordering of >

    I think I see now, cheers.

    Is there some sort of [SOLVED] tag that I need to insert into the thread name? If so, I have no idea how to do it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ordering of a set
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 18th 2012, 06:44 AM
  2. Well Ordering
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: September 8th 2010, 04:04 AM
  3. well-ordering
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 10th 2009, 10:24 AM
  4. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 08:13 AM
  5. well ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 17th 2008, 10:16 AM

Search Tags


/mathhelpforum @mathhelpforum