Hasse Diagrams (Representing Order Relations by Directed Graphs)

Directed Graphs

In what follows, we explain how order relations can be represented visually using the concept of a directed graph.

We denote a directed graph itself by
\[
D
\]A directed graph consists of the following three components.

The first component of a directed graph $D$ is the set of vertices, denoted by \[
V\left( D\right) .
\]An element of the vertex set $V\left( D\right) $ is called a vertex, and we denote it by \[
v.
\]Thus, $v\in V\left( D\right) $.

The second component of a directed graph $D$ is the set of arcs, denoted by \[
A\left( D\right) .
\]An element of the arc set $A\left( D\right) $ is called an arc, and we denote it by \[
a.
\]Thus, $a\in A\left( D\right) $.

The third component of a directed graph $D$ is a mapping \[
\psi_{D}:A\left( D\right) \rightarrow V\left( D\right) \times V\left(
D\right)
\]that assigns to each arc an ordered pair whose components are vertices. This mapping is called the incidence function. If the incidence function $\psi_{D}$ assigns the ordered pair $\left( v_{1},v_{2}\right) \in V\left( D\right) \times V\left( D\right) $ to an arc $a\in A\left( D\right) $, that is, if \[
\psi_{D}\left( a\right) =\left( v_{1},v_{2}\right)
\]holds, we also write
\[
\psi_{D}\left( a\right) =v_{1}v_{2}.
\]In this case, we say that the arc $a$ joins the vertex $v_{1}$ to the vertex $v_{2}$. The vertex $v_{1}$ is called the tail of $a$, while $v_{2}$ is called the head of $a$. The tail and head of an arc are collectively called its ends. The two ends of an arc need not be distinct. When the distinction between the tail and head is ignored, an arc is called an edge.

A directed graph $D$ therefore consists of these three components, and we write \[
D=\left( V\left( D\right) ,A\left( D\right) ,\psi_{D}\right) .
\]

When drawing a directed graph, vertices are represented by points and arcs by directed line segments extending from their tails to their heads.

Example (Directed Graph)

Suppose that the vertex set $V\left( D\right) $ and arc set $A\left( D\right) $ of a directed graph $D$ are \begin{align*}
V\left( D\right) & =\left\{ 1,2,3,4\right\} \\
A\left( D\right) & =\left\{ a,b,c,d,e,f,g\right\}
\end{align*}and that the incidence function $\psi_{D}:A\left( D\right) \rightarrow V\left( D\right) \times V\left( D\right) $ satisfies \begin{align*}
\psi_{D}\left( a\right) & =12,\quad\psi_{D}\left( b\right) =21,\quad
\psi_{D}\left( c\right) =32,\quad\psi_{D}\left( d\right) =43,\\
\psi_{D}\left( e\right) & =41,\quad\psi_{D}\left( f\right) =42,\quad
\psi_{D}\left( g\right) =44.
\end{align*}The directed graph $D$ is shown below.

Ordered Sets as Directed Graphs

A binary relation $\leq$ defined on a set $A$ is a partial order if it satisfies reflexivity, antisymmetry, and transitivity, that is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] .
\end{align*}If, in addition to these properties, $\leq$ satisfies completeness, \[
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right) ,
\]then $\leq$ is called a total order. The following discussion applies to both partial and total orders. We therefore use the term order to refer collectively to partial and total orders. If an order $\leq$ is defined on a set $A$, the pair \[
\left( A,\leq\right)
\]is called an ordered set. When it is clear from context which order $\leq$ is being used, we may simply write the ordered set as \[
A.
\]How can a directed graph be used to represent an ordered set visually?

Given an ordered set $\left( A,\leq\right) $, regard the set $A$ as the vertex set of a directed graph. Then define the arcs and the incidence function so that, for arbitrary vertices $x,y\in A$, \[
x\leq y\Leftrightarrow\text{there is an arc extending from the tail }x\text{
to the head }y.
\]In this way, an ordered set can be represented as a directed graph.

Example (A Partially Ordered Set as a Directed Graph)

Consider the set
\[
A=\left\{ 1,2,3,4\right\}
\]equipped with the usual order $\leq$. Since the usual order is a total order, $\left( A,\leq\right) $ is a totally ordered set. By definition of the usual order, \begin{align*}
1 & \leq1,\quad1\leq2,\quad1\leq3,\quad1\leq4\\
2 & \leq2,\quad2\leq3,\quad2\leq4,\\
3 & \leq3,\quad3\leq4,\\
4 & \leq4
\end{align*}hold. We represent this totally ordered set as a directed graph $D$. Its vertex set is \[
V\left( D\right) =A=\left\{ 1,2,3,4\right\} ,
\]its arc set is
\[
A\left( D\right) =\left\{ a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7},a_{8},a_{9},a_{10}\right\} ,
\]and its incidence function $\psi_{D}:A\left( D\right) \rightarrow V\left( D\right) \times V\left( D\right) $ satisfies \begin{align*}
\psi_{D}\left( a_{1}\right) & =11,\quad\psi_{D}\left( a_{2}\right)
=12,\quad\psi_{D}\left( a_{3}\right) =13,\quad\psi_{D}\left( a_{4}\right)
=14,\\
\psi_{D}\left( a_{5}\right) & =22,\quad\psi_{D}\left( a_{6}\right)
=23,\quad\psi_{D}\left( a_{7}\right) =24,\\
\psi_{D}\left( a_{8}\right) & =33,\quad\psi_{D}\left( a_{9}\right)
=34,\\
\psi_{D}\left( a_{10}\right) & =44.
\end{align*}The directed graph $D$ is shown below. The arc labels are omitted.

Hasse Diagrams and the Cover Relation

If $A$ is a finite set in an ordered set $\left( A,\leq\right) $, that is, if \[
\left\vert A\right\vert <+\infty
\]holds, then $\left( A,\leq\right) $ is called a finite ordered set. A directed graph can be used to represent a finite ordered set visually, but the properties of an order allow us to reduce the amount of information that must be displayed.

Given an order $\leq$ on a set $A$, define the corresponding strict order $<$ on $A$ by \[
x<y\Leftrightarrow x\leq y\wedge x\not =y
\]for arbitrary $x,y\in A$. If \[
x<y
\]holds and there is no $z\in A$ satisfying \[
x<z<y,
\]we write
\[
x\prec y.
\]In other words, define a new binary relation $\prec$ on $A$ by \[
x\prec y\Leftrightarrow x<y\wedge\lnot\left( \exists z\in A:x<z<y\right) .
\]This relation is called the covering relation. If $x\prec y$ holds for $x,y\in A$, we say that $y$ covers $x$. Intuitively, this means that $y$ lies immediately above $x$ under the order $\leq$.

Suppose that we wish to represent a finite ordered set $\left( A,\leq\right) $ as a directed graph. Since the order $\leq$ satisfies reflexivity, \[
\forall x\in A:x\leq x,
\]every vertex $x\in A$ necessarily has an arc whose tail and head are both $x$. Such an arc is called a loop. Since every vertex necessarily has a loop when an ordered set is represented as a directed graph, there is no need to draw these loops explicitly.

Now consider two distinct vertices $x,y\in A$ such that \begin{equation}
x<y\quad \cdots (1)\end{equation}holds. This means that there is an arc from $x$ to $y$. Suppose in addition that \begin{equation}
\exists z\in A:\left( x<z\wedge z<y\right) \quad \cdots (2)\end{equation}holds. In other words, there is a vertex $z$ distinct from $x$ and $y$ such that there is an arc from $x$ to $z$ and an arc from $z$ to $y$. Since the strict order $<$ induced by $\leq$ satisfies transitivity, \[
\forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right) \Rightarrow x<z\right] ,
\]condition $\left( 2\right) $ guarantees condition $\left( 1\right) $. Thus, when both $\left( 1\right) $ and $\left( 2\right) $ hold, there is no need to draw the arc from $x$ directly to $y$. Equivalently, for two distinct vertices $x,y$, we only need to draw an arc from $x$ to $y$ when $\left( 1\right) $ holds but $\left( 2\right) $ does not. By definition of the covering relation, this is precisely the case in which \[
x\prec y
\]holds. Thus, a Hasse diagram needs to display only the covering relations.

Next, suppose that for two distinct vertices $x,y\in A$, \[
x<y
\]holds. This means that there is an arc from $x$ to $y$. Since the strict order $<$ induced by $\leq$ satisfies asymmetry, \[
\forall x,y\in A:\left[ x<y\Rightarrow\lnot\left( y<x\right) \right] ,
\]we have
\[
y<x
\]false. Thus there is no arc from $y$ to $x$. In other words, if two distinct vertices are joined by an arc, there can be only one such direction. Therefore, if we adopt the convention that every arc in the directed graph points upward and place $x$ below $y$ whenever $x<y$, there is no need to draw arrowheads.

We can now summarize the construction. When representing a finite ordered set
$\left( A,\leq\right) $ as a directed graph, the amount of information displayed can be reduced according to the following rules.

For any vertex $x\in A$, do not draw a loop whose tail and head are both $x$.
For distinct vertices $x,y\in A$, if $y$ covers $x$, that is, if \[
x\prec y
\]holds, place $x$ below $y$ and join them by a line. Do not draw an arrowhead.
Do not join vertices that are not related by the covering relation.

A diagram obtained from an ordered set according to these rules is called a Hasse diagram.

Example (Hasse Diagram)

The covering relations are
\[
1\prec2,\quad2\prec3,\quad3\prec4.
\]Therefore, the following Hasse diagram is obtained.
$$\begin{array}{c}4\\ |\\ 3\\ |\\ 2\\ |\\ 1\end{array}$$

Recovering an Order Relation from a Hasse Diagram

By interpreting in reverse the rules used to construct a Hasse diagram from a finite ordered set, we obtain rules for recovering the ordered set from its Hasse diagram.

Suppose that a finite ordered set $\left( A,\leq\right) $ is represented by a Hasse diagram. For any $x\in A$, reflexivity of $\leq$ gives \[
x\leq x.
\]For distinct vertices $x,y\in A$, if there is a finite sequence of covering relations \[
x=x_{0}\prec x_{1}\prec\cdots\prec x_{n}=y,
\]then, by definition of the covering relation,
\[
x=x_{0}<x_{1}<\cdots<x_{n}=y.
\]By transitivity of $<$, it follows that \[
x<y.
\]Hence
\[
x\leq y
\]also holds. Thus, for a finite ordered set, the strict order $<$ can be recovered by applying transitivity to the covering relation, and the original partial order $\leq$ can then be recovered by adding reflexivity.

The rules can be summarized as follows.

For every vertex $x$ appearing in the Hasse diagram, \[
x\leq x
\]holds.
For distinct vertices $x,y$ appearing in the Hasse diagram, if one can start at $x$ and move upward along the lines until reaching $y$, then \[
x\leq y
\]holds.

Example (Hasse Diagram)

Suppose that a binary relation $\leq$ on \[
A=\left\{ 1,2,3,4\right\}
\]is represented by the following Hasse diagram:
$$\begin{array}{c}4\\ |\\ 3\\ |\\ 2\\ |\\ 1\end{array}$$ For the vertices $1,2,3,4$ appearing in the diagram, \begin{align*}
1 & \leq1\\
2 & \leq2\\
3 & \leq3\\
4 & \leq4
\end{align*}hold. Starting from $1$ and moving upward along the lines, one can reach $2,3,4$, so \begin{align*}
1 & \leq2\\
1 & \leq3\\
1 & \leq4
\end{align*}hold. Starting from $2$, one can reach $3,4$, so \begin{align*}
2 & \leq3\\
2 & \leq4
\end{align*}hold. Starting from $3$, one can reach $4$, so \[
3\leq4
\]holds. Therefore,
\[
\leq=\left\{ \left( 1,1\right) ,\left( 1,2\right) ,\left( 1,3\right)
,\left( 1,4\right) ,\left( 2,2\right) ,\left( 2,3\right) ,\left(
2,4\right) ,\left( 3,3\right) ,\left( 3,4\right) ,\left( 4,4\right)
\right\} .
\]

Using Hasse Diagrams to Distinguish Partial and Total Orders

Suppose that a finite ordered set $\left( A,\leq\right) $ is totally ordered. Under a total order, every pair of elements is comparable, so the finitely many elements of $A$ can be arranged as \[
x_{1}<x_{2}<\cdots<x_{n}.
\]The covering relations are
\[
x_{1}\prec x_{2},\quad x_{2}\prec x_{3},\cdots,\quad x_{n-1}\prec x_{n}.
\]Therefore, the Hasse diagram of a finite totally ordered set has the form of a single chain containing all vertices.

By contrast, a partial order may contain incomparable elements, so its Hasse diagram may branch. This difference provides an intuitive way to tell whether an order represented by a Hasse diagram is merely partial or is total.

Example (Hasse Diagram of a Partial Order)

Consider the divisibility relation on
\[
A=\left\{ 1,2,3,6\right\} .
\]That is, define $\leq$ by \[
x\leq y\Leftrightarrow x|y
\]for arbitrary $x,y\in A$. Since divisibility is a partial order, $\leq$ is a partial order. On the other hand, neither $2|3$ nor $3|2$ holds, so $\leq$ does not satisfy completeness and is therefore not a total order. The covering relations are
\[
1\prec2,\quad1\prec3,\quad2\prec6,\quad3\prec6.
\]Hence the following branching Hasse diagram is obtained:
$$\begin{array}{c}6\\ /\quad\backslash\\ 2\qquad3\\ \backslash\quad/\\ 1\end{array}$$

A Note on Infinite Ordered Sets

The discussion so far has mainly concerned the case in which the underlying set $A$ of an ordered set $\left( A,\leq\right) $ is finite. In a finite ordered set, one can move from $x$ to $y$ through a finite sequence of covering relations, so the original order can be recovered from the covering relation.

For an infinite ordered set $\left( A,\leq\right) $, however, this property need not hold. The following example illustrates this point.

Example (Infinite Ordered Set)

Consider the usual order $\leq$ on the set of rational numbers $\mathbb{Q} $. Choose arbitrary distinct rational numbers $x,y\in\mathbb{Q} $. Without loss of generality, suppose \[
x<y.
\]Then
\[
z=\frac{x+y}{2}\in\mathbb{Q} \]and
\[
x<z<y.
\]Thus, between any two distinct rational numbers there is always another rational number. Consequently, there are no rational numbers $x,y$ satisfying \[
x\prec y.
\]Hence there is no covering relation on $\left(\mathbb{Q} ,\leq\right) $. On the other hand, under the usual order there are infinitely many rational numbers $x,y$ satisfying \[
x<y.
\]Therefore, the order relation on $\mathbb{Q} $ cannot be recovered from a diagram displaying only the covering relation.

Exercises

Problem (Hasse Diagram)

Suppose that a binary relation $R$ on \[
A=\left\{ 1,2,3,4,5\right\}
\]is given by
\[
R=\left\{
\begin{array}
[c]{l}\left( 1,1\right) ,\left( 1,3\right) ,\left( 1,4\right) ,\left(
1,5\right) ,\\
\left( 2,2\right) ,\left( 2,3\right) ,\left( 2,4\right) ,\left(
2,5\right) ,\\
\left( 3,3\right) ,\left( 3,4\right) ,\left( 3,5\right) ,\\
\left( 4,4\right) ,\\
\left( 5,5\right)
\end{array}
\right\} .
\]Show that $R$ is a partial order and represent $R$ by a Hasse diagram.

View Solution