Preorders vs. Partial Orders: What Is the Difference?
At a glance
- 1. Check reflexivity
Every element must be related to itself.
- 2. Check transitivity
Related pairs must compose: if x relates to y and y to z, then x relates to z.
- 3. Check antisymmetry
A partial order also requires mutual comparison to imply equality.
- 4. Identify equivalent elements
In a preorder, elements related in both directions can be grouped into one equivalence class.
A preorder and a partial order are both ways of expressing that some elements are “before,” “below,” or “at most” other elements. The difference is one condition: antisymmetry.
Definitions
Let be a set and let be a binary relation on .
The relation is a preorder if it is:
- Reflexive: for every .
- Transitive: if and , then .
It is a partial order if, in addition, it is:
- Antisymmetric: if and , then .
Thus,
The word “partial” means that some distinct elements may be incomparable. It does not mean that antisymmetry is optional.
Why antisymmetry matters
Antisymmetry says that two different elements cannot each be below the other. Formally, it does not say that forces . It says that equality follows only when both directions hold:
This is different from symmetry, which would require if and only if . Antisymmetry and symmetry are not opposites:
- A relation can be both symmetric and antisymmetric, such as equality.
- A partial order is usually not symmetric, such as the usual relation .
- A preorder need not be symmetric, but it can contain symmetric pairs between distinct elements.
Every partial order is a preorder
The usual relation on the real numbers is a partial order. It is reflexive because , transitive because and imply , and antisymmetric because and imply .
Other standard partial orders include:
- Set inclusion on a collection of sets.
- Divisibility on the positive integers: when divides .
- Coordinatewise comparison on : when for every .
These relations may leave some pairs incomparable. For example, neither nor contains the other, so set inclusion is not a total order. It is still a partial order.
A concrete preorder that is not a partial order
Let be the set of all finite strings, and define
This is a preorder:
- Every string has length at most its own length, so the relation is reflexive.
- If the length of is at most the length of , and the length of is at most the length of , then the length of is at most the length of . Thus it is transitive.
However, it is not antisymmetric. Consider the distinct strings cat and dog. Both have length , so
but cat and dog are not equal.
Therefore this relation is a preorder but not a partial order.
A simpler finite example uses with the relation generated by
together with the reflexive pairs. Transitivity also gives . The relation is reflexive and transitive, but and while , so antisymmetry fails.
Turning a preorder into a partial order
A preorder may treat distinct elements as equivalent for ordering purposes. Define a new relation on by
For every preorder, is an equivalence relation:
- Reflexivity follows from reflexivity of .
- Symmetry is built into the definition.
- For transitivity, if and , transitivity gives both and .
Now consider the set of equivalence classes . Define
This is well-defined and produces a partial order on the equivalence classes. The potentially different elements that mutually precede one another have been collapsed into a single class.
For the string example, all strings of length form one class, all strings of length form another, and so on. The quotient is ordered by string length, which is a partial order on the set of possible lengths.
How to test a relation
Given a relation, use this order:
- Test whether every element is related to itself. If not, it is neither a preorder nor a partial order.
- Test transitivity. If it fails, the relation is neither.
- Search for distinct elements and with both and . If such a pair exists, the relation is a preorder but not a partial order.
- If no such distinct pair exists, the relation is a partial order.
For a finite relation, the most efficient counterexample to partial-order status is usually a two-way pair between distinct elements. To disprove transitivity, look for and without .
Common terminology variations
Most modern mathematics uses “preorder” for a reflexive, transitive relation. Some authors use quasi-order as a synonym. In a few contexts, especially older literature, terminology can vary, so check the author’s definitions.
A strict partial order uses a different convention: it is irreflexive and transitive, written . From a non-strict partial order, one obtains a strict partial order by defining
Conversely, a strict partial order can usually be converted to a non-strict one by allowing equality. These strict and non-strict versions should not be confused with the distinction between preorders and partial orders: the latter concerns whether distinct elements may be mutually related.
References
- Discrete Mathematics and Its Applications, Kenneth H. Rosen
- A Course in Universal Algebra, Stanley Burris and H. P. Sankappanavar
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.