# 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

$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),\left( {\delta ,\delta } \right),\left( {\delta ,\gamma } \right),\left( {\delta ,\alpha } \right),\left( {\delta ,\beta } \right),\left( {\gamma ,\gamma } \right),\left( {\gamma ,\alpha } \right),\left( {\gamma ,\beta } \right),\left( {\alpha ,\alpha } \right),\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.

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),\left( {\beta ,\beta } \right),\left( {\beta ,\delta } \right),\left( {\beta ,\gamma } \right),\left( {\beta ,\iota } \right),\left( {\delta ,\delta } \right),\left( {\delta ,\gamma } \right),\left( {\delta ,\iota } \right),\left( {\gamma ,\gamma } \right),\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),}\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:

$\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),\left( {2,4} \right),\left( {2,5} \right),\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.

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

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

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

$\mathcal{P}\left( A \right) = \left\{ {\varnothing,\left\{ a \right\},\left\{ b \right\},\left\{ c \right\},\left\{ {a,b} \right\},\left\{ {b,c} \right\},\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.$$

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.