Source : Free On-Line Dictionary of Computing
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}).
(1995-02-03)