Consider the set X = {a, b, c, d, e} under partial ordering R = {(a,b),(a,c),(a,d),(a,e),(b,d),(b,e),(c,d),(c,e),(d,e),(a,a),(b,b),(c,c),(d,d),(e,e)}. The Hasse diagram of the partial order (X, R) is shown below. (Hasse diagram: e is the top; d is below e; b and c are below d; a is below both b and c — forming a diamond shape M4.) The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is ______
GATE 2017 · Discrete Mathematics · Lattice · medium
Answer: The minimum number of ordered pairs to add is 0 — the poset (X, R) is already a lattice.
- Identify the structure of the Hasse diagram: The diagram is a 5-element chain-with-diamond: a < b,c < d < e. This is the diamond lattice M4 (or a specific named poset). The pairs to check are (b,c) and any pair involving d and e.
- Verify join and meet for all pairs: join(b,c) = d (smallest element above both b and c), meet(b,c) = a (largest element below both). All other pairs: comparable pairs trivially have join = max and meet = min. Every pair has a unique join and meet in X, so (X, R) is already a lattice.