Partial ordering relation is a binary relation that is reflexive, antisymmetric, and transitive, that is, the following properties hold for all :
If is a set and a binary relation on , we call the pair a partial order.
Given a partial ordering relation , the corresponding strict ordering relation is defined by and can be viewed as a shorthand for this conjunction.
We can view partial order as a first-order interpretation of language where .
Example Partial Orders
Orders on integers, rationals, reals are all special cases of partial orders called linear orders.
Given a set , let be any set of subsets of , that is . Then is a partial order.
Example: Let and let . Then is a partial order. We can draw it as a Hasse diagram.
Hasse diagram presents the relation as a directed graph in a plane, such that
- the direction of edge is given by which nodes is drawn above
- transitive and reflexive edges are not represented (they can be derived)
Extreme Elements in Partial Orders
Given a partial order and a set , we call an element
- upper bound of if for all we have
- lower bound of if for all we have
- minimal element of if and there is no element such that
- maximal element of if and there is no element such that
- greatest element of if and for all we have
- least element of if and for all we have
- least upper bound (lub, supremum, join, ) of if is the least element in the set of all upper bounds of
- greatest lower bound (glb, infimum, meet, ) of if is the greatest element in the set of all lower bounds of
Taking we obtain minimal, maximal, greatest, least elements for the entire partial order.
Duality minimal/maximal, least/greatest, supremum/infimum
- minimal element need not exist: interval of rationals
- there may be multiple minimal elements:
- if minimal element exists, it need not be least: above example
- there are no two distinct least elements for the same set
- least element is always glb and minimal
- if glb belongs to the set, then it is always least and minimal
- for relation on sets, is intersection, is union (not all families of sets are closed under , )
Given two partial orders and , we call a function monotonic iff for all ,