Total Orders

Set Theory · Axiom Academy

When every pair of elements is comparable: the complete ordering principle A partial order ≤ on a set A is a total order (or linear order ) if it satisfies the comparability property : Comparability: For all a, b ∈ A, either a ≤ b or b ≤ a (or both) In other words, every pair of elements is comparable. Combined with the partial order properties (reflexive, antisymmetric, transitive), this creates a complete ordering. Alternative characterization: A total order is a partial order with no incomparable pairs. Real numbers with ≤: The standard ordering on ℝ is a total order. For any two real numbers x and y, we always have either x ≤ y or y ≤ x. Integers with ≤: Similarly, ℤ with the usual ordering is totally ordered. Lexicographic order: Words in a dictionary are totally ordered alphabetically. For example, "apple" < "banana" < "cherry". Non-example: The divisibility relation on ℕ is NOT a total order because 2 and 3 are incomparable (neither divides the other). Two important concepts help us understand the structure of partial orders: Chain: A subset C ⊆ A where every pair of elements is comparable. In other words, C is totally ordered by the restriction of ≤. Antichain: A subset B ⊆ A where no two distinct elements are comparable (all pairs are incomparable). A total order is exactly a partial order where the entire set forms a single chain. Example: In the power set of 1, 2 with ⊆, the set 1 , 1,2 is a chain, while 1 , 2 is an antichain.

This is the written version of the interactive lesson above. See the full Set Theory course.