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)
“We know what boredom is: it is a dull
Impatience or a fierce velleity,
A champing wish, stalled by our lassitude,
To make or do. In the strict sense, of course,
We invent nothing, merely bearing witness
To what each morning brings again to light:”
—Richard Wilbur (b. 1921)
“The one-eyed man will be King in the country of the blind only if he arrives there in full possession of his partial faculties—that is, providing he is perfectly aware of the precise nature of sight and does not confuse it with second sight ... nor with madness.”
—Angela Carter (1940–1992)
“Punishment may make us obey the orders we are given, but at best it will only teach an obedience to authority, not a self-control which enhances our self-respect.”
—Bruno Bettelheim (20th century)