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

Question 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 precisely 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.

Question 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.