Calculus

Set Theory

Set Theory Logo

Hasse Diagrams

Solved Problems

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

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

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

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

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.

Page 1 Page 2