Hasse Diagram of Partially Ordered Sets

Definition

A Hasse diagram of a partially ordered set is a diagram in which:

• each element of the poset is represented by a point or node,
• if one element covers another, the two are joined by a line,
• the larger element is placed higher than the smaller element,
• and all reflexive, transitive, and implied relations are omitted.

Important definition of a poset

A partially ordered set (poset) is a set $P$ together with a relation $\le$ that satisfies:

1. Reflexive

• : $a \le a$ for every $a \in P$

2. Antisymmetric

• : if $a \le b$ and $b \le a$, then $a = b$

3. Transitive

• : if $a \le b$ and $b \le c$, then $a \le c$

Cover relation

In a poset, an element $b$ is said to cover an element $a$ if:

• $a < b$, and
• there is no element $c$ such that $a < c < b$

In a Hasse diagram, we draw a line between $a$ and $b$ only when $b$ covers $a$.

---

Main Content

1. First Concept: Structure of a Hasse Diagram

• A Hasse diagram represents elements as vertices arranged vertically according to the order relation.
• The relation is interpreted as “higher means greater”, so if $a < b$, then $a$ is placed below $b$.
• Only covering relations are shown. This avoids clutter and highlights the essential order structure.

Key features

No arrows

• are usually needed, because the vertical placement already indicates direction.

No reflexive loops

• are drawn, since every element is related to itself in a poset.

No transitive edges

• are drawn, because they are implied automatically.

Example: Divisors of 12 under divisibility

Let the set be: $$\{1,2,3,4,6,12\}$$ ordered by divisibility $(a \mid b)$.

The cover relations are:

• $1$ is covered by $2$ and $3$
• $2$ is covered by $4$ and $6$
• $3$ is covered by $6$
• $4$ is covered by $12$
• $6$ is covered by $12$

A simple Hasse diagram is:

      12
     /  \
    4    6
    |   / \
    2  /   3
     \ /
      1

This diagram shows only the direct order relations.

---

2. Second Concept: How to Construct a Hasse Diagram

• First, identify all elements of the poset and list the order relation clearly.
• Next, determine which pairs are cover relations, meaning one element is directly above another with nothing in between.
• Finally, place the elements in levels from smallest to largest and connect only the covering pairs.

Step-by-step idea

Suppose we have the set: $$\{1,2,3,6\}$$ with divisibility order.

• $1 \mid 2$, $1 \mid 3$, $1 \mid 6$
• $2 \mid 6$
• $3 \mid 6$

Now check which relations are direct:

• $1$ is covered by $2$ and $3$
• $2$ is covered by $6$
• $3$ is covered by $6$

The Hasse diagram is:

    6
   / \
  2   3
   \ /
    1

Important construction rules

• Put minimal elements at the bottom.
• Put maximal elements at the top.
• If two elements are incomparable, they are placed on the same level or in positions that avoid implying a false order.
• Always remove edges that are implied by transitivity.

Why this construction works

The diagram becomes a compact representation of the poset. It shows:

• which elements are immediately related,
• which are minimal or maximal,
• whether the poset has chains or branches,
• and whether it forms a lattice.

---

3. Third Concept: Interpretation and Properties of Hasse Diagrams

• A Hasse diagram allows us to read the poset structure visually and quickly.
• It helps identify important order-theoretic properties such as chains, antichains, minimal elements, maximal elements, least upper bounds, and greatest lower bounds.
• It is widely used in algebra, discrete mathematics, and combinatorics because it simplifies complex order relations.

Chains and antichains

• A chain is a subset where every pair of elements is comparable.
• An antichain is a subset where no two distinct elements are comparable.

Example: In the divisors of 12:

• Chain: $1 < 2 < 4 < 12$
• Antichain: $\{2,3\}$ because neither divides the other

Minimal and maximal elements

• A minimal element has nothing below it.
• A maximal element has nothing above it.

In the divisors of 12:

• Minimal element: $1$
• Maximal element: $12$

Incomparability

Two elements are incomparable if neither is related to the other.

Example: In the divisors of 12:

• $2$ and $3$ are incomparable
• $4$ and $6$ are incomparable

Relation to lattices

A poset is a lattice if every pair of elements has:

• a greatest lower bound (meet)
• a least upper bound (join)

A Hasse diagram helps detect this visually.

Example: In the divisors of 12:

• meet of $4$ and $6$ is $2$
• join of $4$ and $6$ is $12$

So the divisibility poset of divisors of 12 is a lattice.

---

Working / Process

1. Write the set and relation

• Start by identifying the elements and the partial order.
• Example: divisors of 18 under divisibility.

2. Find all cover relations

• Remove relations that are implied through intermediate elements.
• Keep only direct comparisons.
• Example: if $1 < 2 < 6$, then do not draw $1 < 6$ as a separate edge.

3. Draw the diagram from bottom to top

• Place smaller elements lower and larger elements higher.
• Connect only covering pairs.
• Check that incomparable elements are not accidentally shown as ordered.

---

Advantages / Applications

• Makes complex partially ordered structures easy to understand visually.
• Helps identify chains, antichains, minimal elements, maximal elements, and lattice properties.
• Useful in divisibility, subset ordering, algebraic structures, scheduling, and decision hierarchies.

---

Summary

• Hasse diagrams are compact visual representations of posets.
• They show only cover relations and omit reflexive and transitive edges.
• They are useful for understanding order, hierarchy, and lattice structure.
• Important terms to remember: poset, partial order, cover relation, minimal element, maximal element, chain, antichain, lattice