Suppose Cassiopeia constellation represents the Hasse diagram of a partial order. List the ordered pairs of the relation and determine its binary matrix.
Solution.
Figure 4.
The brightest stars in the Cassiopea constellation are denoted by 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:
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.
Figure 5.
Consider the set 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 and
Show that the relation is a partial order and draw its Hasse diagram.
Solution.
The relation is reflexive since it contains all reflexive pairs:
is antisymmetric since all non-reflexive elements do not have the corresponding inverse pairs:
is transitive:
Hence, the relation is a partial order and we can draw its Hasse diagram, which is represented below.
Figure 6.
Example 4.
Draw the Hasse diagram representing the divisibility relation on set
Solution.
We place at the bottom of the diagram and on the next level. The number is an immediate successor for and is an immediate successor for and so we place and at higher level and connect these pairs by an edge. The number is divisible by and Hence it is placed above them. Similarly, is placed above So, the Hasse diagram will be as follows:
Figure 7.
Example 5.
Let be the divisors of Draw the Hasse diagram for where "|" represents the divisibility relation.
Solution.
The divisors of the number are given by the set
To draw the Hasse diagram, we start with the minimal element at the bottom. On the first level we place the prime numbers and On the second level we put the numbers and since they are immediate successors for the corresponding numbers at lower level. The number should be placed at higher level than and We then connect all elements with their immediate successors. The resulting Hasse diagram is shown in Figure
Figure 8.
Example 6.
Let Draw the Hasse diagram representing the subset relation on the power set
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
The power set contains all subsets of
We place the empty set at the bottom of the diagram. The subsets with one element are placed on the first level, and the subsets with two elements are placed on the next level. The element 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
Figure 9.
Note that the Hasse diagram coincides with the diagram in Example This means that these posets have the same structure. More precisely, such a similarity of structure is called isomorphism.
