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 (a ≤ b and a ≠ b)
Conversely, if "<" is a strict partial order, then the corresponding non-strict partial order "≤" is the reflexive closure given by:
- a ≤ b 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 and, strict, partial and/or orders:
“In a universe that is all gradations of matter, from gross to fine to finer, so that we end up with everything we are composed of in a lattice, a grid, a mesh, a mist, where particles or movements so small we cannot observe them are held in a strict and accurate web, that is nevertheless nonexistent to the eyes we use for ordinary living—in this system of fine and finer, where then is the substance of a thought?”
—Doris Lessing (b. 1919)
“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)
“America is hard to see.
Less partial witnesses than he
In book on book have testified
They could not see it from outside....”
—Robert Frost (1874–1963)
“One cannot be a good historian of the outward, visible world without giving some thought to the hidden, private life of ordinary people; and on the other hand one cannot be a good historian of this inner life without taking into account outward events where these are relevant. They are two orders of fact which reflect each other, which are always linked and which sometimes provoke each other.”
—Victor Hugo (1802–1885)