Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z 


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)


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017