1.1.6. Question 4: Hasse Diagrams and Partial Orderings

In question number 4, we are supposed to find out the number of partial orderings over a set S consisting of three elements. So, instead of enumerating all possible partial ordering, so what over the set consisting of three elements remember partial ordering means your relation is reflexive, antisymmetric and transitive. So, instead of enumerating all such relations what we will do is we will count the number of distinct Hasse diagrams, which we can draw using these three sets.

In this chunk, we're introduced to Hasse diagrams and partial orderings. A partial ordering is a set with a specific arrangement that respects three properties: reflexivity, antisymmetry, and transitivity. Reflexivity means every element is related to itself, antisymmetry indicates that if one element relates to another, the reverse cannot happen unless both are the same, and transitivity implies if one element relates to a second, and that second relates to a third, then the first must also relate to the third. Hasse diagrams help visualize these partial orderings without needing to enumerate each possible relation.

Think of a family tree where each person is a node. If you consider parent-child relationships, every parent links to their children (reflexivity), and no child can be a parent to the same individual (antisymmetry). Moreover, if a grandparent is related to a grandchild through the parent (transitivity), this arrangement can be easily depicted using a Hasse diagram.

The first category of Hasse diagram is where I have no edges among the nodes. So, I have the nodes a, b, c, where a can be any value in the set {1, 2, 3}, b can be any value in the set {1, 2, 3} and c is any value in the set {1, 2, 3}. What exactly is the relation corresponding to this Hasse diagram? The relation here will be a is related to a, b is related to b, and c is related to c. Remember in Hasse diagram, the directions are not there, self-loops are always implicit, transitively implied edges are also there and so on. So, the relation corresponding to this Hasse diagram is this relation, which is a partial order. Now, the question is how many types of Hasse diagrams of this category I can draw? I can draw only one Hasse diagram like this, because it does not matter whether a is 1 or 2 or 3. The resultant partial ordering will be the same.

Here, we discuss the first category of Hasse diagrams where there are no connections (edges) between the elements. Each element is only related to itself, which maintains the reflexivity property but does not show any relations between different elements. Since it doesn't matter which values are assigned to a, b, or c, there's only one unique diagram with this characteristic.

Imagine three friends standing on their own in a park, each considering their own thoughts (e.g., 'What should I do next?'). They are completely independent of one another when making decisions, representing the lack of connections or relations among them—just like the Hasse diagram with no edges.

My category b Hasse diagram will be like this, where I will have a relation corresponding to the relation where I have a is related to b, b is related to c, and c is related to a. Remember self-loops are always implicitly there. The question is how many partial ordering of this type we can have? In terms of we can have six different partial ordering depending upon what is your value of a and what is your value of b. Because your a could be either 1 or 2 or 3.

In this chunk, we're looking at the second category of Hasse diagrams, where a specific relationship exists: one node serves as a parent to another. This results in a tree structure where you can have different placements of the values for a and b. Since there are different ways a and b can be assigned values from the set, leading to different diagrams, we conclude there are six unique configurations for this relationship.

Consider this scenario: Three siblings, A, B, and C, where A is the eldest (parent to B and C). The arrangement reflecting who influences whom resembles our Hasse diagram here. Depending on which sibling is assigned the title of 'eldest', we will have six different permutations of this family structure.

My category three could be where I have a total ordering among a, b, c, namely by a Hasse diagram is a chain. And it turns out that we can have six partial orderings of this category depending upon whatever my values of a and b. So, I have three choices for a. Once I have fixed a, I have two choices for b and once I have fixed b and a, the third element will be c. So, that is why will have three different Hasse diagrams in this category.

In this third category, we see a scenario where the elements are completely ordered. This means for every pair of elements, you can see a direct relationship represented in the Hasse diagram as a chain. The total number of configurations here is also six because each choice for the highest element influences the order of the others.

Consider a line of people waiting for a bus. Each person (node) has a position (order), and everyone can see who is ahead of them. The arrangement must respect the order; hence one person must be ahead of another, creating a strict hierarchy—precisely what our Hasse diagram captures.

Fourth category is where you have a Hasse diagram where you have a least element and two maximal elements. In this category, we can have three partial orderings depending upon the choice of your least element. Your least element a could be either 1 or 2 or 3. Once you have decided your a, it does not matter whether what is your b and c, they are going to be the remaining two elements. So, that is why if I now count all the different partial orderings and the various categories I get 19 different relations over the set {1, 2, 3} which will be reflexive, antisymmetric and transitive.

In this chunk, we analyze the scenario where a least element exists along with two maximal elements. Depending on which element you choose as the smallest, there are limited ways to assign the remaining two values. This leads to a total of three arrangements in this category, contributing to the overall count of permissible Hasse diagrams.

Think of this like a ranking system in a competition where one contestant must always score the lowest while two contestants may score at their highest levels. No matter how you assign the scores, there's always a clear least performer compared to the top contenders, mirroring the structure in our Hasse diagram.

Finally, if I now count all the different partial orderings and the various categories I get 19 different relations over the set {1, 2, 3} which will be reflexive, antisymmetric, and transitive.

In this concluding chunk, we summarize the counts from the various categories of Hasse diagrams discussed earlier. The total number of distinct possible partial orderings of a set of three elements ultimately reaches nineteen. This final count encapsulates all described relationships while adhering to the properties of partial orders.

Imagine a small company with three employees. They have different roles where one is always a team lead (reflexive), others may serve under it (antisymmetric), and tasks flow in a structured manner (transitive). Summarizing all potential configurations of these employee roles offers insights akin to the 19 distinct arrangements in our study.

--