In the lattice defined by the Hasse diagram given in the following figure, how many complements does the element 'e' have? The diagram has top element a and bottom element f, with a covering b, c and g; b covering e; c covering d; and e, g, d each covering f (chains a-b-e-f, a-g-f and a-c-d-f). A. 2 B. 3 C. 0 D. 1
GATE 1997 · Discrete Mathematics · Lattice · medium
Answer: The element e has 3 complements (c, d and g), so the answer is B. 3.
Set up the complement test: the lattice is bounded with top a and bottom f. e lies on the chain a > b > e > f, so the elements >= e are {e, b, a} and the elements <= e are {e, f}. We will join and meet e with each of b, c, d, g.
Test b and the three other elements: e join b = b (since e <= b), so b is not a complement. For c: the smallest element above both e and c is a, and the largest below both is f, so e join c = a and e meet c = f -> c is a complement. The same holds for d (a-c-d-f chain) and for g (a-g-f chain): each joins with e at a and meets with e at f.
Count the complements: exactly three elements satisfy both conditions, namely c, d and g. Hence e has 3 complements.