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

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

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

4. ## Re: Well-ordering of >

Originally Posted by Timsworth
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.

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