Mathwords logoMathwords

Totally Ordered Set — Definition, Formula & Examples

A totally ordered set is a set equipped with a binary relation (like ≤\leq) such that every two elements can be compared — for any aa and bb in the set, either a≤ba \leq b or b≤ab \leq a (or both).

A totally ordered set (or linearly ordered set) is a pair (S,≤)(S, \leq) where ≤\leq is a binary relation on SS that is reflexive (a≤aa \leq a), antisymmetric (a≤ba \leq b and b≤ab \leq a imply a=ba = b), transitive (a≤ba \leq b and b≤cb \leq c imply a≤ca \leq c), and total (a≤ba \leq b or b≤ab \leq a for all a,b∈Sa, b \in S). The totality condition is what distinguishes a total order from a partial order.

How It Works

A total order arranges every element in the set along a single chain — no two elements are incomparable. To verify that a relation gives a total order, check all four properties: reflexivity, antisymmetry, transitivity, and totality. If even one pair of distinct elements is incomparable (neither a≤ba \leq b nor b≤ab \leq a), the order is only partial, not total.

Example

Problem: Determine whether the set S={2,5,8}S = \{2, 5, 8\} with the usual ≤\leq on integers is a totally ordered set.
Step 1: Check totality: can every pair be compared?
2≤5,2≤8,5≤82 \leq 5, \quad 2 \leq 8, \quad 5 \leq 8
Step 2: Check reflexivity, antisymmetry, and transitivity. Each element satisfies a≤aa \leq a. No two distinct elements satisfy both a≤ba \leq b and b≤ab \leq a. And 2≤52 \leq 5 and 5≤85 \leq 8 give 2≤82 \leq 8, confirming transitivity.
Answer: Yes, ({2,5,8},≤)(\{2, 5, 8\}, \leq) is a totally ordered set because every pair of elements is comparable and all four order axioms hold.

Why It Matters

Total orders underpin the real number line and any setting where you rank or sort elements. In analysis, the completeness of R\mathbb{R} as a totally ordered field is essential for proving the existence of limits and suprema. In computer science, sorting algorithms rely on the input having a total order.

Common Mistakes

Mistake: Assuming every partial order is a total order.
Correction: A partial order allows incomparable elements. For example, the subset relation ⊆\subseteq on {{1},{2}}\{\{1\}, \{2\}\} is a partial order but not a total order, because neither {1}⊆{2}\{1\} \subseteq \{2\} nor {2}⊆{1}\{2\} \subseteq \{1\}.