Preorder

From Wikipedia, the free encyclopedia

This article is about the mathematics concept. For preorder traversal of a tree data structure, see tree traversal. For preordering of a graph, see depth-first search. For the marketing tactic, see pre-order.

In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. The name quasiorder is also a common expression for preorders. Many order theoretical definitions for partially ordered sets can be generalized to preorders, but the extra effort of generalization is rarely needed.

1 Formal definition
2 Constructions
3 Examples of preorders
4 See also

[edit] Formal definition

Consider some set P and a binary relation ≤ on P. Then ≤ is a preorder, or quasiorder, if it is reflexive and transitive, i.e., for all a, b and c in P, we have that:

a ≤ a (reflexivity)

if a ≤ b and b ≤ c then a ≤ c (transitivity)

A set that is equipped with a preorder is called a preordered set.

If a preorder is also antisymmetric, that is, a ≤ b and b ≤ a implies a = b, then it is a partial order. On the other hand, if it is symmetric, that is, if a ≤ b implies b ≤ a, then it is an equivalence relation.

A preorder which is preserved in all contexts is called a precongruence. A precongruence which is also symmetric (i.e. is an equivalence relation) is a congruence relation.

[edit] Constructions

Every binary relation R on a set S can be extended to a preorder on S by taking the transitive closure and reflexive closure, R⁺⁼. The transitive closure indicates path connection in R: x R⁺ y if and only if there is an R- path from x to y.

A partial order can be constructed from any preorder ≤ on set S by collapsing any violations of antisymmetry. Formally, one defines an equivalence relation ~ over S such that a ~ b if and only if a ≤ b and b ≤ a. Then the quotient set, S / ~, is the set of all equivalence classes of ~. Note that if the preorder is R⁺⁼, S / ~ is the set of R- cycle equivalence classes: x ∈ [y] if and only if x = y or x is in an R-cycle with y. In any case, S / ~ inherits the ≤ order by defining [x] ≤ [y] if and only if x ≤ y. By the construction of ~ , this definition is independent from the chosen representatives and the corresponding relation is indeed well-defined. It is readily verified that this yields a partially ordered set.

[edit] Examples of preorders

A net is a directed preorder, that is, each pair of elements has an upper bound. The definition of convergence via nets is important in topology, where preorders cannot be replaced by partially ordered sets without losing important features.
The embedding relation for countable total orderings.
The graph-minor relation in graph theory.
Preference, according to common models.
In computer science, subtyping relations are usually preorders.