Partially Ordered Set - Strict and Non-strict Partial Orders

Strict and Non-strict Partial Orders

In some contexts, the partial order defined above is called a non-strict (or reflexive, or weak) partial order. In these contexts a strict (or irreflexive) partial order "<" is a binary relation that is irreflexive and transitive, and therefore asymmetric. In other words, asymmetric (hence irreflexive) and transitive.

Thus, for all a, b, and c in P, we have that:

  • ¬(a < a) (irreflexivity);
  • if a < b then ¬(b < a) (asymmetry); and
  • if a < b and b < c then a < c (transitivity).

There is a 1-to-1 correspondence between all non-strict and strict partial orders.

If "≤" is a non-strict partial order, then the corresponding strict partial order "<" is the reflexive reduction given by:

a < b if and only if (ab and ab)

Conversely, if "<" is a strict partial order, then the corresponding non-strict partial order "≤" is the reflexive closure given by:

ab if and only if a < b or a = b.

This is the reason for using the notation "≤".

Strict partial orders are useful because they correspond more directly to directed acyclic graphs (dags): every strict partial order is a dag, and the transitive closure of a dag is both a strict partial order and also a dag itself.

Read more about this topic:  Partially Ordered Set

Famous quotes containing the words strict, partial and/or orders:

    The right honourable gentleman caught the Whigs bathing, and walked away with their clothes. He has left them in the full enjoyment of their liberal positions, and he is himself a strict conservative of their garments.
    Benjamin Disraeli (1804–1881)

    You must not be partial in judging: hear out the small and the great alike; you shall not be intimidated by anyone, for the judgment is God’s.
    Bible: Hebrew, Deuteronomy 1:17.

    There are nine orders of angels, to wit, angels, archangels, virtues, powers, principalities, dominations, thrones, cherubim, and seraphim.
    Gregory the Great, Pope (c. 540–604)