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

reflexivityMathworldPlanetmath: ss for all sS, and

transitivity: If st and tu, then su; for all s,t,uS.

Partial order induced by a pre-order

Given such a relation, define a new relation st on S by

st if and only if st and ts.

Then is an equivalence relationMathworldPlanetmath on S, and induces a partial orderMathworldPlanetmath on the set S/ of equivalence classesMathworldPlanetmath of defined by

[s][t] if and only if st,

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 morphismMathworldPlanetmathPlanetmath from x to y if xy (and none otherwise).

Title pre-order
Canonical name Preorder
Date of creation 2013-03-22 13:05:06
Last modified on 2013-03-22 13:05:06
Owner yark (2760)
Last modified by yark (2760)
Numerical id 17
Author yark (2760)
Entry type Definition
Classification msc 06A99
Synonym pre-ordering
Synonym preorder
Synonym preordering
Synonym quasi-order
Synonym quasi-ordering
Synonym quasiorder
Synonym quasiordering
Synonym semi-order
Synonym semi-ordering
Synonym semiorder
Synonym semiordering
Related topic WellQuasiOrdering
Related topic PartialOrder
Defines pre-ordered
Defines preordered
Defines semi-ordered
Defines semiordered
Defines quasi-ordered
Defines quasiordered