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: (<x, y> in R /\ <y,
x> 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: <x, x>
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