GATE CS 1994 Q2.9 — Partial Orders and Lattices

A lattice is a partially ordered set (poset) in which every pair of elements has a unique least upper bound (LUB or join) and a unique greatest lower bound (GLB or meet). Any finite lattice must have a unique least element ($0$) and a unique greatest element ($1$).

Let us find all non-isomorphic lattices with $n$ elements, where $1 \le n \le 4$:

1. For $n = 1$: (1 lattice)
   • A single element: $\{a\}$.
   • Hasse Diagram: A single vertex.
2. For $n = 2$: (1 lattice)
   • A chain of 2 elements: $0 < 1$.
   • Hasse Diagram: Two vertices connected by a single vertical edge.
3. For $n = 3$: (1 lattice)
   • A chain of 3 elements: $0 < a < 1$.
   • Hasse Diagram: Three vertices connected linearly in a single vertical path.
4. For $n = 4$: (2 lattices)

   Let the elements be $\{0, a, b, 1\}$, where $0$ is the bottom and $1$ is the top. The middle elements $a$ and $b$ can be related in two ways:

   • Case 4a (Chain): $a$ and $b$ are comparable (e.g., $0 < a < b < 1$). This forms a linear chain of 4 elements.
   • Case 4b (Diamond): $a$ and $b$ are incomparable. Here, $a \wedge b = 0$ and $a \vee b = 1$. This forms a diamond-shaped lattice.

Summing these up, the total number of distinct Hasse diagrams for lattices with up to 4 elements is: