Quasi order

A quasi-order , also pre-order , (English preorder ) is a weakened variant of a partial order , in which it is possible that different elements are comparable in both directions. The antisymmetry does not have to be fulfilled.

Any two-digit relation can be expanded to a quasi-order by forming its reflexive-transitive envelope .

In particular, the total quasi-orders occur in practical applications when arranging objects in sorting processes , spreadsheet programs or databases .

Definitions

Quasi order

4 types of order relations in relation: A B: A is B; A B: A becomes B when the quotient is formed; A B: A becomes B when expanded; A B: A becomes B with a component-wise composition ${\displaystyle {\rightarrow }}$ ${\displaystyle {\color {Green}\downarrow }}$ ${\displaystyle {\color {Red}\uparrow }}$ ${\displaystyle {\color {Blue}\rightarrow }}$

A two-digit relation on a set is called a quasi-order (English preorder ) if it is reflexive and transitive . So must apply to everyone ${\displaystyle \lesssim }$ ${\displaystyle M\ }$ ${\displaystyle a,b,c\in M}$

${\displaystyle a\lesssim a}$	(Reflexivity)
${\displaystyle a\lesssim b\lesssim c\implies a\lesssim c}$	(Transitivity)

One then calls a quasi-ordered set or, for short, a quasi-order. ${\displaystyle (M,\lesssim )}$

Total quasi-order

A quasi-order is called total , also preference order , (English total preorder ), if two elements are always comparable. The following must therefore apply to all : ${\displaystyle a,b\in M}$

${\displaystyle a\lesssim b\;\;\vee \;\;b\lesssim a}$

(Totality)

One then calls a totally quasi-ordered set or, in short, a total quasi-order. ${\displaystyle (M,\lesssim )}$

Partial quasi-order

Reflexivity is no longer required for all elements, but only for those that occur somewhere in the relation.

A two-digit relation on a set is called partial quasi-order (English partial preorder ) if it is reflexive and transitive where it is defined. So must apply to everyone ${\displaystyle \lesssim }$ ${\displaystyle M\ }$ ${\displaystyle a,b,c\in M}$

${\displaystyle a\lesssim b\implies a\lesssim a\;\;\wedge \;\;b\lesssim b}$	(partial reflexivity)
${\displaystyle a\lesssim b\lesssim c\implies a\lesssim c}$	(Transitivity)

One then calls a partially quasi-ordered set or, for short, a partial quasi-order. ${\displaystyle (M,\lesssim )}$

properties

• A partial order (English partial order ) is a quasi-ordering.

• A total ordering (English total order ) is a total quasi-ordering (and also a partial order).

• Every equivalence relation is a quasi-order.

• If there is a quasi-order, then applies to everyone . This property is even characteristic of quasi-orders: every relation with this property is a quasi-order. ${\displaystyle (M,\lesssim )}$ ${\displaystyle a,b\in M}$
        ${\displaystyle a\lesssim b\iff \forall x\in M\colon (x\lesssim a\Rightarrow x\lesssim b)}$
  ${\displaystyle \lesssim }$

• If there is a quasi-order, then exactly then applies if applies to all . ${\displaystyle (M,\lesssim )}$ ${\displaystyle a\lesssim b\wedge b\lesssim a}$ ${\displaystyle x}$
        ${\displaystyle x\lesssim a\iff x\lesssim b}$
  

• When comparing two quasi-ordered elements and there are a maximum of four options: ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle a\lesssim b\wedge b\not \lesssim a}$	${\displaystyle a}$is (really) smaller than . ${\displaystyle b}$
${\displaystyle a\lesssim b\wedge b\lesssim a}$	${\displaystyle a}$is equivalent to (for the antisymmetric quasi-orders : equal) . ${\displaystyle b}$
${\displaystyle a\not \lesssim b\wedge b\lesssim a}$	${\displaystyle a}$is (really) greater than . ${\displaystyle b}$
${\displaystyle a\not \lesssim b\wedge b\not \lesssim a}$	${\displaystyle a}$and are not comparable. ${\displaystyle b}$

The fourth result does not occur in the total quasi-orders - there are a maximum of three options, and one speaks of a trichotomy of the order .

• With a partial quasi-order, the mutual inclusion is a partial equivalence relation , i.e. symmetrical and transitive. ${\displaystyle a\lesssim b\wedge b\lesssim a}$

Examples and counterexamples

• If you compare complex numbers based on their amount , you get a total quasi-order. So the definition is: . This is not a partial order, since, for example, the numbers and are mutually comparable, so and applies. ${\displaystyle a\lesssim b:\Longleftrightarrow |a|\leq |b|}$ ${\displaystyle 1}$ ${\displaystyle \mathrm {i} }$ ${\displaystyle 1\lesssim \mathrm {i} }$ ${\displaystyle \mathrm {i} \lesssim 1}$
• On the set of nodes of a directed graph , a quasi-order is obtained by specifying that there is a directed path from to ( can therefore be reached from). This quasi-order is a partial order if the graph is cycle-free ( acyclic ), i.e. contains no or only trivial cycles . In fact, every finite quasi-order can be obtained from a suitable graph in this way.
  ${\displaystyle a\lesssim b:\Longleftrightarrow }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$
  
  
• The divisibility relation | is a quasi-order on the set of integers . It is not a partial order because, for example, 3 | −3, but also −3 | 3 applies. If one considers the divisibility on the set of natural numbers , the antisymmetry is added, so that there is a partial order.
• If the comparison of ( real or rational ) numbers is subject to a fluctuation range ( measurement deviation , inaccuracy), then it is not a quasi-order, since the associated duplicate relation is not an equivalence relation .
• In contrast, comparing after cutting off decimal or binary digits, or more generally after rounding , is a total quasi-order.
• The norms for alphabetical sorting in German are examples of total quasi-orders, which are not total orders, in the case of upper and lower case letters and the treatment of umlauts.
• The IEEE floating point numbers common on computers are <=a partial quasi-order with the order . It is not fully reflexive because every comparison is wrong for NaN values. Hence there is ==only a partial equivalence relation. It is also not a partial order , because +0.0 == −0.0, therefore, +0.0 <= −0.0and +0.0 >= −0.0applies, but the two are not identical: The calculation 1.0/(+0.0)gives positive infinity and 1.0/(−0.0)negative infinity ; which of course are different.

Induced equivalence relation and strict order

A quasi-ordering on a set produces an equivalence relation - the "canonical" that is to be associated, excellent equivalence relation -   on by setting ${\displaystyle \lesssim }$ ${\displaystyle M\ }$ ${\displaystyle \lesssim }$ ${\displaystyle \sim }$ ${\displaystyle M\ }$

${\displaystyle a\sim b:\Longleftrightarrow a\lesssim b\wedge b\lesssim a}$ .

So two elements are equivalent if they are mutually comparable. For the sake of brevity, this equivalence relation is referred to as the duplicate relation of the quasi-order. If there is already an equivalence relation, this construction creates again  . ${\displaystyle \lesssim }$ ${\displaystyle \lesssim }$

The minor class of is quantity ${\displaystyle a}$

${\displaystyle {\bar {a}}:=\{x\mid x\sim a\}}$ .

Furthermore, one receives the canonical strict order on fortune ${\displaystyle <\ }$ ${\displaystyle M\ }$

${\displaystyle a<b:\Longleftrightarrow a\lesssim b\wedge a\not \sim b}$ .

Is total, then there is a strict weak order . In general, the complement of a total quasi-order is a strict weak order, and vice versa. ${\displaystyle \lesssim }$ ${\displaystyle <\ }$

The following relationship exists between the original relation and the 2 induced relations:

${\displaystyle a\lesssim b\Longleftrightarrow a\sim b\vee a<b\ }$,

where the two conditions on the right are mutually exclusive.

Examples:

• If you compare complex numbers based on their amount (see above), then two numbers are equivalent if and only if their amount is equal. The equivalence classes are therefore the circles around the zero point in the complex plane . A number is “smaller” than a second if it lies on the circle with a smaller radius (radius 0 is permitted).

A directed graph

• With the quasi-order given by a directed graph (see above), two nodes are equivalent if and only if they are the same or lie on a common cycle. It also applies if there is a directed path from to , but no directed path from to . The three equivalence classes in the graph opposite are also the following applies to the induced strict partial order: ${\displaystyle a<b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle \left\{A\right\},\left\{B,C,D,E\right\},\left\{F\right\}.}$ ${\displaystyle A<B,C,D,E<F.}$

• The divisibility relation is also a quasi-order on every integrity ring . Two elements are equivalent (in the sense of the quasi-order) if and only if they are associated , i.e. if they emerge from one another through multiplication with a unit .

Quotient set

On the quotient set or factor set   ( i.e. the set of equivalence classes ) the canonical partial order is obtained through the well-defined definition ${\displaystyle M/\!\sim }$

${\displaystyle [x]\leq [y]:\Longleftrightarrow x\lesssim y}$

(the class of with is designated). ${\displaystyle x\ }$ ${\displaystyle [x]\ }$

If the given quasi-order is total, then the result is a total order .

Examples:

• When comparing complex numbers on the basis of their absolute value (see above), the partial order on the quotient set is isomorphic to the usual (total) order on the non-negative real numbers . ${\displaystyle \leq \ }$
• With the divisibility relation on the whole numbers (see above) the partial order on the quotient set is isomorphic to the divisibility relation on the set of natural numbers (including 0).

reflection

A quasi-order can be mirrored : ${\displaystyle (M,\lesssim )}$

${\displaystyle a\lesssim _{2}b:\Longleftrightarrow \ b\lesssim a\;\;}$(see also inverse relation ).

Usually you then use the notation:

${\displaystyle a\gtrsim b:\Longleftrightarrow \ b\lesssim a}$ .

If the given quasi-order is total, then the result is also total.

If it is a partial order, so is the result.

The reflection of the reflection is the original.

Composition (composition, cascading)

Composition by component

On two quasi-ordered sets and the composition component-wise-less than-or-equal to the set of pairs can be defined as follows: ${\displaystyle (M_{1},\lesssim _{1})}$ ${\displaystyle (M_{2},\lesssim _{2})}$ ${\displaystyle \lesssim _{1}\!\oplus \!\lesssim _{2}}$ ${\displaystyle M_{1}\!\times \!M_{2}}$

${\displaystyle {\left(a_{1},a_{2}\right)}\;\;\lesssim _{1}\!\oplus \!\lesssim _{2}\;\;{\left(b_{1},b_{2}\right)}\;\;\;:\Longleftrightarrow \;\;\;a_{1}\lesssim _{1}b_{1}\wedge a_{2}\lesssim _{2}b_{2}}$

The composition is again a quasi-order. ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\oplus \!\lesssim _{2})}$

Asymmetry is retained. Totality is lost, however, that is, with two total quasi-orders only one quasi-order remains, with two total orders only one partial order remains. (Example: (1,0) is not comparable to (0,1).)

There is a kind of communitativity because is isomorphic to  . ${\displaystyle (M_{2}\!\times \!M_{1},\lesssim _{2}\!\oplus \!\lesssim _{1})}$ ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\oplus \!\lesssim _{2})}$

Lexicographical composition

For two quasi-ordered sets and the lexicographical composition on the set of pairs is defined as follows: ${\displaystyle (M_{1},\lesssim _{1})}$ ${\displaystyle (M_{2},\lesssim _{2})}$ ${\displaystyle \lesssim _{1}\!\otimes \!\lesssim _{2}}$ ${\displaystyle M_{1}\!\times \!M_{2}}$

${\displaystyle {\left(a_{1},a_{2}\right)}\;\;\lesssim _{1}\!\otimes \!\lesssim _{2}\;\;{\left(b_{1},b_{2}\right)}\;\;\;:\Longleftrightarrow \;\;\;a_{1}<_{1}b_{1}\vee (a_{1}\sim _{1}b_{1}\wedge a_{2}\lesssim _{2}b_{2})}$

The composition is again a quasi-order. ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\otimes \!\lesssim _{2})}$

If the given quasi-orders are all total (on their respective component sets) and only then does a total quasi-order arise again. If they are all partial orders, a partial order arises again; if they are total orders, a total order arises again.

The following quasi-orders for symbol sequences ( words ) of variable length can be derived according to the lexicographical principle. To do this, be quasi-ordered and let and be the lengths of two words ${\displaystyle (M,\lesssim )}$ ${\displaystyle l_{a}:=\operatorname {length} (a)}$ ${\displaystyle l_{b}:=\operatorname {length} (b)}$

${\displaystyle a,b\in M^{*}:=\bigcup _{l\in \mathbb {N} _{0}}\underbrace {M\times \dotsb \times M} _{l{\text{-mal}}}}$       ( Kleenesche shell of ) ${\displaystyle M}$

and be . ${\displaystyle m:=\operatorname {min} (l_{a},l_{b})}$

1. Then through is quasi-ordered, whereby for the sake of simplicity the order of the words of   the same length   is written   for     and     for   . M. a. .W .: If the smallest index is with then the following also applies to the empty word as all non-empty words. The order put together in this way is again called lexicographical. It corresponds to the composition of just the same components . ${\displaystyle M^{*}\ }$
         ${\displaystyle a\lesssim \ b\;:\Longleftrightarrow \ \operatorname {left} (a,m)<\operatorname {left} (b,m)\,\,\,\vee \,\,\,{\bigl (}\operatorname {left} (a,m)\sim \operatorname {left} (b,m)\,\wedge \,l_{a}\leq l_{b}{\bigr )}}$
   ${\displaystyle \operatorname {left} (a,m),\operatorname {left} (b,m)}$ ${\displaystyle <}$ ${\displaystyle \sim \!\otimes \!\sim \!\otimes \!\dotsb \!\otimes \!<\!\otimes \,?\otimes \!\dotsb \!\otimes \,?}$ ${\displaystyle \sim }$ ${\displaystyle \sim \!\otimes \!\dotsb \!\otimes \!\sim }$ ${\displaystyle i}$ ${\displaystyle a_{i}\not \sim b_{i},}$ ${\displaystyle a<b\Longleftrightarrow a_{i}<b_{i}.}$ ${\displaystyle <}$
   
         ${\displaystyle (M^{*},\lesssim \!\otimes \dotsb \otimes \!\lesssim )=:(M^{*},\lesssim )}$
   ${\displaystyle (M,\lesssim )}$
2. Another composition with very similar order-theoretical properties is the quasi-lexicographical one with analogous signs for the order of words of equal length.
         ${\displaystyle a\lesssim _{q}b\;:\Longleftrightarrow \ l_{a}<l_{b}\,\,\,\vee \,\,\,{\bigl (}l_{a}=l_{b}\,\wedge \,\operatorname {left} (a,m)\lesssim \operatorname {left} (b,m){\bigr )}}$
   ${\displaystyle \lesssim }$

Associativity

The compositions are associative , that is, and  . ${\displaystyle \oplus ,\otimes }$ ${\displaystyle {\bigl (}(M_{1},\lesssim _{1})\oplus (M_{2},\lesssim _{2}){\bigr )}\oplus (M_{3},\lesssim _{3})\;=\;(M_{1},\lesssim _{1})\oplus {\bigl (}(M_{2},\lesssim _{2})\oplus (M_{3},\lesssim _{3}){\bigr )}}$ ${\displaystyle {\bigl (}(M_{1},\lesssim _{1})\otimes (M_{2},\lesssim _{2}){\bigr )}\otimes (M_{3},\lesssim _{3})\;=\;(M_{1},\lesssim _{1})\otimes {\bigl (}(M_{2},\lesssim _{2})\otimes (M_{3},\lesssim _{3}){\bigr )}}$

Remarks:

1. In the spreadsheet programs , a "column" corresponds to a set of components . The sorting function often offered in these programs corresponds to a lexicographical composition with a precedence of the columns to be specified, whereby there is usually a "standard" order for each column, which is a total (required for sorting!) Quasi-order. The "ascending" or "descending" sort order can be selected. ${\displaystyle M_{i}\ }$
2. If the individual columns are sorted in a stable manner, then the overall sorting can be broken down into individual sortings in the reverse order.

Archetype of an order relation

Let be a non-empty set, a quasi-ordered set and an arbitrary map. Then can fortune ${\displaystyle M_{0}\ }$ ${\displaystyle (M,\lesssim )}$ ${\displaystyle f\colon \,M_{0}\to M}$

${\displaystyle a_{0}\lesssim _{f}b_{0}:\Longleftrightarrow f(a_{0})\lesssim f(b_{0})}$

the set can be quasi-ordered. ${\displaystyle (M_{0},\lesssim _{f})}$

It is totally quasi-ordered, and that's how it is  . ${\displaystyle (M,\lesssim )}$ ${\displaystyle (M_{0},\lesssim _{f})}$

If is a partial order, then a partial order is if and only if is injective . ${\displaystyle (M,\lesssim )}$ ${\displaystyle (M_{0},\lesssim _{f})}$ ${\displaystyle f\ }$

Comment:

• The international Unicode standard has existed for the digital coding of alphabets since 1991, and it seems to be gaining increasing acceptance. This does not say too much about the arrangement of the characters, since in addition to special problems such as umlauts, for example, attention / disregard of upper / lower case and special characters can make the image non- injective.

extension

If there is a quasi-order and any non-empty set, the set can be expanded as follows : ${\displaystyle (M_{1},\lesssim )}$ ${\displaystyle M_{2}\ }$ ${\displaystyle \lesssim }$ ${\displaystyle M_{1}\!\times \!M_{2}}$

${\displaystyle {\left(a_{1},a_{2}\right)}\lesssim _{2}{\left(b_{1},b_{2}\right)}\;\;\;:\Longleftrightarrow \;\;\;a_{1}\lesssim b_{1}}$ .

How is also a quasi-order. ${\displaystyle \lesssim }$ ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{2})}$

If total, the result is again a total quasi-order. ${\displaystyle \lesssim }$

Antisymmetry is generally lost, that is, if the given quasi-order is a partial order (or total order), the result is only again a partial order (or total order) if it consists of exactly one element. If there are several elements, the result is only a quasi-order (or total quasi-order). ${\displaystyle \lesssim }$ ${\displaystyle M_{2}\ }$ ${\displaystyle M_{2}\ }$

${\displaystyle \lesssim _{2}}$is the quasi-order     (with the trivial order on ). It can be thought of as a comparison function that operates on its key fields in . The order of results can therefore be   referred to again with without any loss of accuracy   . ${\displaystyle (\lesssim \!\otimes \,\tau )}$ ${\displaystyle \tau \ }$ ${\displaystyle M_{2}\,}$ ${\displaystyle \lesssim }$ ${\displaystyle M_{1}\ }$ ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim )}$

Composition on the base quantity

If you have several quasi-orders on a set , you can form the lexicographical compositions according to similar to the above ${\displaystyle M}$ ${\displaystyle \lesssim _{1},\lesssim _{2},\ldots }$ ${\displaystyle (M,\lesssim _{1}\!\otimes \!\lesssim _{2}\!\otimes ...)}$

${\displaystyle a\lesssim _{1}\!\otimes \!\lesssim _{2}b\;\;\;:\Longleftrightarrow \;\;\;a<_{1}b\vee (a\sim _{1}b\wedge a\lesssim _{2}b)}$ .

They form a (non-commutative) semigroup with the (both sides) neutral element  . ${\displaystyle \tau }$

${\displaystyle (M,\lesssim _{1}\!\otimes \!\lesssim _{2}\!)}$is a refinement of . This also means that a quasi-order that follows a ( completely total) total order does not change anything. ${\displaystyle (M,\lesssim _{1}\!)}$ ${\displaystyle M}$

Example:

• Let the set of natural numbers, with the (non-injective) Euler's function and the usual smaller relation, then order the total order   ${\displaystyle M:=\mathbb {N} }$ ${\displaystyle \lesssim _{1}\;:=\;<_{\varphi }}$ ${\displaystyle \varphi }$ ${\displaystyle \lesssim _{2}\;:=\;<}$ ${\displaystyle (\lesssim _{1}\!\otimes \!\lesssim _{2})\;=\;(<_{\varphi }\!\otimes \!<)}$

the payment	2,	3,	4,	5,	6,	7,	8th,	9,	10,	11,	12	around
to	2,	3,	4,	6,	5,	8th,	10,	12,	7,	9,	11	because of
	1,	2,	2,	2,	4,	4,	4,	4,	6,	6,	10	for the values. ${\displaystyle \varphi }$

Restriction of a quasi-order

In an obvious way, the restriction to a subset is formed by a quasi-order . ${\displaystyle (M_{1},\lesssim )}$ ${\displaystyle (M_{2},\lesssim )}$ ${\displaystyle M_{2}\subseteq M_{1}}$

Comment:

• The domains of definition are usually conceptually infinite sets. In this respect, statements about the properties of the order relationships (especially about transitivity) can only come from mathematical considerations. The assignments in the IT applications are of course always finite.

Intervals

Similar to numbers, a concept of interval can be introduced more generally for quasi-ordered sets - in a notation that is familiar from school:

${\displaystyle [a,b]}$	${\displaystyle :=\{x\mid a\lesssim x\;\wedge \;x\lesssim b\}}$
${\displaystyle {[}a,b{)}:=\,{[}a,b{[}}$	${\displaystyle :=\{x\mid a\lesssim x\;\wedge \;x<b\}}$
${\displaystyle {(}a,b{]}:=\,{]}a,b{]}}$	${\displaystyle :=\{x\mid a<x\;\wedge \;x\lesssim b\}}$
${\displaystyle (a,b):=\,{]}a,b{[}}$	${\displaystyle :=\{x\mid a<x\;\wedge \;x<b\}}$

Then the duplicate class of is  . ${\displaystyle a}$ ${\displaystyle {\bar {a}}=[a,a]=:[a]}$

For improper intervals there are the notations:

${\displaystyle {[}a,\;{)}\;:=\,{[}a,\;{[}}$	${\displaystyle :=\,\{x\mid a\lesssim x\}}$
${\displaystyle (a,\;)\,:=\,{]}a,\;{[}}$	${\displaystyle :=\,\{x\mid a<x\}}$
${\displaystyle {(}\;,a{]}\;:=\,{]}\;,a{]}}$	${\displaystyle :=\,\{x\mid x\lesssim a\}}$
${\displaystyle (\;,a)\,:=\,{]}\;,a{[}}$	${\displaystyle :=\,\{x\mid x<a\}}$

Footnotes

1. ↑ in English quasi-lexicographic , radix , length-plus-lexicographic or shortlex order

See also

• directed amount
• transitive envelope
• Quasi order