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)
“Should you be unfortunate enough to have vices, you may, to a certain degree, even dignify them by a strict observance of decorum; at least they will lose something of their natural turpitude.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Both the man of science and the man of art live always at the edge of mystery, surrounded by it. Both, as a measure of their creation, have always had to do with the harmonization of what is new with what is familiar, with the balance between novelty and synthesis, with the struggle to make partial order in total chaos.... This cannot be an easy life.”
—J. Robert Oppenheimer (1904–1967)
“God is a foreman with certain definite views
Who orders life in shifts of work and leisure.”
—Seamus Heaney (b. 1939)