language-agnosticstrict-weak-ordering

Total, weak, partial orderings - complete definition


What are the differences between


Solution

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

    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:

    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.