In mathematics, in particular in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. The name is meant to suggest that preorders are almost partial orders, but not quite, as they are not necessarily antisymmetric.

A natural example of a preorder is the divides relation "x divides y" between integers. It is to this preorder that "least" refers in the phrase "least common multiple, ..., but no least one).

Preorders are closely related to equivalence relations and (non-strict) partial orders. Both of these are special cases of a preorder: an antisymmetric preorder is a partial order, and a symmetric, together with a partial order on the set of equivalence class, cf. picture. Like partial orders and equivalence relations, preorders (on a nonempty set) are never asymmetric.

A preorder can be visualized as a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a directed acyclic graph. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder's corresponding directed graph may have many disconnected components.

.

Definition

on a set is called a or if it is reflexive and transitive; that is, if it satisfies:

1. Reflexivity and

2. Transitivity

A set that is equipped with a preorder is called a preordered set (or proset).

Preorders as partial orders on partitions

one may define an equivalence relation twice; and symmetric by definition.

Using this relation, it is possible to construct a partial order on the quotient set That this is well-defined.

itself. There is a one-to-one correspondence between preorders and pairs (partition, partial order).

be the set of all (valid or invalid) sentences in some subfield of mathematics, like geometry are called "logically equivalent is a directed set, their logical conjunction is hence also a directed set. See Lindenbaum–Tarski algebra for a related example.

Relationship to strict partial orders

If reflexivity is replaced with irreflexivity (while keeping transitivity) then we get the definition of a strict partial order. For this reason, the term that satisfies: Irreflexivity or anti-reflexivity: is and Transitivity

Strict partial order induced by a preorder

is a strict partial order and strict partial order can be constructed this way. is antisymmetric But importantly, this new condition is is

Preorders induced by a strict partial order

include the following:

• are not needed.

• " is a strict weak order. The resulting preorder is connected (formerly called total); that is, a total preorder.

Examples

Graph theory

• The reachability relationship in any directed graph in the preorder if and only if there is a path from x to y in the directed graph. Conversely, every preorder is the reachability relationship of a directed graph (for instance, the graph that has an edge from x to y for every pair ). However, many different graphs may have the same reachability preorder as each other. In the same way, reachability of directed acyclic graphs, directed graphs with no cycles, gives rise to partially ordered sets (preorders satisfying an additional antisymmetry property).

• The graph-minor relation is also a preorder.

Computer science

In computer science, one can find examples of the following preorders.

• Asymptotic order. The corresponding equivalence relation is called asymptotic equivalence.

• Polynomial-time, many-one (mapping) and Turing reductions are preorders on complexity classes.

• Subtyping relations are usually preorders.

• Simulation preorders are preorders (hence the name).

• Reduction relations in abstract rewriting systems.

• The encompassment preorder on the set of terms if a subterm of t is a substitution instance of s.

• Theta-subsumption, which is when the literals in a disjunctive first-order formula are contained by another, after applying a substitution to the former.

Category theory

• A category with at most one morphism from any object x to any other object y is a preorder. Such categories are called thin. Here the objects and there is one morphism for objects which are related, zero otherwise. In this sense, categories "generalize" preorders by allowing more than one relation between objects: each morphism is a distinct (named) preorder relation.

• Alternately, a preordered set can be understood as an enriched category

Other

Further examples:

• Every finite topological space if and only if x belongs to every neighborhood of y. Every finite preorder can be formed as the specialization preorder of a topological space in this way. That is, there is a one-to-one correspondence between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not one-to-one.

  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.

  where f is a function into some preorder.

• if there exists some injection from x to y. Injection may be replaced by surjection, or any type of structure-preserving function, such as ring homomorphism, or permutation.

• The embedding relation for countable total orderings.

Example of a total preorder:

• Preference, according to common models.

Constructions

by taking the transitive closure and reflexive closure-path

Left residual preorder induced by a binary relation

forms a preorder called the left residual, denotes the converse relation denotes the complement denotes relation composition.

Related definitions

If a preorder is also antisymmetric then it is a partial order.

On the other hand, if it is symmetric then it is an equivalence relation.

A preorder is total

A preordered class is a class equipped with a preorder. Every set is a class and so every preordered set is a preordered class.

Uses

Preorders play a pivotal role in several situations:

• Every preorder can be given a topology, the Alexandrov topology; and indeed, every preorder on a set is in one-to-one correspondence with an Alexandrov topology on that set.

• Preorders may be used to define interior algebras.

• Preorders provide the Kripke semantics for certain types of modal logic.

• Preorders are used in forcing in set theory to prove consistency and independence results.

Number of preorders

As explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order). Thus the number of preorders is the sum of the number of partial orders on every partition. For example:

Interval

the interval is the set of points x It contains at least the points a and b. The extra intervals are all empty.

as the set of points x

can be defined similarly.

See also

• Partial order – preorder that is antisymmetric

• Equivalence relation – preorder that is symmetric

• Total preorder – preorder that is total

• Total order – preorder that is antisymmetric and total

• Directed set

• Category of preordered sets

• Prewellordering

• Well-quasi-ordering

Notes

References

• Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011,