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:

The resulting graph looks far simpler and is called a Hasse diagram, named after the German mathematician Helmut Hasse (1898−1979).

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 you can see, the Hasse diagram is a useful tool which completely describes the associated partial order.

See solved problems on Page 2.

Page 1 Page 2