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 twodigit relation
on a set with certain properties listed below, one of which is transitivity .
If there is a set with an order relation , then the pair is called an ordered set . Usually, instead of the spelling, the socalled 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 " ").
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

(Reflexivity) 

(Antisymmetry) 

(Transitivity) 

(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 .
By
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
 .
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 quasiorder (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 .
A counterexample is the subset relation on the power set of : it is not total, because neither is nor .
Strict total order
A relation to is called strict (or also strong ) total order , if

(Transitivity) 

( Trichotomy ) 
applies to all .
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
is defined. Conversely from every (weak) total ordering on by
a strict total order .
Quasi order
A quasiorder is a transitive and reflexive relation.
Example:
For complex numbers , the relation defined by " " for the absolute amount is a quasiorder.
This quasiorder 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 quasiorder, 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

(Reflexivity) 

(Antisymmetry) 

(Transitivity) 
for all are fulfilled. The inverse relation of a partial order
is again a partial order.
Half orders can be visualized in Hasse diagrams . A subset of a semiordered 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
 transitive , since the subset of a subset of is also a subset of :
 for all
 reflexive , since any set is a subset of itself:
 for all
 and antisymmetric , since only itself is both a subset and a superset of :
 for all
Further examples are the relation componentwiseless thanorequal in a space of ntuples and the divisional relationship between the natural numbers, which are defined as follows:

componentwiseless thanorequal, For a fixed natural number and two tuples from a set of uples the following applies:
 for each
 This is a special case of a cone induced partial order, which leads to the concept of socalled generalized inequalities , which play an important role in optimization.

Partial relationship, for two natural numbers applies:
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 presorting 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 presorted is in this case . The sorting process Natural Mergesort uses presorted pieces for a complete sorting of the quantity.
Predecessor and successor
Let be a (weak) total (or partial) order on the set . For with
is called a predecessor of , and a successor to . If there isn't , with
 ,
then is called the direct (also immediate ) predecessor of , and the direct (or immediate ) successor of .
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:
Be on the crowd . For with
is called a predecessor of , and a successor to . If there isn't , with
 (i.e. ),
then is called the direct (also immediate ) predecessor of , and the direct (or immediate ) successor of .
Minimum, maximum and other elements
Let be a subset of a semiordered set .
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.
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:
 For , provided with a partial order, is indeed the only minimal element, but not the least, since not all of applies.
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.
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
applies.
Locally finite partial order
A partial order is locally finite if every interval is a finite set .
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”
 the relation “real subset” in a power set
 the relation “componentwise smaller, but not equal” on the vector space .
Strict weak order
A strict weak order R is a strict order in which negative transitivity also applies:
A strict, weak order is complementary to a total quasiorder and vice versa.
Inductive order
A semiordered 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.
According to Zorn's lemma , every inductively ordered set has a maximum element.
Wellfounded order
A wellfounded order is a partial order in which there are no infinite, genuinely descending chains (or, formulated equivalently: in which every nonempty subset has a minimal element). Example: The divisibility relationship  between natural numbers.
Quasi order
A well quasi order is a quasiorder with the property that there are two natural numbers for every sequence , so that applies.
Wellbeing
A wellorder is a total order in which every nonempty subset has a smallest element. Some examples:
 “Less than equal” on the natural numbers .
 The whole numbers with the order
 The whole numbers with the order
The wellorder theorem guarantees the existence of a wellorder for every set, for example also for the real numbers . It is equivalent to the axiom of choice .
tree
A tree is a partial order , in which for each the set of the predecessors of is well ordered.
Association regulations
An association order is a partial order in which it for any two elements and always a supremum and an infimum are.
The algebraic structure of an association is given by every association order by defining for two elements and :
Conversely, it can be passed in any association
for every two elements and define an association code so that
An associationordered 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.
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 .
Ordertheoretical 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.
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 .
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
or
 Partial order order (in the sense of total order).
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 threedigit 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 9783658006181 .
 Marcel Erné: Introduction to Order Theory. Bibliographisches Institut, Mannheim u. a. 1982, ISBN 3411016388 .
 Bernhard Ganter : Discrete Mathematics: Ordered Sets . Springer Spectrum, Berlin / Heidelberg 2013, ISBN 9783642374999 .
 Egbert Harzheim : Ordered Sets (= Advances in Mathematics. Vol. 7). Springer, New York NY 2005, ISBN 0387242198 .
 Ingmar Lehmann , Wolfgang Schulz: Sets  Relations  Functions. A clear introduction. 3rd, revised and expanded edition. Teubner, Wiesbaden 2007, ISBN 9783835101623 .
 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
Individual evidence

↑ ^{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 .
 ^ Dana Scott: Continuous Lattices. In: SLNM 274. 1972, pp. 97136, Proposition 2.5. Sa Scott, 1971 (PDF; 1.2 MB).
 ^ Roberto M. Amadio and PierreLouis Curien: Domains and LambdaCalculi. Cambridge University Press 1998. ISBN 0521622778 , p. 2.