This is an old revision of the document!
Partial Orders
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.
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,
) of
if
is the least element in the set of all upper bounds of
- greatest lower bound (glb, infimum,
) of
if
is the least element in the set of all upper bounds of
Taking we obtain minimal, maximal, greatest, least elements for the entire partial order.
Duality minimal/maximal, least/greatest, supremum/infimum
Note:
- minimal element need not exist
- there may be multiple minimal elements
- if minimal element exists, it need not be least
- there are no two distinct minimal 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
Monotonic functions
Given two partial orders and
, we call a function
monotonic iff for all
,