~20 min
Section 4 of 10
Sections
Historical Context & Motivation
Core Definitions & Foundational Principles
Hasse Diagrams — Visualizing Partial Orders
Mathematical Framework
Lattices — When Every Pair Has a Join and Meet
Worked Example — Divisibility Poset on {1, 2, 3, 5, 6, 10, 15, 30}
Comparison of Ordering Structures
Connections to Advanced Theory
Practice Problems
Summary & Key Concepts
Discrete Math • Relations and Discrete Structures
Partial orders, Hasse diagrams, and lattices (intro)
Difficulty 3/5
Mathematical Framework
We now formalize the key definitions. Let (S, ≤) be a poset. The concepts of bounds and extremal elements are central to connecting partial orders to lattice theory.
PARTIAL ORDER AXIOMS
∀a,b ∈ S : (a ≤ b ∧ b ≤ a) ⟹ a = b (antisymmetry) ∀a,b,c ∈ S : (a ≤ b ∧ b ≤ c) ⟹ a ≤ c (transitivity)$$ A binary relation ≤ on S satisfying all three axioms is a partial order, and (S, ≤) is a poset. **UPPER AND LOWER BOUNDS** $$For A ⊆ S: u is an upper bound of A ⟺ ∀a ∈ A : a ≤ u ℓ is a lower bound of A ⟺ ∀a ∈ A : ℓ ≤ a$$ An upper bound u need not belong to A itself. The **least upper bound** (lub or **join**, written a ∨ b) is the smallest upper bound; the **greatest lower bound** (glb or **meet**, written a ∧ b) is the largest lower bound. **LATTICE DEFINITION** $$A poset (L, ≤) is a lattice ⟺ ∀a,b ∈ L : a ∨ b and a ∧ b both exist in L.$$ In words, every pair of elements must have both a join (least upper bound) and a meet (greatest lower bound) within the set. If this holds only for every finite nonempty subset, we have a **complete lattice** when it extends to arbitrary subsets. **COVERING RELATION** $$a ≺ b ⟺ (a < b) ∧ (∄ c ∈ S : a < c < b)$$ Here a < b means a ≤ b and a ≠ b (the strict partial order). The covering relation captures the "immediate successor" relationship used to draw edges in a Hasse diagram. These definitions interact tightly. In a finite lattice, the join of two elements can be found visually in the Hasse diagram by tracing all paths upward from both elements until they first converge at a common node; that node is the join. Dually, the meet is found by tracing downward. The lattice property guarantees this convergence always yields a unique element, not merely a set of incomparable upper bounds.Section 4 of 10
Still stuck? Get 1:1 help.
Book a tutoring session with an expert discrete math tutor.