GATE CS 2005 Q9 — Partial Orders and Lattices

The given Hasse diagram represents the classic pentagon lattice, often denoted as $N_5$. It consists of the elements $\{a, b, c, d, e\}$ with the following relations:

• $a$ is the least element (bottom).
• $e$ is the greatest element (top).
• One path goes from $a \to b \to c \to e$.
• Another path goes from $a \to d \to e$.

1. Checking if the poset is a Lattice

A poset is a lattice if and only if every pair of elements has a unique least upper bound (LUB or join, $\vee$) and a unique greatest lower bound (GLB or meet, $\wedge$).

• For comparable elements, the LUB and GLB always exist (e.g., $b \prec c \implies b \vee c = c$ and $b \wedge c = b$).
• For incomparable elements $b$ and $d$:
  • $\text{LUB}(b, d) = b \vee d = e$
  • $\text{GLB}(b, d) = b \wedge d = a$
• For incomparable elements $c$ and $d$:
  • $\text{LUB}(c, d) = c \vee d = e$
  • $\text{GLB}(c, d) = c \wedge d = a$

Since every pair has a unique LUB and GLB, the poset is a lattice.

2. Checking if the lattice is Distributive

A lattice is distributive if it satisfies the distributive law for all elements $x, y, z$:

Let us test this with $x = c$, $y = b$, and $z = d$:

• Left-Hand Side (LHS): $$c \wedge (b \vee d) = c \wedge e = c$$
• Right-Hand Side (RHS): $$(c \wedge b) \vee (c \wedge d) = b \vee a = b$$

Since $\text{LHS} \neq \text{RHS}$ ($c \neq b$), the distributive law does not hold. Thus, the lattice is not distributive.

Therefore, the poset is a lattice but not a distributive lattice.