GATE CS 1996 Q1.2 — Partial Orders and Lattices

A Hasse diagram of a partially ordered set (poset) represents the elements as vertices, where an edge is drawn from $x$ to $y$ (with $y$ placed higher than $x$) if and only if $y$ covers $x$. That is, $x < y$ and there is no element $z$ such that $x < z < y$.

Given the set $X = \{2, 3, 6, 12, 24\}$ and the partial order relation "divides" ($x \le y$ if $x \mid y$):

• Minimal elements: $2$ and $3$ do not divide each other, so both are minimal elements.
• Covering relations:
  • $6$ is divisible by both $2$ and $3$. Since there are no elements between $2$ and $6$, or between $3$ and $6$, we have the cover relations:
    $(2, 6)$ and $(3, 6)$.
  • $12$ is divisible by $6$. Since there is no element $z \in X$ such that $6 < z < 12$, we have the cover relation:
    $(6, 12)$.
  • $24$ is divisible by $12$. Since there is no element $z \in X$ such that $12 < z < 24$, we have the cover relation:
    $(12, 24)$.

Transitive edges like $(2, 12)$, $(2, 24)$, $(3, 12)$, $(3, 24)$, and $(6, 24)$ are excluded from the Hasse diagram.

Thus, the edges in the Hasse diagram are:

The total number of edges is $4$.