Preorder

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.

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:

aa (reflexivity)
if ab and bc then ac (transitivity)

A set that is equipped with a preorder is called a preordered set. If a preorder is also antisymmetric, that is, ab and ba implies a = b, then it is a partial order.

A partial order can be constructed from any preorder by identifying "equal" points. Formally, one defines an equivalence relation ~ over X such that a ~ b iff ab and ba. Now the quotient set X / ~, i.e. the set of all equivalence classes of ~, can easily be ordered by defining [x] ≤ [y] iff xy. 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.

Examples of preorders

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy