Order

Overview

An ordering on a set $A$ is a relation $R:A\to A\to \mathrm{Prop}$ satisfying some combination of the following properties:

Property	Meaning
Reflexivity	$\forall x.Rxx$
Irreflexivity	$\forall x.\neg Rxx$
Transitivity	$\forall x,y,z.Rxy\to Ryz\to Rxz$
Anti-symmetry	$\forall x,y.Rxy\to Ryx\to x=y$
Totality	$\forall x,y.Rxy\vee Ryx$
Well-foundedness	every nonempty subset has a minimal element

Hierarchy of Orders

The standard hierarchy, from weakest to strongest, is:

• Preorder: reflexive and transitive.
• Partial order: reflexive, transitive, and anti-symmetric.
• Total order: a partial order in which any two elements are comparable.
• Well-ordering: a total order in which every nonempty subset has a least element.

Strict variants replace reflexivity with irreflexivity. The strict relation $x<y$ associated to a non-strict order $x\le y$ is defined by $x<y⟺x\le y\wedge x\ne y$, and conversely.

Related Concepts

• Order Theory
• Preorder
• Partial Order
• Total Ordering
• Well-Ordering
• Equivalence Relation
• Predicate