pre-order

Definition

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

reflexivity: $s\lesssim s$ for all $s\in S$, and

transitivity: If $s\lesssim t$ and $t\lesssim u$, then $s\lesssim u$; for all $s,t,u\in S$.

Partial order induced by a pre-order

Given such a relation, define a new relation $s\sim t$ on $S$ by

$$s\sim t\text{ if and only if }s\lesssim t\text{ and }t\lesssim s.$$

Then $\sim$ is an equivalence relation on $S$, and $\lesssim$ induces a partial order $\le$ on the set $S/\sim$ of equivalence classes of $\sim$ defined by

$$[s]\le [t]\text{ if and only if }s\lesssim t,$$

where $[s]$ and $[t]$ denote the equivalence classes of $s$ and $t$. In particular, $\le$ does satisfy antisymmetry, whereas $\lesssim$ may not.

Pre-orders as categories

A pre-order $\lesssim$ 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\lesssim y$ (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