Total Ordering

Definition

A total order (or linear order) on a set $A$ is a relation $\le :A\to A\to \mathrm{Prop}$ that is:

• reflexive: $\forall x:A.x\le x$
• anti-symmetric: $\forall x,y:A.x\le y\to y\le x\to x=y$
• transitive: $\forall x,y,z:A.x\le y\to y\le z\to x\le z$
• total: $\forall x,y:A.x\le y\vee y\le x$

A set equipped with a total order is called a totally ordered set, a chain, or a linearly ordered set.

Strict Total Order

Associated to any total order $\le$ is the strict total order $<$ defined by $x<y⟺x\le y\wedge x\ne y.$ The strict version is irreflexive, transitive, and trichotomous: $\forall x,y:A.x<y\vee x=y\vee y<x.$ The two presentations are interdefinable: each determines the other.

Relationship to Partial Orders

A total order is a partial order with the additional totality condition. Every two elements are comparable, so there are no “incomparable” elements as may occur in a partial order.

A partial order in which every two elements are comparable is a total order; such a subset of a partial order is called a chain.

Examples

• $\le$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$: the standard numerical orderings.
• The Lexicographic order on words over an ordered alphabet.
• Any well-ordering is a total order.
• The ordinals under $\le$ form a total order (indeed a well-order).

Well-Ordering

A total order is a well-ordering iff every non-empty subset has a least element. Well-orderings are the total orders that support transfinite induction.

Categorical Perspective

A totally ordered set is a thin category in which for every pair of objects $x,y$, either $x\to y$ or $y\to x$ (or both, when $x=y$). Order-preserving maps are the morphisms between totally ordered sets.

Related Concepts

• Partial Order
• Preorder
• Well-Ordering
• Reflexive Relation
• Anti-Symmetric Relation
• Transitive Relation
• Total Relation
• Ordinal

References

• munkres2000-topology