Total, weak, partial orderings - complete definition [closed]

Question

What are the differences between

• strict/non-strict ordering,
• weak/non-weak ordering, and
• partial/total ordering?

Adamo

The Wikipedia articles are pretty concise. The C++ standard also gives a nice definition in [lib.alg.sorting]. What, specifically, are you confused about? – Cahra

What's the difference between strict and non-strict? – Adamo

cpp-next.com/archive/2010/02/order-i-say – Sasnett

this doesn't have anything to do with C++ or algorithms. please edit your questions (and then the tags) if you disagree. – Jeepers

@JerryCoffin, it’s here now: web.archive.org/web/20120422220137/http://cpp-next.com/archive/… – Portugal

Answer 1

Let X be a set. An relation < ⊆ X × X is a partial ordering if

• for all x ∈ X, we never have x < x,

• whenever x < y, we never have y < x, and

• whenever x < y and y < z, we have x < z.

A total ordering is a partial ordering with the additional property that for any two x and y, we have pre­cise­ly one of x < y, or y < x, or x = y.

A weak ordering on a set X is (as far as I know) a partial ordering < with the additional property that the induced ordering on the quotient set X / ~ is a total ordering, where [x] = [y] ∈ X / ~ if and only if neither x < y nor y < x hold in X.

In other words, in a partial ordering, some elements can be compared, and if they can be compared, the ordering is consistent. Examples of a partial orderings:

• Proper subsets of a set X, where A < B means A ⊊ B.

• Natural numbers with a < b meaning "a divides b".

• Template specializations in C++.

A total ordering is one where all elements, all at once, form a single, consistent order.

A weak ordering is a total ordering if you're willing to lump several elements together and treat them as equivalent for the purpose of the ordering.

---

The term "strict" refers to the use of "<" as a defining relation, as opposed to "≤". You can see how it would be easy to rewrite all the definitions in terms of ≤, e.g. in a partial ordering we always have x ≤ x, etc.

---

Here are two examples, both of C++ template specializations. Both are partially ordered, of course, but the first is also totally ordered.

Example #1:

template <typename T> struct Foo {};               // A1
template <typename U> struct Foo<U*> {};           // A2
template <> struct Foo<int*> {};                   // A3

These specializations are totally ordered as A3 < A2 < A1, where "<" means "more specialized than".

Example #2:

template <typename T1, typename T2> struct Bar {}; // B1
template <typename U> struct Bar<int, U> {};       // B2a
template <typename V> struct Bar<V, int> {};       // B2b
template <> struct Bar<int, int> {};               // B3

This time, we have B3 < B2b < B1 and B3 < B2a < B1, but B2a and B2b are not comparable.

In C++, this manifests in the following way: If the specialization B3 were not defined, then attempting to instantiate Bar<int, int> would result in a compiler error because there is no unambiguous "most specialized" specialization.

Partially ordered sets can have many "least" elements and "biggest" elements, because those notions can only speak about elements that are comparable. Among B1, B2a and B2b, both B2a and B2b are "least elements", because there is no element that's smaller. Nonetheless there isn't a unique smallest element.

Spicate

To be precise, I think rather than "x = y", it should be "!(x < y) && !(y < x)" (because it's about equivalence, rather than equality). – Cahra

@OliCharlesworth Or perhaps better: ! (x < y) && ! (y < x) defines an equivalence relationship. (For that matter, we should probably replace < with <code><i>op</i></code>, since there's no requirement that the relationship be spelled <, either.) – Jansenism

@JohnnyPauling: I think "strict" refers to the use of < rather than <=. You can imagine the same definitions in terms of <=, e.g. "we always have x <= x", and "in a total order we always have x <= y OR y <= x, and both if and only if x = y". – Spicate

Very precise but not plain English. – Tarrah

@LokiAstari: Feel free to post a conversational explanation :-) – Spicate

@KerrekSB: If I could I would. :-) – Tarrah

@LokiAstari: Well: "Total ordering": everything can be compared with everything else and is either bigger or smaller or the same. "Partial ordering": Some things can be compared and are ordered with respect to each other, but other things are not comparable. – Spicate

@KerrekSB Great answer, clarify me what does the "weak" mean and I'm awarding you all the points! – Adamo

@JohnnyPauling: I'm not 100% sure, but my gut feeling is this: A "weak" ordering is a relation "<" on a set X such that the induced relation on the quotient set X / ~ is a total ordering, were x ~ y if and only if neither x < y nor y < x hold. In other words, if you consider any two elements where neither is smaller than the other to be the same, then up to that equivalence you have a total order. – Spicate

For example, consider the set of integers with the relation that x is related to y if and only if x / 10 < y / 10 (with integer division). That's a weak ordering in which all elements that agree on all but the last digit are considered equivalent. – Spicate

I've amemnded the post. – Spicate

I wonder whether the partial ordering of class template specialization is really a formal partial order. Would be nice if you would put a proof :) – Jeepers

@JohannesSchaub-litb: You mean a proof that "is base of" is a partial ordering relation? Left to the reader, I'd say :-) – Spicate

Answer 2

Simply, a strict weak ordering is defined as an ordering that defines a (computable) equivalence relation. The equivalence classes are ordered by the strict weak ordering: a strict weak ordering is a strict ordering on equivalence classes.

A partial ordering (that is not a strict weak ordering) does not define an equivalence relation, so any specification using the concept of "equivalent elements" is meaningless with a strict weak ordering. All STL associative containers use this concept at some point, so all these specifications are meaningless with a strict weak ordering.

Because a partial ordering (that is not a strict weak ordering) does not defines any strict ordering, you cannot "sort elements" in the common sens according to partial ordering (all you can do is a "topological sort" which has weaker properties).

Given

• a mathematical set S
• a partial ordering < over S
• a value x in S

you can define a partition of S (every element of S is either in L(x), I(x) or G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

A sequence is sorted according to < iff for every x in the sequence, elements of L(x) appear first in the sequence, followed by elements of I(x), followed by elements of G(x).

A sequence is topologically sorted iff for every element y that appears after another element x in the sequence, y is not less than x. It is a weaker constraint than being sorted.

It is trivial to prove that every element of L(x) is less than any element of G(x). There is no general relation between elements of L(x) and elements of I(x), or between elements of I(x) and elements of G(x). However, if < is a strict weak relation, than every element of L(x) is less than any element of I(x), and than any element of I(x) is less than any element of G(x).

If < is a strict weak relation, and x<y then any element of L(x) U I(x) is less then any element I(y) U G(y): any element not greater than x is less than any element not less that y. This does not hold for a partial ordering.

Antioch