pre-order (original) (raw)

Definition

A pre-order on a set S is a relation ≲ on S satisfying the following two axioms:

reflexivity: s≲s for all s∈S, and

transitivity: If s≲t and t≲u, then s≲u; for all s,t,u∈S.

Partial order induced by a pre-order

Given such a relation, define a new relation s∼t on S by

Then ∼ is an equivalence relation on S, and ≲ induces a partial order ≤ on the set S/∼ of equivalence classes of ∼ defined by

where [s] and [t] denote the equivalence classes of s and t. In particular, ≤ does satisfy antisymmetry, whereas ≲ may not.

Pre-orders as categories

A pre-order ≲ on a set S can be considered as a small category, in the which the objects are the elements of S and there is a unique morphism from x to y if x≲y (and none otherwise).