GATE CS 2017 Set 2 Q21 — Partial Orders and Lattices

A partially ordered set (poset) $(X, R)$ is a lattice if every pair of elements $x, y \in X$ has a unique least upper bound (LUB, join) and a unique greatest lower bound (GLB, meet).

From the given relation $R$, we can trace the Hasse diagram:

• $a$ is the least element (since $a \le x$ for all $x \in X$).
• $e$ is the greatest element (since $x \le e$ for all $x \in X$).
• The elements form two main branches: $a \to b \to c \to e$ and $a \to d \to e$.

Let us verify the existence of LUB and GLB for all pairs of elements:

• For any pair containing the least element $a$ or the greatest element $e$, the GLB and LUB trivially exist.
• For the pair $(b, c)$: since $b \le c$, we have $\text{GLB}(b, c) = b$ and $\text{LUB}(b, c) = c$.
• For the pair $(b, d)$: the only common lower bound is $a$, so $\text{GLB}(b, d) = a$. The only common upper bound is $e$, so $\text{LUB}(b, d) = e$.
• For the pair $(c, d)$: the common lower bounds are $\{a, b\}$, and the greatest among them is $b$ (since $a \le b$), so $\text{GLB}(c, d) = b$. The only common upper bound is $e$, so $\text{LUB}(c, d) = e$.

Since every pair of elements has a unique LUB and GLB, the poset $(X, R)$ is already a lattice. Thus, the minimum number of ordered pairs that need to be added is 0.