Order relation

In mathematics , order relations are generalizations of the “less than or equal” relationship . They allow elements of a set to be compared with one another .

An order relation is formally a two-digit relation

${\displaystyle R\subseteq M\times M}$

on a set with certain properties listed below, one of which is transitivity . ${\displaystyle M}$

If there is a set with an order relation , then the pair is called an ordered set . Usually, instead of the spelling, the so-called Infix notation is preferred . In addition, a symbol such as is rarely used for order relations . Instead, symbols such as , or similar are often used . The notation is used as an abbreviation for " and ". This proves to be useful, since for the most part arithmetic rules apply to relations that correspond to those in (with the usual " "). ${\displaystyle M}$ ${\displaystyle R}$ ${\displaystyle (M,R)}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle a\,R\,b}$ ${\displaystyle R}$ ${\displaystyle \leq }$ ${\displaystyle \preceq }$ ${\displaystyle a<b}$ ${\displaystyle a\leq b}$ ${\displaystyle a\neq b}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \leq }$

The following is a list of different types of ordering relations with examples. For definitions of the properties see transitive , reflexive and irreflexive , asymmetric , antisymmetric , or the article Relation (mathematics) .

Total order

A relation on a set is ( weak ) total ordering or total order or simply ( weak ) order mentioned if the claims ${\displaystyle \leq }$ ${\displaystyle M}$

${\displaystyle x\leq x}$	(Reflexivity)
${\displaystyle x\leq y\land y\leq x\;\Rightarrow \;x=y}$	(Antisymmetry)
${\displaystyle x\leq y\land y\leq z\;\Rightarrow \;x\leq z}$	(Transitivity)
${\displaystyle x\leq y\lor y\leq x}$	(Totality)

for all are fulfilled. Since this is the case with the number line , the “line”, a total order is also called a linear order . Furthermore, there is the designation chain for totally ordered subsets of partially ordered sets . ${\displaystyle x,y,z\in M}$

By

${\displaystyle x\preceq y:\Longleftrightarrow y\leq x}$

defined inverse relation of a total order is itself a total order. In the case of inverse relations, the mirrored symbol is often used as the relation sign, in this case instead of , that is ${\displaystyle \preceq }$ ${\displaystyle \leq }$ ${\displaystyle \geq }$ ${\displaystyle \preceq }$

${\displaystyle x\geq y:\Longleftrightarrow y\leq x}$.

In the case of total (quasi) orders, this has a special justification, because with them the inverse relation is a reflection.

A finite subset of a totally ordered set can be sorted in an unambiguous way according to this order, that is, brought into a (“linear”) order in such a way that each element is related to its subsequent element. This sort of order is called ascending . If instead the mirrored order relation applies between two neighboring elements, the sorting is called descending . The weaker concept of total quasi-order (see below) allows the existence of “duplicates”, that is, an ambiguous sorting.

Example and counterexample:

One example is the relation (“less than or equal”) on the whole numbers . ${\displaystyle \leq }$ ${\displaystyle \mathbb {Z} }$

A counterexample is the subset relation on the power set of : it is not total, because neither is nor . ${\displaystyle \subseteq }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \{1,2\}\subseteq \{2,3\}}$ ${\displaystyle \{2,3\}\subseteq \{1,2\}}$

Strict total order

A relation to is called strict (or also strong ) total order , if ${\displaystyle <}$ ${\displaystyle M}$

${\displaystyle x<y\;\land \;y<z\;\;\Rightarrow \;\;x<z}$	(Transitivity)
either or or ${\displaystyle x<y}$ ${\displaystyle x=y}$ ${\displaystyle y<x}$	( Trichotomy )

applies to all . ${\displaystyle x,y,z\in M}$

Since a strict total order is not reflexive, it is not a total order . A total order in the weak sense explained above is the order belonging to it (with reflexivity and antisymmetry), which is carried out by ${\displaystyle <}$

${\displaystyle x\leq y\;\;:\Leftrightarrow \;\;x<y{\text{ oder }}x=y}$

is defined. Conversely from every (weak) total ordering on by ${\displaystyle \leq }$ ${\displaystyle M}$

${\displaystyle x<y\;\;:\Leftrightarrow \;\;x\leq y{\text{ und }}x\neq y}$

a strict total order  . ${\displaystyle <}$

Quasi order

→ Main article : quasi-order

A quasi-order is a transitive and reflexive relation.

Example:

For complex numbers , the relation defined by " " for the absolute amount is a quasi-order. ${\displaystyle a,b\in \mathbb {C} }$ ${\displaystyle a\leq b,{\text{ falls }}|a|\leq |b|}$

This quasi-order is not antisymmetric - i.e. not a partial order, because numbers of the same amount do not have to be identical.

However, it is a total quasi-order, since two elements are comparable.

Partial order

A partial order - also called partial order , partial order or partial order - is a reflexive , antisymmetric and transitive relation, i.e. in which

${\displaystyle x\leq x}$	(Reflexivity)
${\displaystyle x\leq y\land y\leq x\;\Rightarrow \;x=y}$	(Antisymmetry)
${\displaystyle x\leq y\land y\leq z\;\Rightarrow \;x\leq z}$	(Transitivity)

for all are fulfilled. The inverse relation of a partial order ${\displaystyle x,y,z\in M}$

• ${\displaystyle y\preceq x:\Longleftrightarrow x\leq y}$

is again a partial order.

Half orders can be visualized in Hasse diagrams . A subset of a semi-ordered set is called an upper set if it also contains all of the following elements for each of its elements (i.e. all that could be to the right of the relation symbol).

With the help of the axiom of choice one can prove that every partial order can be embedded in a total order. For finite sets one does not have to assume the axiom of choice, and in this case there are also explicit algorithms for the construction of such a total order (see topological sorting ).

Examples:

Every subset relation on a system of sets is a partial order because it is ${\displaystyle A\subseteq B}$ ${\displaystyle {\mathfrak {M}}}$

• transitive , since the subset of a subset of is also a subset of : ${\displaystyle A}$ ${\displaystyle A}$

${\displaystyle {C\subseteq B\subseteq A}\ \Rightarrow \ {C\subseteq A}}$ for all ${\displaystyle A,B,C\in {\mathfrak {M}};}$

• reflexive , since any set is a subset of itself:

${\displaystyle {A\subseteq A}}$ for all ${\displaystyle A\in {\mathfrak {M}};}$

• and antisymmetric , since only itself is both a subset and a superset of : ${\displaystyle A}$ ${\displaystyle A}$

${\displaystyle {(A\subseteq B)}\wedge {(B\subseteq A)}\ \Rightarrow \ {A=B}}$ for all ${\displaystyle A,B\in {\mathfrak {M}}.}$

Further examples are the relation component-wise-less than-or-equal in a space of n-tuples and the divisional relationship between the natural numbers, which are defined as follows:

1. component-wise-less than-or-equal, ${\displaystyle \leq ^{n}:}$ For a fixed natural number and two tuples from a set of -uples the following applies: ${\displaystyle n}$ ${\displaystyle V}$ ${\displaystyle n}$

   ${\displaystyle {\left(a_{1},a_{2},\ldots ,a_{n}\right)}\leq ^{n}{\left(b_{1},b_{2},\ldots ,b_{n}\right)}\ :\Longleftrightarrow \ a_{i}\leq b_{i}}$ for each ${\displaystyle i=1,2,\ldots ,n;}$

2. This is a special case of a cone induced partial order, which leads to the concept of so-called generalized inequalities , which play an important role in optimization.
3. Partial relationship, ${\displaystyle \mid :}$ for two natural numbers applies:

   ${\displaystyle {a\mid b}\ ({a\ \mathrm {teilt} \ b}):\Longleftrightarrow \ \exists n\in \mathbb {N} :n\cdot a=b.}$

Strict partial order

Just as the strict total order differs from total order in that reflexivity and antisymmetry are replaced by irreflectivity, so a strict partial order is determined by irreflectivity and transitivity. As with the strict total order, with the strict partial order the equal bar in the notation is omitted or is even replaced by an unequal sign. An example is the relation "real subset" for the quantities.

Further application of the partial order

In order to measure the degree of pre-sorting of a set, one can specify the number of possible continuations of a partial order to a linear order . For example, if the ordered set with and given, there are three possible sequels: , and . The degree of pre-sorted is in this case . The sorting process Natural Mergesort uses pre-sorted pieces for a complete sorting of the quantity. ${\displaystyle (X,\leq )}$ ${\displaystyle X=\{a,b,c\}}$ ${\displaystyle a\leq b}$ ${\displaystyle a\leq b\leq c}$ ${\displaystyle a\leq c\leq b}$ ${\displaystyle c\leq a\leq b}$ ${\displaystyle e(\leq )=3}$

Predecessor and successor

→ Main article : Predecessor and successor (mathematics)

Let be a (weak) total (or partial) order on the set . For with ${\displaystyle \leq }$ ${\displaystyle M}$ ${\displaystyle x,z\in M}$

${\displaystyle x\leq z\land x\neq z}$

is called a predecessor of , and a successor to . If there isn't , with ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y\in M}$

${\displaystyle x\leq y\land x\neq y\land y\leq z\land y\neq z}$,

then is called the direct (also immediate ) predecessor of , and the direct (or immediate ) successor of . ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle x}$ 

For a strong (synonymous: strict ) total (or partial) order on , the above definition also applies formally (with notation instead of ).   However, in this case the criteria can be simplified as follows: ${\displaystyle <}$ ${\displaystyle M}$ ${\displaystyle <}$ ${\displaystyle \leq }$

Be on the crowd . For with ${\displaystyle <}$ ${\displaystyle M}$ ${\displaystyle x,z\in M}$

${\displaystyle x<z}$

is called a predecessor of , and a successor to . If there isn't , with ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y\in M}$

${\displaystyle x<y<z}$(i.e. ), ${\displaystyle x<y\land y<z}$

then is called the direct (also immediate ) predecessor of , and the direct (or immediate ) successor of . ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle x}$

Minimum, maximum and other elements

Let be a subset of a semi-ordered set . ${\displaystyle T}$ ${\displaystyle P}$

If has the property that there is no with , then the minimal element is called of . If there is an element that is all other elements of , then the smallest element is called of . A smallest element of (if it exists; e.g. the set of integers has no smallest element) is always uniquely determined (because of the antisymmetry) and of course also minimal. In a total order, “smallest element” and “minimal element” mean the same thing, but in general partial orders a set can have several minimal elements, none of which is then the smallest. ${\displaystyle m\in T}$ ${\displaystyle x\in T}$ ${\displaystyle x<m}$ ${\displaystyle m}$ ${\displaystyle T}$ ${\displaystyle m\in T}$ ${\displaystyle \leq }$ ${\displaystyle T}$ ${\displaystyle m}$ ${\displaystyle T}$ ${\displaystyle T}$

It can even happen that an (infinite) set has a single minimal element, but this is not the smallest element of the set (then it has no smallest element). Example: ${\displaystyle T}$ ${\displaystyle T}$

For , provided with a partial order, is indeed the only minimal element, but not the least, since not all of applies. ${\displaystyle M:=\{[0,a]\mid 0<a<1\}\cup \{\{2\}\}}$ ${\displaystyle \subseteq }$ ${\displaystyle \{2\}}$ ${\displaystyle \{2\}\subseteq A}$ ${\displaystyle A}$ ${\displaystyle M}$

If is a subset of and has the property that the relation holds for all , then a lower bound of is called . ( can, but does not have to be an element of .) If there is a largest lower bound of the set , then this is also called the lower limit or the infimum of . A lower bound is therefore smaller than or equal to the infimum. ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle p\in P}$ ${\displaystyle t\in T}$ ${\displaystyle p\leq t}$ ${\displaystyle p}$ ${\displaystyle T}$ ${\displaystyle p}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$

The terms maximum element , largest element , upper bound and upper limit or supremum are defined analogously .

A set that has both an upper and a lower bound is called bounded . (Similarly, "restricted upwards" and "restricted downwards" are defined.)

A function that maps any set into a semi- or totally ordered set (see below) is called bounded if the set of function values ​​is bounded, i.e. if there is one and one , so that for all ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle q\in P}$ ${\displaystyle x\in X}$

${\displaystyle p\leq f(x)\leq q}$

applies.

Locally finite partial order

A partial order is locally finite if every interval is a finite set . ${\displaystyle (M,\leq )}$ ${\displaystyle [x,y]:=\{z\in M:x\leq z\leq y\}}$

Strict order

A strict order or strict order is transitive and asymmetric . The term asymmetry summarizes the terms irreflectivity and antisymmetry . Irreflexibility distinguishes the strict order from the partial order and means that no element is related to itself. A strict order is therefore transitive , irreflexive and antisymmetric

Examples:

• The relation “(really) smaller” ${\displaystyle \mathbb {R} }$
• the relation “real subset” in a power set
• the relation “component-wise smaller, but not equal” on the vector space . ${\displaystyle \mathbb {R} ^{n}}$

Strict weak order

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

${\displaystyle \neg aRb\land \neg bRc\Rightarrow \neg aRc}$

A strict, weak order is complementary to a total quasi-order and vice versa.

Inductive order

A semi-ordered set is called inductively ordered if every linearly ordered subset of has an upper bound. It is called strictly inductively ordered if every linearly ordered subset has a smallest upper bound. ${\displaystyle (M,\leq )}$ ${\displaystyle M}$

According to Zorn's lemma , every inductively ordered set has a maximum element.

Well-founded order

A well-founded order is a partial order in which there are no infinite, genuinely descending chains (or, formulated equivalently: in which every non-empty subset has a minimal element). Example: The divisibility relationship | between natural numbers.

Quasi order

A well -quasi- order is a quasi-order with the property that there are two natural numbers for every sequence , so that applies. ${\displaystyle (p_{1},p_{2},p_{3},\ldots )}$ ${\displaystyle k<n}$ ${\displaystyle p_{k}\leq p_{n}}$

Well-being

A well-order is a total order in which every non-empty subset has a smallest element. Some examples:

• “Less than equal” on the natural numbers . ${\displaystyle \mathbb {N} }$
• The whole numbers with the order ${\displaystyle \mathbb {Z} }$ ${\displaystyle 0<1<-1<2<-2<3<-3<\ldots }$
• The whole numbers with the order ${\displaystyle \mathbb {Z} }$ ${\displaystyle 0<1<2<3<\ldots <-1<-2<-3<\ldots }$

The well-order theorem guarantees the existence of a well-order for every set, for example also for the real numbers . It is equivalent to the axiom of choice . ${\displaystyle \mathbb {R} }$

tree

→ Main article : tree

A tree is a partial order , in which for each the set of the predecessors of is well ordered. ${\displaystyle (T,<)}$ ${\displaystyle x\in T}$ ${\displaystyle \{y\mid y<x\}}$ ${\displaystyle x}$

Association regulations

An association order is a partial order in which it for any two elements and always a supremum and an infimum are. ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle \sup(v,w)}$ ${\displaystyle \inf(v,w)}$

The algebraic structure of an association is given by every association order by defining for two elements and : ${\displaystyle v}$ ${\displaystyle w}$

• ${\displaystyle v\vee w:=\sup(v,w),}$
• ${\displaystyle v\wedge w:=\inf(v,w).}$

Conversely, it can be passed in any association

• ${\displaystyle v\leq w\iff v\vee w=w}$

for every two elements and define an association code so that ${\displaystyle v}$ ${\displaystyle w}$

• ${\displaystyle \sup(v,w)=v\vee w,}$
• ${\displaystyle \inf(v,w)=v\wedge w.}$

An association-ordered set is therefore often called a "association", but in contrast to the association it is not an algebraic structure.

Complete partial order

A complete partial order ( pointed complete partial order , dcpo , cppo , also cpo ) is a partial order with a smallest element and the property that every subset that forms an ascending chain has a supremum . The supremum does not have to be in the subset itself. ${\displaystyle (x_{0}\leq x_{1}\leq x_{2}\leq \dotsb )}$

In a directed complete partial order (Engl. Directed complete partial order , DCPO ) must be in contrast to the complete partial order have the empty set no upper bound. There does not have to be a smallest element.

These two notions of completeness play a role in proofs using the lemma of Zorn . → This must be distinguished from the concept of completeness of order, which is based on the topology .

Order-theoretical concept of continuity

In terms of order theory , continuity can be understood as the compatibility of a function with the supremum of complete partial orders . A function is called continuous if holds for all directed subsets . This term plays a central role in domain theory . Similar to the continuity of sequences above, limit values ​​are again mapped onto limit values. ${\displaystyle A,B}$ ${\displaystyle f\colon A\rightarrow B}$ ${\displaystyle f(\bigsqcup X)=\bigsqcup f(X)}$ ${\displaystyle X\subseteq A}$

In this context, the continuity of a function results in its monotony . Conversely, every monotonous function maps a directed set back onto such a set, whereby the existence of the supreme of the image is then certain from the start and no longer has to be shown. Many authors include monotony as a requirement in the definition of continuity.

Homomorphisms

Be and ordered sets. A mapping is called isotonic , order preserving , orderly or order homomorphism , if applies to all . ${\displaystyle X}$ ${\displaystyle X'}$ ${\displaystyle \varphi \colon X\rightarrow X'}$ ${\displaystyle x\leq y\Rightarrow \varphi (x)\leq \varphi (y)}$ ${\displaystyle x,y\in X}$

Use of the terms

The authors use the term “order” differently. It can denote a partial order or a total order . Presumably induced by the polarities “half” and “total”, one often finds the demarcation

Order (in the sense of partial order) total order ${\displaystyle \quad \longleftrightarrow \quad }$

or

Partial order order (in the sense of total order). ${\displaystyle \quad \longleftrightarrow \quad }$

See also

• An order relation on a set of bundles of goods is called a preference relation in microeconomics .
• In algebra , (mostly total) order relations are considered on a set that is compatible with the link or the links on this set. See Ordered Body as an example .
• In geometry, under certain conditions, arrangements of the points can be introduced on every straight line. One speaks here of intermediate relations (these are three-digit relations), from which, in important special cases, total orders that are compatible with one another and with the geometric structure result on these rows of points.
• Every totally ordered set can be equipped with a topological structure determined by the order , the order topology .

literature

• Rudolf Berghammer: Orders, associations and relations with applications. 2nd, revised and corrected edition. Springer Vieweg, Wiesbaden 2012, ISBN 978-3-658-00618-1 .
• Marcel Erné: Introduction to Order Theory. Bibliographisches Institut, Mannheim u. a. 1982, ISBN 3-411-01638-8 .
• Bernhard Ganter : Discrete Mathematics: Ordered Sets . Springer Spectrum, Berlin / Heidelberg 2013, ISBN 978-3-642-37499-9 .
• Egbert Harzheim : Ordered Sets (= Advances in Mathematics. Vol. 7). Springer, New York NY 2005, ISBN 0-387-24219-8 .
• Ingmar Lehmann , Wolfgang Schulz: Sets - Relations - Functions. A clear introduction. 3rd, revised and expanded edition. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3 .
• Wiebke Petersen: Mathematical Foundations of Computational Linguistics - Order Relations, 4th set of slides, Heinrich Heine University Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 WS 2013/14 , accessed on April 21, 2018.

Web links

Wikibooks: Math for non-freaks: order relation  - learning and teaching materials

• Order relation in the lexicon of mathematics on Spektrum.de

Individual evidence

1. ↑ ^{a b} W. Petersen WS 2001/12 p. 93, WS 2013/14 p. 90. The terms are often used for other relationships instead of the (weak or strong ) (partial) order relationships listed here . Attention: Some authors only refer to their immediate (i.e. direct ) predecessors (or successors) as predecessors (or successors). What is defined above as a predecessor / successor would then be a predecessor or successor in the broader sense. However, it does not necessarily have to be accessible via a sequence of direct (i.e. immediate) predecessors or successors (quasi indirectly or indirectly), e.g. B. 0 and 1 on or . ${\displaystyle R}$ ${\displaystyle \leq }$ ${\displaystyle <}$
   
   ${\displaystyle (\mathbb {R} ,<)}$ ${\displaystyle (\mathbb {Q} ,<)}$
2. ^ Dana Scott: Continuous Lattices. In: SLNM 274. 1972, pp. 97-136, Proposition 2.5. Sa Scott, 1971 (PDF; 1.2 MB).
3. ^ Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi. Cambridge University Press 1998. ISBN 0-521-62277-8 , p. 2.