partial ordering

views updated

partial ordering (partial order) A relation defined between elements of some set and satisfying certain properties, discussed below. It is basically a convenient generalization of the usual comparison operators, such as > or <, that are typically defined on the integers or the real numbers. The generalization also captures the essential properties of the set operations such as “is a subset of”, the alphabetic ordering of strings, and so on. In denotational semantics, partial orderings are used to express some approximation relation between partially defined computational objects.

Two different but equivalent definitions of a partial ordering are possible. The first is a generalization of the usual ← operation in which the relation must be a transitive, antisymmetric, and reflexive relation defined on the set S. The second definition is a generalization of the usual < operation in which the relation must be a transitive, asymmetric, and irreflexive relation defined on S. A set with a partial ordering defined on it is called a partially ordered set or sometimes a poset.