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)
“There is no luck in literary reputation. They who make up the final verdict upon every book are not the partial and noisy readers of the hour when it appears; but a court as of angels, a public not to be bribed, not to be entreated, and not to be overawed, decides upon every man’s title to fame. Only those books come down which deserve to last.”
—Ralph Waldo Emerson (1803–1882)
“There is nothing on earth more exquisite than a bonny book, with well-placed columns of rich black writing in beautiful borders, and illuminated pictures cunningly inset. But nowadays, instead of looking at books, people read them. A book might as well be one of those orders for bacon and bran.”
—George Bernard Shaw (1856–1950)