Course contentsShow
← Mathematics
Lesson 2547 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Total Orders and Linear Orders

Understand total orders as partial orders where every pair of elements is comparable and examine ordering on numbers.

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.