PartialOrdering, StrictWeakOrdering, TotalOrdering, what's the main difference in application

Question

[SGI official document]

Because of irreflexivity and transitivity, operator< always satisfies the definition of a partial ordering. The definition of a strict weak ordering is stricter, and the definition of a total ordering is stricter still.

And I also read the definition of strict weak ordering in the document: StrictWeakOrdering

The first three axioms, irreflexivity, antisymmetry, and transitivity, are the definition of a partial ordering; transitivity of equivalence is required by the definition of a strict weak ordering. A total ordering is one that satisfies an even stronger condition: equivalence must be the same as equality.

I am not quite sure about these definition. Some main questions:

1.Is partial ordering implicitly define a equivalence?

2.What about strict weak ordering and total ordering?

3.STL require a strict weak ordering in sort algorithms, why isn't partial ordering or total ordering? For this question, I've read some textbooks that prove a valid comparing rules by proving the rule satisfy three axioms: irreflexivity, antisymmetry, transitivity which is the definition for partial ordering, and the document refer that operator< always satisfies this definition, So why can't we just compare objects using partial ordering, or equivalently, using operator

Fescue

Answer 1

Partial ordering is, essentially, <=. If both a <= b and b <= a then you may say that a is equivalent to b. But it's also possible that neither a <= b nor b <= a - the two elements are incomparable. As a result, you cannot impose a total order (like std::sort would need to) on a set with partial ordering relation - at best you can do a topological sort. Nor can you derive an equivalence relation - again, there may be elements that are incomparable.

Strict weak ordering is like <. It doesn't allow having both a < b and b < a, and if neither a < b nor b < a, you can just pronounce a and b equivalent.

Total ordering is simply strict weak ordering where two elements are equivalent if and only if they are equal (which is only meaningful if you have an equality comparison predicate in addition to less-than predicate, and there is no C++ standard library algorithm that uses both at the same time, so the issue is largely moot in this context).

Erle

In the official document, a greater predicate is also claimed a valid strict weak ordering. So the weak here really has nothing to do with less than then? Because you can use > in your application just to represent a <? – Fescue

I didn't literally mean less-than. I meant, "behaves like a less-than as opposed to less-or-equals" (for example, partial ordering relation is reflexive, strict weak ordering relation is irreflexive). Greater-than has all the same properties as less-than, and is equally suitable. – Erle

And one more question, as stated at the end of my question. Say that you defined a new relationship, you are required to prove that can be used in a sorting (topo sorting is not counted), you need at least prove it an strict weak ordering? So besides the 3 axioms as stated in the question, I still need to prove it is transitivity of equivalence? – Fescue

For a predicate to be usable with std::sort and similar, it must be irreflexive, transitive, and the equivalence relation it induces must be transitive (the standard doesn't explicitly require asymmetric, but I believe it can be derived from these properties). Perhaps there exists a different notion of sorting that can get by with fewer requirements; I can't think of one off the top of my head. – Erle

Here's an example of a (seemingly reasonable) relation that breaks the transitivity-of-equivalence rule: bool noticeablyLessThan(double a, double b) {return a < b-epsilon; } The idea is to declare two floating point values that are "close enough" as equivalent. The problem is on the edges: it's possible that a is close enough to b and b to c, but a is not close enough to c. This may break the algorithm used by std::sort. – Erle

Very nice answer in plain English, easy to understand. Thank you! – Fescue