Recognizing Total Orders — Which relations are total orders?

The ≤ and alphabetical order are total orders because every element is comparable. Divisibility and subset relations are only partial orders, not total.

Total Order

Partial Order Well-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

We have reviewed and checked the materials, but errors may still occur. The content is provided for educational purposes only, so use it at your own responsibility and verify with other sources if needed.