GATE CS 2004 Q73 — Partial Orders and Lattices

For a finite poset to be a complete lattice, it is necessary and sufficient that it has a least element (bottom) and every pair of elements has a unique least upper bound (LUB, join $\vee$).

Let us analyze the given set $S = \{\{1, 2\}, \{1, 2, 3\}, \{1, 3, 5\}, \{1, 2, 4\}, \{1, 2, 3, 4, 5\}\}$ under the partial order of set containment ($\subseteq$):

• The pair $\{1, 2\}$ and $\{1, 3, 5\}$ has an intersection of $\{1\}$. Since $\{1\} \notin S$, there is no common subset of both in $S$. Thus, they have no lower bound, meaning their greatest lower bound (GLB) does not exist.
• To resolve this, we must include $\{1\}$ in $S$.

Let $S' = S \cup \{\{1\}\}$. In $S'$:

1. $\{1\}$ is a subset of every element in $S'$, making it the unique least element (bottom).
2. Every pair of elements in $S'$ has a unique least upper bound (LUB). For example:
   • $\text{LUB}(\{1, 2\}, \{1, 3, 5\}) = \{1, 2, 3, 4, 5\}$
   • $\text{LUB}(\{1, 2, 3\}, \{1, 2, 4\}) = \{1, 2, 3, 4, 5\}$

Since $S'$ has a least element and a unique LUB for every pair, it is a lattice. Since it is finite, it is also a complete lattice. Thus, adding only $\{1\}$ is necessary and sufficient.