Calculus

Set Theory

Set Theory Logo

Hasse Diagrams

Since a partial order is a binary relation, it can be represented by a digraph. When we deal with a partial order, we know that the relation must be reflexive, transitive, and antisymmetric. This allows to simplify the graphical representation of a partially ordered set by taking the following steps:

  • Remove all self loops;
  • Remove all transitive edges;
  • Remove directions on edges assuming that they are oriented upwards. So if \(\require{AMSsymbols}{a \preccurlyeq b,}\) then the vertex \(b\) appears above the vertex \(a.\)

The resulting graph looks far simpler and is called a Hasse diagram, named after the German mathematician Helmut Hasse \(\left( {1898 – 1979} \right).\)

German mathematician Helmut Hasse
Fig.1 Helmut Hasse (1898-1979)

As an example, consider the divisibility relation \(a \mid b\) on the set

\[A = \left\{ {1,2,3,4,5,6,7,8,9,10} \right\}.\]

The directed graph corresponding to this relation looks a bit messy:

Original digraph of the divisibility relation on the set of natural numbers from 1 to 10.
Figure 2.

We can easily convert the original digraph into a Hasse diagram by deleting all loops and transitive edges from the graph. Making sure that the terminal vertex is above the initial vertex, we also remove the arrows on the directed edges. The element \(9\) can be moved to the second level as it is an immediate successor of \(3\). Similarly, \(10\) is an immediate successor of \(2\) and \(5,\) so we also put it on the second level.

The number \(8\) remains on the \(3\text{rd}\) level as it is a direct successor of \(4.\)

The Hasse diagram of the partially ordered set \(\left( {A, \mid} \right)\) is shown in Figure \(3.\) Notice that the vertices in the Hasse diagram are represented by dots rather than by circles.

Hasse diagram of the divisibility relation on the set of natural numbers from 1 to 10.
Figure 3.

As it can be seen, the Hasse diagram is a useful tool which completely describes the associated partial order.


Solved Problems

Click or tap a problem to see the solution.

Example 1

Suppose Cassiopeia constellation represents the Hasse diagram of a partial order.
Cassiopeia constellation as an order relation.
List the ordered pairs of the relation and determine its binary matrix.

Example 2

Let Cancer constellation represent the Hasse diagram of a partial order relation.
Cancer constellation as an order relation.
List the ordered pairs of the relation and find its binary matrix.

Example 3

Let \(A = \left\{ {1,2,3,4,5} \right\}\) and \[{R = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,3} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {2,5} \right),}\right.}\kern0pt{\left.{\left( {3,3} \right),}\right.}\kern0pt{\left.{\left( {3,4} \right),}\right.}\kern0pt{\left.{\left( {3,5} \right),\left( {4,4} \right),}\right.}\kern0pt{\left.{\left( {5,5} \right)} \right\}.}\] Show that the relation \(R\) is a partial order and draw its Hasse diagram.

Example 4

Draw the Hasse diagram representing the divisibility relation on set \[A = \left\{ {1,2,3,4,6,12,24} \right\}.\]

Example 5

Let \(D_{30}\) be the divisors of \(30.\) Draw the Hasse diagram for \(\left( {{D_{30}},\mid} \right),\) where “|” represents the divisibility relation.

Example 6

Let \(A = \left\{ {a,b,c} \right\}.\) Draw the Hasse diagram representing the subset relation \(\subseteq\) on the power set \(\mathcal{P}\left( A \right).\)

Example 1.

Suppose Cassiopeia constellation represents the Hasse diagram of a partial order. List the ordered pairs of the relation and determine its binary matrix.

Solution.

The order of stars in Cassiopeia constellation as a binary relation.
Figure 4.

The \(5\) brightest stars in the Cassiopea constellation are denoted by \({\alpha ,\beta, \gamma, \delta, \varepsilon},\) so the relation is defined on the set

\[A = \left\{ {\varepsilon ,\delta ,\gamma ,\alpha ,\beta } \right\}.\]

Any partial order satisfies the following three properties: reflexivity, antisymmetry, and transitivity. Keeping this in mind, the list of the ordered pairs of the relation is given by

\[{\left( {\varepsilon ,\varepsilon } \right),\left( {\varepsilon ,\delta } \right),\left( {\varepsilon ,\gamma } \right),\left( {\varepsilon ,\alpha } \right),\left( {\varepsilon ,\beta } \right),}\kern0pt{\left( {\delta ,\delta } \right),\left( {\delta ,\gamma } \right),}\kern0pt{\left( {\delta ,\alpha } \right),\left( {\delta ,\beta } \right),}\kern0pt{\left( {\gamma ,\gamma } \right),\left( {\gamma ,\alpha } \right),}\kern0pt{\left( {\gamma ,\beta } \right),\left( {\alpha ,\alpha } \right),}\kern0pt{\left( {\alpha ,\beta } \right),\left( {\beta ,\beta } \right).}\]

In matrix form, the partial order relation is represented by the upper triangular matrix:

\[{M_{Cassiopeia}} = \left[ {\begin{array}{*{20}{c}} 1&1&1&1&1\\ 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&0&1&1\\ 0&0&0&0&1 \end{array}} \right].\]

As you can see, this relation is a total order.

Example 2.

Let Cancer constellation represent the Hasse diagram of a partial order relation. List the ordered pairs of the relation and find its binary matrix.

Solution.

Cancer constellation as an order relation.
Figure 5.

Consider the set \(B = \left\{ {\alpha ,\beta ,\delta ,\gamma ,\iota } \right\}.\) The elements of the set denote stars in the constellation. Since the given relation is a partial order, it must have three properties: reflexivity, antisymmetry, and transitivity. Therefore it contains the following ordered pairs:

\[{\left( {\alpha ,\alpha } \right),\left( {\alpha ,\delta } \right),\left( {\alpha ,\gamma } \right),\left( {\alpha ,\iota } \right),}\kern0pt{\left( {\beta ,\beta } \right),\left( {\beta ,\delta } \right),}\kern0pt{\left( {\beta ,\gamma } \right),\left( {\beta ,\iota } \right),}\kern0pt{\left( {\delta ,\delta } \right),\left( {\delta ,\gamma } \right),}\kern0pt{\left( {\delta ,\iota } \right),\left( {\gamma ,\gamma } \right),}\kern0pt{\left( {\gamma ,\iota } \right),\left( {\iota ,\iota } \right).}\]

The partial order relation can be easily converted into matrix representation:

\[{M_{Cancer}} = \left[ {\begin{array}{*{20}{c}} 1&0&1&1&1\\ 0&1&1&1&1\\ 0&0&1&1&1\\ 0&0&0&1&1\\ 0&0&0&0&1 \end{array}} \right].\]

Example 3.

Let \(A = \left\{ {1,2,3,4,5} \right\}\) and \[{R = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,3} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {2,5} \right),}\right.}\kern0pt{\left.{\left( {3,3} \right),}\right.}\kern0pt{\left.{\left( {3,4} \right),}\right.}\kern0pt{\left.{\left( {3,5} \right),\left( {4,4} \right),}\right.}\kern0pt{\left.{\left( {5,5} \right)} \right\}.}\] Show that the relation \(R\) is a partial order and draw its Hasse diagram.

Solution.

The relation \(R\) is reflexive since it contains all reflexive pairs:

\[\left( {1,1} \right),\left( {2,2} \right),\left( {3,3} \right),\left( {4,4} \right),\left( {5,5} \right).\]

\(R\) is antisymmetric since all non-reflexive elements do not have the corresponding inverse pairs:

\[{\left( {1,3} \right),\left( {1,4} \right),\left( {1,5} \right),\left( {2,3} \right),}\kern0pt{\left( {2,4} \right),\left( {2,5} \right),}\kern0pt{\left( {3,4} \right),\left( {3,5} \right).}\]

\(R\) is transitive:

\[{\left( {1,3} \right) \in R,\;\left( {3,4} \right) \in R \to \left( {1,4} \right) \in R;}\]

\[{\left( {1,3} \right) \in R,\;\left( {3,5} \right) \in R \to \left( {1,5} \right) \in R;}\]

\[{\left( {2,3} \right) \in R,\;\left( {3,4} \right) \in R \to \left( {2,4} \right) \in R;}\]

\[{\left( {2,3} \right) \in R,\;\left( {3,5} \right) \in R \to \left( {2,5} \right) \in R.}\]

Hence the relation \(R\) is a partial order and we can draw its Hasse diagram, which is represented below.

Hasse diagram of a relation R on the set A={1,2,3,4,5}.
Figure 6.

Example 4.

Draw the Hasse diagram representing the divisibility relation on set \[A = \left\{ {1,2,3,4,6,12,24} \right\}.\]

Solution.

We place \(1\) at the bottom of the diagram and \(2, 3\) on the next level. The number \(4\) is an immediate successor for \(2,\) and \(6\) is an immediate successor for \(2\) and \(3,\) so we place \(4\) and \(6\) at higher level and connect these pairs by an edge. The number \(12\) is divisible by \(4\) and \(6.\) Hence it is placed above them. Similarly, \(24\) is placed above \(12.\) So, the Hasse diagram will be as follows:

Hasse diagram for the divisibility relation on the set A={1,2,3,4,5,12,24}.
Figure 7.

Example 5.

Let \(D_{30}\) be the divisors of \(30.\) Draw the Hasse diagram for \(\left( {{D_{30}},\mid} \right),\) where “|” represents the divisibility relation.

Solution.

The divisors of the number \(30\) are given by the set

\[D_{30} = \left\{ {1,2,3,5,6,10,15,30} \right\}.\]

To draw the Hasse diagram, we start with the minimal element \(1\) at the bottom. On the first level we place the prime numbers \(2, 3,\) and \(5.\) On the second level we put the numbers \(6, 10,\) and \(15\) since they are immediate successors for the corresponding numbers at lower level. The number \(30\) should be placed at higher level than \(6, 15,\) and \(10.\) We then connect all elements with their immediate successors. The resulting Hasse diagram is shown in Figure \(8.\)

Hasse diagram of the divisibility relation on the set of divisors of 30.
Figure 8.

Example 6.

Let \(A = \left\{ {a,b,c} \right\}.\) Draw the Hasse diagram representing the subset relation \(\subseteq\) on the power set \(\mathcal{P}\left( A \right).\)

Solution.

It is known that the subset relation on a power set is a partial order. Hence, we can draw the Hasse diagram for the poset \(\left( {\mathcal{P}\left( A \right), \subseteq } \right).\)

The power set \(\mathcal{P}\left( A \right)\) contains all subsets of \(A:\)

\[\require{AMSsymbols}{\mathcal{P}\left( A \right) = \left\{ {\varnothing,\left\{ a \right\},\left\{ b \right\},\left\{ c \right\},\left\{ {a,b} \right\},\left\{ {b,c} \right\},}\right.}\kern0pt{\left.{\left\{ {a,c} \right\},\left\{ {a,b,c} \right\}} \right\}.}\]

We place the empty set \(\varnothing\) at the bottom of the diagram. The subsets with one element \({\left\{ a \right\},\left\{ b \right\},\left\{ c \right\}}\) are placed on the first level, and the subsets with two elements \({\left\{ {a,b} \right\},\left\{ {b,c} \right\},\left\{ {a,c} \right\}}\) are placed on the next level. The element \({\left\{ {a,b,c} \right\}}\) occupies the top of the diagram. Finally we connect the subsets with their immediate successor with respect to the inclusion relation. The resulting diagram is shown in Figure \(9.\)

Hasse diagram of the subset relation on the power set of A={a,b,c}.
Figure 9.

Note that the Hasse diagram coincides with the diagram in Example \(5.\) This means that these posets have the same structure. More precisely, such a similarity of structure is called isomorphism.