24.4.2.1. Finding Minimal Elements

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 this chunk, we delve into the fundamental concepts of partial order sets (posets) and what it means for one element to cover another. A poset is a set combined with a relationship (less than or equal to) that must be reflexive (related to itself), anti-symmetric (if two elements are related in both directions, they are identical), and transitive (if one is related to a second, which is related to a third, then the first is related to the third). The concept of 'covering' is critical; for y to be a cover of x, y must immediately succeed x without any elements in between them that would create additional layers.

Imagine a staircase where each step represents an element in a poset. If you are standing on step x (element x), the step directly above you, step y (element y), is a ‘cover’ of step x if there is no step between them. If there was a step z between x and y, then y cannot be a cover of x because there is an intermediate step, just as if there was a barrier preventing direct upward movement.

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. More formally, a is called maximal if ∄b ∈ S, b > a. Similarly, we define a minimal element as one which occurs at the lower level of your Hasse diagram or it covers no element.

In poset terminology, maximal elements are those that cannot be surpassed by any other element in the set, meaning no element exists above it in the hierarchical structure, while minimal elements are those that do not cover any other element, representing the lowest points in the hierarchy. The terms are vital for understanding the structure and limits of the poset; for instance, if element 8 is not related to any element above it, it is maximal, while an element like 1 could be minimal if there are no elements below it.

Think of a class of students where the tallest person is likened to the maximal element - no one is taller than them, just like there is no element above a maximal element in a poset. In contrast, the shortest person represents a minimal element, unable to have any classmates shorter than themselves. Maximal elements represent the highest achievements while minimal elements represent starting points in various contexts.

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 example, if the poset is defined over a singleton element, then your Hasse diagram will be just a node itself. Whereas if your set S has multiple elements, there will be some element at the lowermost level and some at the higher most level.

In any non-empty poset, we can guarantee the existence of at least one maximal and one minimal element due to the structure of the set. Even in single-element sets, that single element is trivially both maximal and minimal since there are no other elements to compare it against. For larger sets, these elements will reside at the highest and lowest points of the Hasse diagram, affirming their roles as maximal and minimal.

Imagine a city skyline: there has to be a tallest building (the maximal element) and the shortest one (the minimal element). No two buildings are in the very same height category; thus, even in a diverse city, the limits of structures must be observed, paralleling the relationships found in posets.

Now finally let us define what we call as the greatest element and the least element of a poset. The element a of the set S is called the greatest element if every element b is related to it as per the relation R. Conversely, it is the least element if it is related to every other element.

The greatest element of a poset encompasses the idea that it is 'greater than or equal to' all other elements in that set, while the least element is 'less than or equal to' all. In formal definitions, if an element a is the greatest, then every other element can be observed to relate to a, and vice versa for the least element. The existence of these elements is not guaranteed in every poset; they are unique when they do exist.

Think of the highest student in a scholarship program as the greatest element; they are eligible for all awards above them, while the first to enroll can be seen as the least element. This distinction plays out in various contexts, illustrating how hierarchical structures determine outcomes.

--