   Go backward to 7.1 Equivalence Relations and PartitionsGo up to 7 More on RelationsGo forward to 7.3 Graphs ## 7.2 Order Relations

Partial Orders  A binary relation is a partial order if it has some (not necessarily all) properties of the relation <= on R. In addition to some of the properties introduced in the previous section, we need the following notion.

Definition 113 (Antisymmetric) A binary relation is  antisymmetric (antisymmetrisch), if different elements are not mutually related:
 R is antisymmetric on S : <=> forall x in S, y in S: ( in R /\  in R) => x = y.

In the graph representation of an antisymmetric relation, the only loops are from a node to itself, i.e., the following relation is not antisymmetric: Definition 114 (Partial Order) A binary relation on S is a  partial order (partielle Ordnung, Halbordnung), if it is reflexive, antisymmetric, and transitive:
 R is partial order on S : <=> R subset S x S /\ R is reflexive on S /\ R is antisymmetric on S /\ R is transitive on S.

Example
• <= is a partial order on N.
• subset  is a partial order on P(S), for every set S.
• | (divides) is a partial order on N.

Quasi Orders  Frequently, a partial order is denoted as infix <= (or simply as <= ); a corresponding relation < is then defined as

 x < y : <=> x <= y /\  x != y.
While < is also antisymmetric and transitive, it is not reflexive, and thus not a partial order. Actually, it even satisfies the following property.

Definition 115 (Irreflexive) A binary relation is  irreflexive (irreflexiv), if no element is related to itself:
 R is irreflexive on S : <=> forall x in S: not  in R.

The graph representation of an irreflexive relation does not contain direct loops from a node to itself, i.e., the following relation is not irreflexive: Definition 116 (Quasi Order) A binary relation on S is a  quasi order (Quasi-Ordnung), if it is irreflexive, antisymmetric, and transitive:
 R is quasi order on S : <=> R subset S x S /\ R is irreflexive on S /\ R is antisymmetric on S /\ R is transitive on S.

The graph representation of an quasi order does not contain any (direct or indirect) loops, i.e., the following is not a quasi-order: Proposition 127 (Quasi Orders Are Antisymmetric) Every quasi order is antisymmetric:
 forall S, < : < is quasi order on S => < is antisymmetric on S.

Proof  Take arbitrary S and quasi order < on S. Assume there exist x in S and y in S with x != y such that x < y and y < x. By transitivity, we then have x < x which contradicts the irreflexivity of < .

Consequently, the only difference between partial orders and quasi orders is reflexivity versus irreflexivity. Furthermore, the following holds.

Proposition 129 (Quasi Order from Partial Order) If <= is a partial order, then < is a quasi-order:
 forall S, <= : <= is partial order on S => < is quasi order on S.

Therefore adding equality to a quasi order makes it a partial order and removing equality from a partial order makes it a quasi order.

Example
• < is a quasi-order on R.
• proper subset  (proper subset) is a quasi-order on P(S), for every set S.

In a partial order or quasi order, not all elements are necessarily comparable, e.g., in P({0, 1, 2}) neither {0, 1} subset {1, 2} nor {1, 2} subset {0, 1}.

Definition 117 (Incomparable) Two elements x and y are incomparable with respect to a relation <= if neither x <= y nor y <= x:
 x and y are incomparable w.r.t. <= : <=> x not <= y /\  y not <= x.

Total Orders  Some partial orders do not have incomparable elements.

Definition 118 (Total Order) A partial order is a  total order (totale Ordnung) or  linear order (lineare Ordnung) or  chain (Kette) if no elements are incomparable with respect to this order:
 R is total order on S : <=> R is partial order on S /\ ~exists x in S, y in S: x and y are incomparable w.r.t. R.

Example
• <= is a total order on R.
• The  lexicographic order (lexikographische Ordnung)
 x <= y : <=> x0 < y0 \/ (x0 = y0 /\  x1 <= y1)
is a total order on N x N. In this order, we have
 <0, 0> < <0, 1> < <0, 2> < ...< <1, 0> < <1, 1> < <1, 2> < ...
i.e., tuples are ordered first by their first component and then by their second component.
• Let <= be a total order on an alphabet A, let Wn := Nn -> A be the set of all words with n letters, and let
 w := such u in Wn-1: forall i in Nn-1: ui = wi+1
be the function that removes the first letter from word w. The lexicographic order <= n subset Wn x Wn defined as
 w <= n u : <=> n = 0 \/ w0 < u0 \/ (w0 = u0 /\  w <= n-1 u)
is a total order. If A is the set of Roman letters, we have
"back" < 4 "bare" < 4 "base" < 4 "bear" < 4 "bend" < 4 "care"

Hasse Diagrams  Like any binary relation, a partial order can be represented by a directed graph, e.g. A more economical visualization that utilizes the properties of partial order is provided by a  Hasse diagram (Hasse Diagramm). Such a diagram is an undirected graph were all edges are considered as arrows from bottom to top, i.e., smaller elements are placed lower: The graph for the corresponding partial order is constructed by directing the edges from bottom to top, by adding loops to all nodes (because of reflexivity) and by adding direct arrows between all nodes that are indirectly connected by two or more arrows (because of transitivity). E.g., the relationship a <= d is not denoted by an extra edge but can be deduced from the relationship a <= b and b <= d in the diagram.

Example
• This Hasse diagram illustrates the total order <= on N5. • This Hasse diagram illustrates the partial order subset  on P({1, 2, 3}): • This Hasse diagram illustrates the partial order subset  on
{{0}, {1}, {2}, {0, 1}, {1, 2}, {0, 1, 2}}: • Let Fn := {m in N: m | n} (the factors of n). The following Hasse diagram illustrates the partial order | on F12: Logic Evaluator  Above definitions can be implemented as shown below (see Appendix `order.txt`):

More Notions  Various notions that we have introduced for the total ordering <= on R can be generalized to partial orders.

Definition 119 (Least and Greatest Element) If x is an element of S such that x is less than or equal to any element of S, then x is called the  least element (kleinstes Element) of S:
 x is least element of S w.r.t. <= : <=> x in S /\  forall y in S: x <= y.
Correspondingly, if x is an element of S such that x is greater than or equal to any element of S with respect to a partial ordering, then x is called the  greatest element (größtes Element) of S:
 x is greatest element of S w.r.t. <= : <=> x in S /\  forall y in S: y <= x.

We can show that a least respectively greatest element is unique, if such an element exists.

Example
• 0 is the least element of P({1, 2, 3}) with respect to subset , {1, 2, 3} is the greatest element: • The following Hasse diagram denotes a partial order with greatest element a but without a least element: Definition 120 (Minimal and Maximal Element) If x is an element of S such that no element of S is smaller than S, then x is called a  minimal element (minimales Element) of S.
 x is minimal element of S w.r.t. <= : <=> x in S /\  forall y in S: y <= x => y = x.
Correspondingly, if x is an element of S such that no element of S is greater than S, then x is called a  maximal element (maximales Element) of S.
 x is maximal element of S w.r.t. <= : <=> x in S /\  forall y in S: x <= y => x = y.

Minimal and maximal elements are not necessarily unique: distinct incomparable minimal respectively maximal elements may exist.

Example  The following Hasse diagram denotes a partial order with two minimal elements a and b: Definition 121 (Upper and Lower Bound) A value x is a  lower bound (untere Schranke) of S, if it is less than or equal any element of S:
 x is lower bound of S w.r.t. <= : <=> forall y in S: x <= y.
Correspondingly, a value x is an upper bound (obere Schranke) of S, if it is greater than or equal any element of S:
 x is upper bound of S w.r.t. <= : <=> forall y in S: y <= x.

Please note that an lower (respectively upper bound) of a set S need not be an element of S: Definition 122 (Infimum and Supremum) A value x is a infimum (Infimum) of S, if it is the greatest lower bound of S:
 x is infimum of S w.r.t. <= : <=> x is lower bound of S w.r.t. <= /\ forall y: y is lower bound of S w.r.t. <= => y <= x.
Correspondingly, a value x is a supremum (Supremum) of S, if it is the least upper bound of S:
 x is supremum of S w.r.t. <= : <=> x is upper bound of S w.r.t. <= /\ forall y: y is upper bound of S w.r.t. <= => x <= y.

Even the supremum respectively infimum of a set need not be an element of this set. However, we have the following relationships between the concepts defined above.

Proposition 130 (Order Laws) Let <= be a partial order on S. Then for every x, the following holds:
 x is least (greatest) element of S w.r.t. <= => x is minimal (maximal) element of S w.r.t. <= , x is least (greatest) element of S w.r.t. <= => x is infimum (supremum) of S w.r.t. <= , x is lower (upper) bound of S w.r.t. <= /\  x in S => x is least (greatest) element of S w.r.t. <= .

Logic Evaluator  Some of above definitions can be implemented as shown below, see Appendix `order.txt`.

Author: Wolfgang Schreiner
Last Modification: October 4, 1999   