# Hasse Diagrams

## Solved Problems

Click or tap a problem to see the solution.

### 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.

### 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.

### 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),}\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.{\left( {4,4} \right),\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 \(5\) brightest stars in the Cassiopea constellation are denoted by \({\alpha ,\beta, \gamma, \delta, \varepsilon},\) so the relation is defined on the set

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

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

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.

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:

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

### 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),}\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.{\left( {4,4} \right),\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:

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

\(R\) is transitive:

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

### 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:

### 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

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.\)

### 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:\)

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.\)

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.