Total, weak, partial orders - full definition

Question

What's the difference between

• strict / non-strict order,
• weak / weak order and
• partial / full ordering?

Answer 1

Let X be a set. The ratio <& Subseteq; X & times; X is a partial order if

• for all x & in; X, we never have x <x,

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

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

Full ordering is a partial ordering with the additional property that for any two x and y we have pre & shy; cise & shy; ly is one of x <y, or y <x or x = y.

Weak ordering on the set X (as far as I know) partial ordering <with the additional property that the induced ordering on the factor set X / ~ is the full order, where [x] = [y] & in; X / ~ if and only if neither x <y nor y <x are held in X.

In other words, with partial ordering, some elements can be compared, and if they can be compared, ordering is consistent. Partial ordering examples:

• Own subsets of the set X, where A <B means A & subsetneq; B.

• Natural numbers with <b means "divides b".

• Specialization of templates in C ++.

Complete ordering is where all the elements, all at once, form a single sequential order.

Weak ordering is a complete ordering if you are ready to combine several elements together and consider them equivalent for ordering purposes.

---

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

---

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

Example # 1:

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

These specializations are fully 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 itself as follows: if the B3 specialization has not been defined, an attempt to create an instance of Bar<int, int> will lead to a compiler error, because there is no unique "specialized" specialization.

Partially ordered sets can have many "least" elements and "largest" elements, because these concepts can only speak of comparable elements. Among B1, B2a and B2b, both B2a and B2b are the “smallest elements” because there is no smaller element. However, there is no unique smallest element.

Answer 2

Just a strict weak ordering is defined as an ordering that defines a (computable) equivalence relation . Equivalence classes are ordered by strict weak ordering: strict weak order - strict order on equivalence classes.

Partial ordering (not strict weak ordering) does not define an equivalence relationship; therefore, any specification using the concept of "equivalent elements" does not make sense with strict weak ordering. All STL associative containers use this concept at some point, so all of these specifications do not make sense with a strict weak order.

Since partial ordering (not a strict weak order) does not determine a strict order, you cannot “sort the elements” in the general sense according to partial ordering (all you can do is “topological view”, which has weaker properties).

Considering

• math set S
• partial order < over S
• x value in S

you can define a partition S (each 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 

The sequence is sorted according to < iff for each x in the sequence, the elements from L(x) appear first in the sequence, followed by the elements I(x) , followed by the elements G(x) .

A sequence is topologically sorted if, for every element y that appears after another element x in the sequence, y at least x . This is a weaker restriction than sorting.

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

If < is a strict weak relation, and x<y , then any element of L(x) UI(x) smaller than any element I(y) UG(y) : any element not exceeding x is smaller than any element, t216>. This is not done for partial sequencing.