Preorder

All definitions tacitly require the homogeneous relation

A term's definition may require additional properties that are not listed in this table.

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive.

A natural example of a preorder is the divides relation "x divides y" between integers, polynomials, or elements of a commutative ring.

, together with a partial order on the set of equivalence class.

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.

Using this relation, it is possible to construct a partial order on the quotient set of the equivalence,

That this is well-defined, meaning that its defining condition does not depend on which representatives of

It is readily verified that this yields a partially ordered set.

Conversely, from any partial order on a partition of a set

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

be a formal theory, which is a set of sentences with certain properties (details of which can be found in the article on the subject).

is that it is closed under logical consequences so that, for instance, if a sentence

where the right hand side condition is independent of the choice of representatives

denotes the sentence formed by logical conjunction

If reflexivity is replaced with irreflexivity (while keeping transitivity) then we get the definition of a strict partial order on

gives rise to a strict partial order defined by

But importantly, this new condition is not used as (nor is it equivalent to) the general definition of the relation

would not be transitive (consider how equivalent non-equal elements relate).

", which might cause confusion for a preorder that is not antisymmetric since it might misleadingly suggest that

for instance), it might not be possible to reconstruct the original non-strict preorder from

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

forms a preorder called the left residual,[4] where

Preorders play a pivotal role in several situations: Note that S(n, k) refers to Stirling numbers of the second kind.

As explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order).