Wednesday, January 8, 2014

Partial orders and extrema

Given any partial ordering relation we can form ternary extrema relations of suprema and infima based upon least upper bounds and greatest lower bounds. These extrema relations necessarily are idempotent, commutative, and have the generalized associative property. However, in general these ternary relations are not either magmas or even binary operations for that matter.
(false? 
  (binary-operation? 
    (infima-relation (weak-order [#{0 1} #{2 3}))))

(binary-operation? 
  (infima-relation (weak-order [#{0 1}]))))

(false? 
  (magma? 
    (infima-relation (weak-order [#{0 1}]))))
In order for the extrema relations of a partial order to be binary operations the partial order [2 2] must be forbidden as a suborder. Since lower and upper forests are defined as suborders of [2 2] they are examples of partial orders with unique extrema. If a commutative idempotent associative binary operation is a magma it is a semilattice so there is a clear correspondence between partial orders that are meet or join semilattices and extrema relations that are magmas. Another interesting property is that connectivity is maintained by the extrema relation:
(= (connected-components order)
   (connected-components (infima-relation order))
Zero elements and identity elements in extrema relations correspond to upper and lower bounds in the underlying partial order relation.

No comments:

Post a Comment