Partial Orders

Set Theory · Axiom Academy

Understanding reflexive, antisymmetric, and transitive relations that establish hierarchical structure 1. Definition of Partial Order A relation R on a set A is a partial order (or partial ordering ) if it satisfies three key properties: Reflexivity: Every element is related to itself: ∀a ∈ A, aRa Antisymmetry: If aRb and bRa, then a = b Transitivity: If aRb and bRc, then aRc We typically write partial orders using symbols like ≤ or ⊑. The pair (A, ≤) is called a partially ordered set or poset . 2. Classic Examples of Partial Orders Many familiar mathematical structures are partial orders: Subset relation (⊆): On any collection of sets, A ⊆ B means every element of A is in B. This satisfies all three properties. Divisibility on ℕ: We write a|b (a divides b) when there exists k such that b = ka. For example, 2|6 and 3|6, but 4∤6. Standard ordering (≤) on ℝ: The familiar "less than or equal to" relation on real numbers. A Hasse diagram is a graphical representation of a partial order that omits reflexive loops and transitive edges. Elements are positioned vertically, with smaller elements below larger ones. Place larger elements higher in the diagram Draw an edge from a to b only if a < b and there's no c with a < c < b Omit all reflexive loops (they're implied) Omit all transitive edges (they can be inferred) 4. Maximal, Minimal, Greatest, and Least Elements Partial orders have several important types of special elements:

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