Partial ordering
A
relation R is a partial ordering if it is a
pre-order (i.e. it is
reflexive (x R x) and
transitive (x R y R z => x R z)) and it is also
antisymmetric (x R y R x => x = y). The ordering is partial, rather than total, because there may exist elements x and y for which neither x R y nor y R x.
In
domain theory, if D is a set of values including the undefined value (
bottom) then we can define a partial ordering relation <= on D by
x <= y
if
x = bottom or x = y.
The constructed set D x D contains the very undefined element, (bottom, bottom) and the not so undefined elements, (x, bottom) and (bottom, x).
The partial ordering on D x D is then
(x1,y1) <= (x2,y2)
if
x1 <= x2 and y1 <= y2.
The partial ordering on D -> D is defined by
f <= g
if
f(x) <= g(x)
for all x in D.
(No f x is more defined than g x.)
A
lattice is a partial ordering where all finite subsets have a
least upper bound and a
greatest lower bound.
("<=" is written in
LaTeX as
\sqsubseteq).
