Total Order

A total order (in English: total order or linear order) is a relation that satisfies all properties of a partial order (reflexive, antisymmetric, transitive), and in addition is total, meaning every pair of elements is comparable.

Formal Definition

Let R be a relation on a set A. R is a total order if:

• Reflexive: ∀a ∈ A: (a,a) ∈ R.
• Antisymmetric: ∀a,b ∈ A: (a,b) ∈ R ∧ (b,a) ∈ R ⇒ a = b.
• Transitive: ∀a,b,c ∈ A: (a,b) ∈ R ∧ (b,c) ∈ R ⇒ (a,c) ∈ R.
• Totality (comparability): ∀a,b ∈ A: (a,b) ∈ R ∨ (b,a) ∈ R.

Totality ensures that for any two distinct elements, one precedes the other.

Examples of Total Orders

• The ≤ relation on integers: reflexive, antisymmetric, transitive, and total.
• Alphabetical order on words: every two words can be compared.
• Chronological order on dates: every two dates, one is earlier than the other.

Counterexamples (Non-Total Orders)

• Divisibility relation on natural numbers: reflexive, antisymmetric, transitive, but not total (e.g., 2 and 3 incomparable).
• Subset relation ⊆ on sets: partial order, but not total (e.g., {1} and {2} incomparable).
• Friend of relation among people: not antisymmetric.

Total vs. Partial Order

Every total order is also a partial order, but not every partial order is total. The difference is comparability: partial orders can have incomparable elements, while total orders compare every pair.

Summary

A total order is a relation that creates an ordered sequence on the set: reflexive, antisymmetric, transitive, and total. It is one of the most important concepts in mathematics, as numbers, letters, dates, and many other data naturally stand in total order.

Practice Exercise