Order Relation Examples

Set Theory · Axiom Academy

EXAMPLE Working with Order Relations Prove that divisibility is a partial order on positive integers and visualize it with a Hasse diagram Edges point upward from a to b when a | b (a divides b) Note: 2 and 3 are incomparable (neither divides the other), proving this is NOT a total order. Excellent work! You've successfully proven a partial order relation. Here's what we learned: Partial Order: A relation must be reflexive, antisymmetric, and transitive to be a partial order. Reflexive: Every element is related to itself. For divisibility, n | n because n = n × 1. Antisymmetric: If a | b and b | a, then a = b. This distinguishes partial orders from equivalence relations. Transitive: If a | b and b | c, then a | c. This follows from the multiplicative property of divisibility. Total vs Partial: A total order requires all elements to be comparable. Since 2 ∤ 3 and 3 ∤ 2, divisibility is only a partial order. Hasse Diagrams: Visual representations of partial orders that omit reflexive and transitive edges for clarity. Understanding partial orders is crucial for many areas of mathematics and computer science, including lattice theory and sorting algorithms!

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