Consider the set X = {a, b, c, d, e} under partial ordering R = {(a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,e), (c,c), (c,e), (d,d), (d,e), (e,e)}. The Hasse diagram of the partial order (X, R) is shown below (a is the bottom element; a is covered by b and d; b is covered by c; c and d are each covered by the top element e). 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: Every pair already has a unique join and meet, so (X, R) is already a lattice; the minimum number of ordered pairs to add is 0.
Read the order and isolate the incomparable pairs: From R the strict relations are a < b < c < e and a < d < e, with a the bottom and e the top. Comparable pairs trivially have join = larger and meet = smaller element. The only incomparable pairs are {b, d}, {c, d} (b vs d and c vs d), so these are the ones to verify.
Check uniqueness of join and meet for each incomparable pair: For {b, d}: common lower bounds = {a} so meet = a (unique); common upper bounds = {e} so join = e (unique). For {c, d}: common lower bounds = {a} so meet = a (unique); common upper bounds = {e} so join = e (unique). Every pair therefore has a unique LUB and GLB, so (X, R) is already a lattice. No ordered pairs need to be added: the minimum is 0.