23.3.4. Hasse Diagram for Subset Relationship

It turns out that we can represent partial ordering or posets by a very specific type of diagrams which are called as Hasse diagrams.

Hasse diagrams are visual representations for illustrating the relationships among elements in a partially ordered set (poset). They simplify the relationships by showing only the essential connections without redundancies like explicit self-loops or transitively implied edges.

Think of a Hasse diagram like a family tree, where only the direct relationships (parent to child) are shown, rather than listing every other relative's connection. This keeps the structure clear and easy to follow.

So, let me demonstrate this Hasse diagram with this less than equal to relationship which is the numerical less than equal to relationship defined over the set S = {1,2,3,4}.

To create a Hasse diagram, we start by defining the elements and their relationships. Here, we take the set S and the relationship of 'less than or equal to'. This means we will plot the numbers from 1 to 4 in such a way that the lower numbers are beneath the higher ones according to this relationship.

Imagine a stack of boxes where each box is labeled with a number. The box labeled '1' is at the bottom, and each subsequent box (2, 3, and 4) is on top of the previous one, demonstrating who is 'less than' the others.

Now what I can say here is that there is no point of explicitly writing down or stating the self loops. Because I can say that since my relationship is reflexive anyhow, I can always say that the self loops are implicitly present in my diagram.

In constructing a Hasse diagram, we can simplify it further by omitting the self-loops that indicate each element relates to itself. Given the reflexive property of the relation, it is understood that each element is related to itself without needing to depict that on the diagram.

If you think about a team where each member has a defined role, you wouldn't need to label that each member 'is responsible for themselves' because it's implicit. We understand this without needing it spoken.

Then I can remove the transitively implied edges from this diagram and say that hey, since my relation is anyhow transitive, I can remove the edge present from the node 1 to 3.

In a Hasse diagram, once the self-loops are removed, any pairs of elements that have a relationship due to transitivity can also be removed. For example, if 1 ≤ 2 and 2 ≤ 3, we understand that 1 ≤ 3 without needing to show that direct edge. This cleans up the graph and makes it simpler to read.

Think of a chain of command in an organization. If employee A reports to employee B, and employee B reports to employee C, you don’t need to show that A has a direct report to C; it’s implied that C is indirectly connected to A through B.

And now there is no more of information, which I can remove from this graph and say that it still represents my original relationship.

At the end of constructing a Hasse diagram, all unnecessary information is removed, leaving behind a simple, upward-directed diagram. This final illustration maintains the relationships of the original set while making it more visually accessible. Each upward connection reflects the partial order structure.

Consider a simplified map of a city where only main roads are shown, avoiding all side streets. The resulting map provides a clear view of the essential routes one might take without clutter.

So let us see another example here. So you are given the divide (|) relationship. So your ≤ is the divider relationship.

Using the divide relationship, we can create another Hasse diagram that represents how numbers divide each other within a certain set. This involves listing out relevant numbers and their divide relationships, followed by removing self-loops and transitive connections, similar to previous steps.

Think of this relationship as organizing a collection of books based on how one book references another. If Book A references Book B and Book B does further references, you don’t need to show every path explicitly, just the primary connections.

Again, I have removed all the self loops. I have removed all the transitively implied edges and I have removed the direction of the edges.

For the subset relationship, the Hasse diagram helps illustrate how subsets relate to one another within a power set. It shows only the essential connections without clutter from self-loops and transitive edges, allowing one to see the subset structure clearly.

Imagine organizing filing cabinets by categories. Each main file folder (subset) contains various subfolders, and you can see how they relate without needing extra notes on each folder saying what falls under what.

--