24.3.2. Existence and Uniqueness

So, imagine you are given an arbitrary poset less than equal to relationship. This is not again a numerical less than equal to, this is an arbitrary relation, R, which is reflexive, anti symmetric and transitive. Then if I take a pair of elements x, y then the element y is called the cover of element x if the following two conditions hold. The element x should be related to the element y and of course x ≠ y, that is why the less than symbol. And there should not exist any intermediate element ∃z, x ≤ z ≤ y.

In a partially ordered set (poset), we define a relation called 'covering'. For an element y to be the cover of element x, two conditions must be satisfied: first, x must be related to y (meaning x comes before y in the ordering), and second, there should be no element z that fits between x and y that would break this direct relationship. This means y is directly above x without any 'interruptions'.

Think of a stack of books. If book A is directly below book B on the shelf, then book B can be said to cover book A. If there is no other book in between them (like book C), then it is a cover relationship. If book A is below book D, but there is a book C above A and below D, then D does not cover A.

So, it turns out that in a partially partial order set every element need not have a cover. So, for instance, if you take the Hasse diagram on your left-hand side the elements 8 and 12, it does not have any common. There is no element on top of 8, there is no element on top of 12. Similarly, an element can have more than one cover. Both 2 and 3 can cover 1. An element may cover multiple elements.

In a poset, not all elements will necessarily have covers. For example, an element might be at the top of the ordering with no element above it, like elements 8 and 12 in a diagram. Moreover, some elements might cover multiple other elements. For instance, element 6 can cover both elements 2 and 3 if both of these elements come directly below 6 in the ordering.

Consider a hierarchy in a company. A manager may have several team members reporting to them directly (covering multiple elements), while some employees may not have anyone above them (having no cover) if they are at the highest level in their department.

Let us next define what we call as the maximal and minimal element in a poset. So, if you are given an arbitrary poset and an element a from the set S. Then the element a is called as the maximal element if it is on the top most layer informally, or in a loose sense or if it has no cover.

Maximal and minimal elements provide important boundaries within a poset. An element is maximal if there is no other element directly covering it. That means it sits at the top layer of the poset structure. Conversely, an element is minimal if nothing covers it from below—it is at the bottom layer. These definitions help categorize elements based on their position in the ordering structure.

Imagine a building with floors. The top floor can be seen as the maximal element because there is no floor above it, while the ground floor is the minimal element as there are no lower floors. If the 10th floor is the highest point, then it is maximal, and if the ground floor is the starting point, it is minimal.

Now finally let us define what we call as the greatest element and the least element of a poset. So, if you are given a poset S and with an arbitrary relation less than equal to and if you have an element a then the element a of the set S is called as the greatest element if every element b is related to the element a.

A greatest element in a poset is one that is greater than or equal to every other element in the set. Similarly, a least element is less than or equal to every other element. Finding these elements helps in understanding the extremes of the ordering, and if they exist, they have a unique position.

Think of a leaderboard in a game where players have certain scores. The player with the highest score is the greatest element, being better than all others. The player with no score at all is the least element, as they haven't placed higher than anyone, highlighting their position in the league.

It is easy to prove that if you have a poset over a non-empty set, then it has at least one maximal element and one minimal element. For instance, if the poset is defined over a singleton element, then your Hasse diagram will be just a node itself say the element is a only.

Theoremically, for any non-empty poset, there is at least one maximal and one minimal element. This means no matter how complex the poset is, you can find anchors at both ends of the order. A singleton poset, one with only one element, trivially satisfies this by having that sole element as both maximal and minimal.

Consider a sports league with at least one team. Even if some teams are very weak and only one team wins all the matches, there will still be a top team (maximal) and a bottom team (minimal). Even if all other teams are exceptionally bad, there is always at least one team on top and one at the very bottom.

Using all the concepts that we have discussed in, now we will now do a very interesting exercise here, which we call as topological sorting. So, in this topological sorting, you are given a set of tasks which is denoted by S and you are also given a dependency relationship R defined over the task in the set S.

Topological sorting is about ordering tasks based on their dependencies. For instance, if task A must be completed before task B can start, then in the ordered output, A will always come before B. The goal is to list all tasks in such a way that all dependencies are respected.

Imagine cooking a complex meal with multiple dishes. You can’t bake a cake before mixing the batter, so you must list the tasks in a proper order, ensuring that all ingredients are prepared in sequence. This ensures that when you start cooking, you are following the required steps without missing any.

--