2.5Partial orders, Hasse diagrams and lattices
The idea
A partial order is reflexive, antisymmetric and transitive. Its Hasse diagram draws only the covering pairs, upward, and a lattice is a poset where every two elements have a least upper bound and a greatest lower bound.
Think of it like this: A company chart: bosses above, with only direct reports drawn, and the lines you can follow upward show who outranks whom.
Why it exists
Reading a Hasse diagram (maximal, minimal, lub, glb, chain, antichain) and deciding "is this a lattice" are regular multi-mark questions.
How it works
- Draw a line from a up to b only when a < b and nothing lies in between (a cover).
- Minimal: nothing below it. Maximal: nothing above it. Least/greatest: below/above everything (unique if they exist).
- lub(a, b) is the smallest element above both; glb is the largest below both.
- Lattice: every pair has both. A finite lattice has a least and a greatest element.
- Divisors of n under divisibility form a lattice; with n squarefree it is a Boolean algebra.
Worked example: Divisors of 12 under divisibility
lub is the lcm, glb is the gcd, so it is a lattice. 12 is not squarefree (4 divides it), so it is not a Boolean algebra. Its longest chain is 1, 2, 4, 12, so height 4.
Now play with it
- →Select a = 4 and b = 6 in D₁₂ and read the lub and glb.
- →Switch to the pentagon N₅ and see it is a lattice that is not distributive.
lub(a, b) = a ∨ b = 2 · glb(a, b) = a ∧ b = 1
A Hasse diagram draws only the cover relations (no loops, no transitive edges, direction upward). A lattice needs a lub and a glb for every pair.
| Idea | Definition | Note |
|---|---|---|
| Minimal / maximal | no element strictly below / above | can be several |
| Least / greatest | below / above every element | unique if it exists |
| Upper bound of a, b | x with a ≤ x and b ≤ x | lub = least upper bound |
| Lattice | every pair has a lub (join) and a glb (meet) | every finite chain is a lattice |
| Antichain | pairwise incomparable elements | size of the largest = width |
| Chain | pairwise comparable | height = longest chain |
| Bounded lattice | has a least (0) and greatest (1) element | every finite lattice is bounded |
| Boolean algebra | complemented distributive lattice | 2ⁿ elements, ≅ P(n-set) |
Non-distributive five-element lattices: the diamond M₃ and the pentagon N₅. A lattice is distributive iff it contains neither as a sublattice.
Check yourself
The divisors of 30 under divisibility form a Boolean algebra with how many elements?
Exam notes (the dense version)
Partial order = reflexive + antisymmetric + transitive. A Hasse diagram draws only covering pairs, upward, no loops. Maximal/minimal elements may be several; greatest/least are unique if they exist. A lattice has a lub and glb for every pair. Divisor posets D_n are distributive lattices; D_n is a Boolean algebra iff n is squarefree. A chain of length k has k elements; width is the size of the largest antichain (Dilworth: = minimum number of chains covering).
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.