Partially Ordered Sets, Hasse Diagrams & Lattices
Idea in plain words
Partially Ordered Set (Poset): A pair (S, ≤) where relation ≤ is Reflexive, Antisymmetric, and Transitive.
Exam tip
High-yield exam topic (High).
Explanation
Posets model hierarchy, task precedence scheduling, type systems, and access control matrices. Lattices guarantee that any two assertions or states have a well-defined supremum (join) and infimum (meet), forming the theoretical foundation of abstract interpretation in static program analysis and compiler optimizations.
Key points
- Hasse Diagram: Visual representation of a poset where reflexive loops and transitive edges are omitted, and elements are arranged with arrows pointing upward.
- Extremal Elements: Maximal (no element strictly greater); Minimal (no element strictly smaller); Greatest / Maximum (unique element greater than all others); Least / Minimum (unique element smaller than all others).
- Upper/Lower Bounds: Least Upper Bound (LUB / Supremum / Join ∨); Greatest Lower Bound (GLB / Infimum / Meet ∧).
- Lattice: A poset (L, ≤) in which EVERY pair of elements has a unique LUB and a unique GLB.
- Special Lattices: Bounded (has universal 0 and 1); Distributive (a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)); Complemented (every element a has an a' such that a ∨ a' = 1 and a ∧ a' = 0). A Boolean Algebra is a complemented distributive lattice.
Example
Example
Is D_12 complemented? The 0 element is 1, and 1 element is 12. For element 4, its complement x must satisfy 4 ∨ x = 12 and 4 ∧ x = 1. GCD(4, 3) = 1 and LCM(4, 3) = 12, so 3 is the complement of 4. But element 2 has no complement (no x has GCD(2, x)=1 and LCM(2, x)=12). Hence D_12 is NOT complemented.
Code examples
// Divisibility Poset: D_12 = {1, 2, 3, 4, 6, 12} with relation a | b
// Hasse Diagram Construction:
// Level 3: 12
// / \
// Level 2: 4 6
// | \ / |
// Level 1: | 2 3
// \ | /
// Level 0: 1
//
// LUB(4, 6) = LCM(4, 6) = 12
// GLB(4, 6) = GCD(4, 6) = 2
// Since every pair of elements has a unique LCM and GCD, (D_12, |) is a Lattice!
Exam questions
- [8 Marks] Define a Lattice. Draw the Hasse diagram for the divisibility relation on D_30 = {1, 2, 3, 5, 6, 10, 15, 30} and determine whether it is a Boolean algebra.
- [7 Marks] Explain maximal, minimal, greatest, and least elements in a poset with a suitable Hasse diagram.
- [7 Marks] Prove that in any distributive lattice, if an element has a complement, then the complement is unique.