Total Orders and Linear Orders
You'll learn: How total orders extend partial orders by requiring that every pair of elements can be compared, giving you a completely ordered set.
What Is a Total Order?
In the last lesson, you learned about partial orders—relations that are reflexive, antisymmetric, and transitive, but where some elements might be incomparable. A total order (also called a linear order) is a partial order with one crucial additional property: every pair of distinct elements must be comparable.
Formally, a relation ≤ on a set A is a total order if it's a partial order AND for all a, b in A, either a ≤ b or b ≤ a (or both, if a = b).
The Intuition: A Single Line
Think of a total order as arranging elements along a single line, like books sorted by height or numbers on a ruler. You can always say which of any two books is taller—there are no "tie" situations where they're incomparable (unlike in partial orders, where elements might lie on separate "branches").
Classic Example: Ordering on Real Numbers
The standard ≤ relation on real numbers ℝ is the quintessential total order:
- It's reflexive: x ≤ x
- It's antisymmetric: if x ≤ y and y ≤ x, then x = y
- It's transitive: if x ≤ y and y ≤ z, then x ≤ z
- It's total: for any two numbers x and y, either x ≤ y or y ≤ x
You can pick any two numbers—say 3.7 and π—and definitively say which is smaller.
Non-Example
The subset relation ⊆ on a power set is not a total order. Given sets {1, 2} and {2, 3}, neither is a subset of the other—they're incomparable.
Key Takeaway: A total order is a partial order where comparability is complete—every pair of elements can be ordered, eliminating all "gaps" in the ordering structure.