Strict weak order

A strict, weak order is an order relation that allows several objects of the same kind, but otherwise defines a clear sequence.

Example: Relation A costs less than B is a strict, weak order: Two or more different objects can cost the same, but otherwise it is always clear which object costs less.

Mathematical definition

A strict weak order < is a strict order in which negative transitivity also applies:

${\displaystyle a\not <b\land b\not <c\Rightarrow a\not <c}$

Example: If milk costs no less than bread and bread no less than cake, then milk costs no less than cake either.

From this it follows in particular that the relation

${\displaystyle a\sim b:=a\not <b\land b\not <a}$

is an equivalence relation, because in a strict order the following applies:

(Reflexivity)

${\displaystyle a\not <a}$, so ${\displaystyle a\sim a.}$

It follows directly from the definition:

(Symmetry)

${\displaystyle a\sim b\Rightarrow b\sim a}$,

and for:

(Transitivity)

${\displaystyle a\sim b\land b\sim c}$,

so

${\displaystyle a\not <b\land b\not <a\land b\not <c\land c\not <b}$

applies because of the negative transitivity

${\displaystyle a\not <c\land c\not <a}$,

or

${\displaystyle a\sim c}$

The strict, weak order induces a strict total order on the equivalence classes of this relation.

In the example: "A costs no less than B and B costs no less than A" is an equivalence relation: "A and B cost the same". The equivalence classes contain all products with the same price, and the strict total order induced on them is simply the order of prices.

If < is also a strict total order, then the equivalence relation is equality. ${\displaystyle \sim }$

The complement of a total quasi-order is a strict weak order, and vice versa.

The associated non-strict relation is called the preference relation (see preference ). A preference relation is therefore a partial order for which it applies that the relation “x = y or x, y are incomparable” is an equivalence relation. Every strict weak order induces a preference relation (as just described), and every preference relation, conversely, induces a strict weak order. ${\displaystyle x\leq y\Leftrightarrow x<y\vee x=y}$ ${\displaystyle \leq }$

Construction of strict weak orders

Every strict total order is a strict weak order. In addition, one can construct further strict weak orders from strict weak orders according to the following rules:

• If one has a mapping and the strict weak order is defined on the set , then the order is also a strict weak order. ${\displaystyle f\colon A\rightarrow B}$ ${\displaystyle B}$ ${\displaystyle <_{B}}$ ${\displaystyle {<_{A}}:=\{(a,b)\in A\times A:f(a)<_{B}f(b)\}}$

Examples:

• Amounts of money are subject to a strict total system . The price is a function that maps the amount of goods to the amount of monetary amounts (each commodity is assigned a monetary amount, the price of the commodity). The associated relation is (costs less than) a strict weak order. ${\displaystyle <_{B}}$ ${\displaystyle <_{A}}$
• Selecting an element from a tuple is also a function. A strict weak order on this element thus also provides a strict weak order on the tuples. How to get z. B. from the alphabetical order of names to an order of addresses by name.

• Are and strict weak orders on , so is a strict weak ordering. ${\displaystyle <_{1}}$ ${\displaystyle <_{2}}$ ${\displaystyle A}$ ${\displaystyle {<}:=\{(a,b)\in A\times A:a<_{1}b\lor (b\sim _{1}a\land a<_{2}b)\}}$

Example:

If the alphabetical order is on the surname and the alphabetical order on the first name, the usual order is on the name: First the surname is compared, if the surname is the same, the first name. ${\displaystyle <_{1}}$ ${\displaystyle <_{2}}$ ${\displaystyle <}$

An extension of this rule to lists of any length results in the lexicographical order . This provides, for example, the alphabetical order of the words from the order of the letters.

application

The usual sorting methods work not only for total orders, but also for strict weak orders. A distinction is made between stable and unstable sorting processes: Stable sorting processes do not change the order of equivalent elements when sorting, unstable sorting processes can change them.

Example: On the set of all words, the relation A has fewer letters than B is a strict weak order. Now lies the unsorted list

Hund Katze Maus Elefant Nashorn Vogel

before, a stable sorting algorithm always delivers for this relation

Hund Maus Katze Vogel Elefant Nashorn

while an unstable sorting algorithm also z. B.

Maus Hund Vogel Katze Nashorn Elefant

can deliver.

Further examples

In Newtonian physics , the causal order (time order) of events forms a strict weak order. Equivalent events with regard to the time order are mentioned at the same time . In the theory of relativity this no longer applies.