Ma · Mathematics

Preorders vs. Partial Orders: What Is the Difference?

Published By the 9to5Science editorial team

At a glance

  1. 1. Check reflexivity

    Every element must be related to itself.

  2. 2. Check transitivity

    Related pairs must compose: if x relates to y and y to z, then x relates to z.

  3. 3. Check antisymmetry

    A partial order also requires mutual comparison to imply equality.

  4. 4. Identify equivalent elements

    In a preorder, elements related in both directions can be grouped into one equivalence class.

Advertisement

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 XX be a set and let ⪯\preceq be a binary relation on XX.

The relation is a preorder if it is:

  1. Reflexive: x⪯xx \preceq x for every x∈Xx \in X.
  2. Transitive: if x⪯yx \preceq y and y⪯zy \preceq z, then x⪯zx \preceq z.

It is a partial order if, in addition, it is:

  1. Antisymmetric: if x⪯yx \preceq y and y⪯xy \preceq x, then x=yx=y.

Thus,

partial order=preorder+antisymmetry.\text{partial order} = \text{preorder} + \text{antisymmetry}.

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 x⪯yx \preceq y forces x=yx=y. It says that equality follows only when both directions hold:

(x⪯y and y⪯x)⇒x=y.(x \preceq y \text{ and } y \preceq x) \Rightarrow x=y.

This is different from symmetry, which would require x⪯yx \preceq y if and only if y⪯xy \preceq x. 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 ≤\leq.
  • A preorder need not be symmetric, but it can contain symmetric pairs between distinct elements.

Every partial order is a preorder

The usual relation ≤\leq on the real numbers is a partial order. It is reflexive because x≤xx \leq x, transitive because x≤yx \leq y and y≤zy \leq z imply x≤zx \leq z, and antisymmetric because x≤yx \leq y and y≤xy \leq x imply x=yx=y.

Other standard partial orders include:

  • Set inclusion ⊆\subseteq on a collection of sets.
  • Divisibility on the positive integers: a⪯ba \preceq b when aa divides bb.
  • Coordinatewise comparison on Rn\mathbb{R}^n: (x1,…,xn)⪯(y1,…,yn)(x_1,\ldots,x_n) \preceq (y_1,\ldots,y_n) when xi≤yix_i \leq y_i for every ii.

These relations may leave some pairs incomparable. For example, neither {1}\{1\} nor {2}\{2\} 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 XX be the set of all finite strings, and define

x⪯yif and only iflength⁡(x)≤length⁡(y).x \preceq y \quad\text{if and only if}\quad \operatorname{length}(x) \leq \operatorname{length}(y).

This is a preorder:

  • Every string has length at most its own length, so the relation is reflexive.
  • If the length of xx is at most the length of yy, and the length of yy is at most the length of zz, then the length of xx is at most the length of zz. Thus it is transitive.

However, it is not antisymmetric. Consider the distinct strings cat and dog. Both have length 33, so

cat⪯doganddog⪯cat,\text{cat} \preceq \text{dog} \quad\text{and}\quad \text{dog} \preceq \text{cat},

but cat and dog are not equal.

Therefore this relation is a preorder but not a partial order.

A simpler finite example uses X={a,b,c}X=\{a,b,c\} with the relation generated by

a⪯b,b⪯a,b⪯c,a \preceq b, \qquad b \preceq a, \qquad b \preceq c,

together with the reflexive pairs. Transitivity also gives a⪯ca \preceq c. The relation is reflexive and transitive, but a⪯ba \preceq b and b⪯ab \preceq a while a≠ba \neq b, 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 XX by

x∼yif and only ifx⪯y and y⪯x.x \sim y \quad\text{if and only if}\quad x \preceq y \text{ and } y \preceq x.

For every preorder, ∼\sim is an equivalence relation:

  • Reflexivity follows from reflexivity of ⪯\preceq.
  • Symmetry is built into the definition.
  • For transitivity, if x∼yx \sim y and y∼zy \sim z, transitivity gives both x⪯zx \preceq z and z⪯xz \preceq x.

Now consider the set of equivalence classes X/∼X/{\sim}. Define

[x]⪯[y]if and only ifx⪯y.[x] \preceq [y] \quad\text{if and only if}\quad x \preceq y.

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 00 form one class, all strings of length 11 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:

  1. Test whether every element is related to itself. If not, it is neither a preorder nor a partial order.
  2. Test transitivity. If it fails, the relation is neither.
  3. Search for distinct elements xx and yy with both x⪯yx \preceq y and y⪯xy \preceq x. If such a pair exists, the relation is a preorder but not a partial order.
  4. 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 x⪯yx \preceq y and y⪯zy \preceq z without x⪯zx \preceq z.

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 x≺yx \prec y. From a non-strict partial order, one obtains a strict partial order by defining

x≺yif and only ifx⪯y and x≠y.x \prec y \quad\text{if and only if}\quad x \preceq y \text{ and } x \neq y.

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

  1. Discrete Mathematics and Its Applications, Kenneth H. Rosen
  2. 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.