Hasse Diagram is created for POSET or Partially Ordered Set. It means that there is a set of elements in which certain element are ordered, sequenced or arranged in some way. It is usually denoted as ≤, this is not “Less than, Equal to”, this symbol shows that elements are ordered.
Now, there is a relation among all the elements in the partial order set and it is some binary relation R, this relation must satisfy following properties
- Reflexive
- Anti-Symmetric
- Transitive
Example Problem
Reflexive Property
Anti-Symmetric Property
Transitive Property
Hasse Diagram
Rules for Hasse Diagram
- If x < y, then in the graph x appears lower to y.
- We draw line segment between x and y only if x cover y or y cover x, it means some order is maintained between them.
Step 1
Due to the reflexive property all elements have direct edge to itself.
![Hasse Diagram showing all relations Hasse Diagram showing all relations](https://notesformsc.org/wp-content/uploads/2016/11/hasse.png)
In this diagram, it shows the relations removed all the self-directing loops.
![All Self-Directing Edges Removed All Self-Directing Edges Removed](https://notesformsc.org/wp-content/uploads/2016/11/hasse-2.png)
Step 2
The green lines shows transitivity, so we remove all the transitive lines. Out diagram look like the following.
![Hasse Diagram without Transition and Loops Hasse Diagram without Transition and Loops](https://notesformsc.org/wp-content/uploads/2016/11/hasse3.png)
Step 3
Replace all the vertices with dots and directed edges with ordinary lines. This final diagram is called the Hasse Diagram of poset.
![Hasse Diagram for A = { 1, 3, 5, 12, 15 } and relation a | b i.e., a divides b Hasse Diagram for A = { 1, 3, 5, 12, 15 } and relation a | b i.e., a divides b](https://notesformsc.org/wp-content/uploads/2016/11/Hasse-Diagram.png)
Exercise
Here is an exercise for you to practice. The prerequisite for Hasse Diagram is to know how to represent relations using graphs.
Let A be a poset, A = { 2, 4, 6, 8 } and the relation a | b is ‘a divides b. Draw a Hasse Diagram for the poset showing all the relations.