Proving the Existence of a Greatest Element in a Set

[gnome]

If I'm writing a proof that depends upon the assumption that a set of unique identifiers (integers, names, etc) must have a "greatest" element under some ordering scheme, what do I need in order to be entitled to make that assertion?

 

[Bartholomew]

Of course I am no mathematician but it seems you would want to show there is a unique element x such that x R y for all y in the set and also that there is no z other than x so that z R x, where R is your ordering relation.

 

[gnome]

That's more work than I want to do. I don't want to prove anything about the identifiers. I just want to say something like "it is assumed that the elements of U are unique and there is an ordering scheme such that any subset of U has a greatest element" so that I can use that in a proof of something about some algorithm.

But is there a more formal or "preferred" way to make that assertion?

 

[Bartholomew]

If you want to say any subset of U has a greatest element, I think that's called being well-ordered. But I'm not sure on that; well-ordering might also have some other condition.

 

[gnome]

Thanks, that's more or less what I wrote:
"there is an underlying assumption that each process has a unique identifier (UID) taken from some totally ordered set of identifiers so there is one process with a "greatest" UID."

I do remember reading a definition of a well-ordered set saying that it's a set S, such that every nonempty subset of S has a least element. Nothing explicitly about a greatest element, but it's so obvious that there must be a theorem to that effect.

So hopefully one of the mathematicians will tell me the "scholarly" way to say that.

 

[Bartholomew]

I looked it up in mathworld, there's a lot to well-ordering.

http://mathworld.wolfram.com/WellOrderedSet.html

Not sure exactly the term you're looking for, then. I think, however, that once you say you have a "least element," you can just flip your definitions around and call the same thing a "greatest element," so long as you are ordering the set arbitrarily.

 

[gnome]

Thanks. I should've thought to look there. Based on that I think I can just require that my set of UIDs is well-ordered and therefore has a distinct greatest element. I don't have to prove that any particular set is well-ordered, just that my algorithm will use some arbitrary well-ordered set of unique identifiers. And I think it's obvious enough that since by definition every subset of a well-ordered set has a least element, it also has a greatest element (just keep taking away the least element until there's only 1 left).

 

[honestrosewater]

Why won't the least-upper-bound property work? Just say your sets are all non-empty subsets of a set that has the least-upper-bound property, and they contain their supremum. Wouldn't that work?

 

[mathwonk]

well there are two drawbacks to what you suggest:

1) you would have to prove, not just say, that it is true for your set.

2) the least upper bound propery, even when it is true, does not say what he wants, as a subset, in order to have a lub must be itself bounded, and then the lub may not lie in the subset.

 

[honestrosewater]

well there are two drawbacks to what you suggest:

1) you would have to prove, not just say, that it is true for your set.

2) the least upper bound propery, even when it is true, does not say what he wants, as a subset, in order to have a lub must be itself bounded, and then the lub may not lie in the subset.

Ooh, right. Thanks.