Let S = {a, b} and let 2^S (the powerset of S) be the set of all subsets of S. Consider the binary relation 'subset (set inclusion)' on 2^S. Draw the Hasse diagram corresponding to the lattice (2^S, subset).

GATE 2002 · Discrete Mathematics · Lattice · medium

Answer: The Hasse diagram is the diamond: empty set at the bottom, {a,b} at the top, and the incomparable singletons {a} and {b} in the middle; join is union and meet is intersection, so (2^S, subset) is a lattice.

1. List the powerset and the order: with S = {a,b} the four subsets are empty set, {a}, {b}, {a,b}. Under inclusion: empty set subset {a} subset {a,b}, empty set subset {b} subset {a,b}, while {a} and {b} are incomparable (neither contains the other).
2. Find covers and draw the diagram: each cover adds exactly one element. Put the empty set at the bottom, the two singletons {a} and {b} side by side in the middle, and {a,b} at the top, drawing the four cover edges. This is the diamond (2x2 square).
3. Confirm it is a lattice: join is union and meet is intersection, both always subsets of S, so every pair has a unique lub and glb. For instance {a} join {b} = {a,b} and {a} meet {b} = empty set. Hence (2^S, subset) is a (Boolean) lattice.