GATE CS 1992 Q14b — Partial Orders and Lattices

An algebraic structure $(S, ext{GCD}, ext{LCM})$ is a lattice if the two binary operations (meet $\wedge$ and join $\vee$) satisfy the commutative, associative, and absorption laws. Equivalently, under the partial order of divisibility ($a \le b \iff a \mid b$), every pair of elements must have a unique greatest lower bound (GLB) and a unique least upper bound (LUB).

Let $S = \{1, 2, 3, 4, 6, 8, 12, 24\}$, which is the set of all positive divisors of $24$.

• Greatest Lower Bound (GLB): For any $a, b \in S$, $\text{GLB}(a, b) = \text{GCD}(a, b)$. Since $a$ and $b$ are divisors of $24$, their greatest common divisor is also a divisor of $24$, meaning $\text{GCD}(a, b) \in S$.
• Least Upper Bound (LUB): For any $a, b \in S$, $\text{LUB}(a, b) = \text{LCM}(a, b)$. Since both $a$ and $b$ divide $24$, their least common multiple must also divide $24$, meaning $\text{LCM}(a, b) \in S$.

Since every pair of elements has a unique GLB (GCD) and LUB (LCM) in $S$, the structure is a lattice.

Why other options are incorrect:

• Group: A group requires a single binary operation with an identity and inverses. Under LCM, the identity is $1$, but no element $x > 1$ has an inverse (there is no $y \in S$ such that $\text{LCM}(x, y) = 1$).
• Ring / Field: These structures require two operations where the first operation forms an abelian group. Since neither GCD nor LCM forms a group on $S$, it cannot be a ring or a field.