23.2.1. Definition of Partial Ordering

So, what is the partial ordering? So, if you consider a dictionary then the words in a dictionary are arranged alphabetically or we also say that the words are arranged lexicographically. And there is a very nice relationship which you can state that holds between the words or relationship holds with respect to the way in which the words are arranged in your dictionary. So, the relationship here is, I say that a word a in the dictionary is related to the word b in my dictionary provided the word a appears before the word b.

Partial ordering is a way of arranging elements based on specific relationships. For example, in a dictionary, words are sorted alphabetically. This means if you have two words, 'apple' and 'banana', 'apple' appears before 'banana', stating that 'apple' is related to 'banana'. This illustrates the basic idea of partial ordering: how one element can be considered as 'before' or 'after' another based on defined criteria.

Think about arranging your books on a shelf by title. Just like in a dictionary, '1984' would come before 'Brave New World'. You can see that each book has a specific position in relation to others based on its title.

This alphabetical arrangement of the words can be considered as a relationship. And it turns out that this alphabetical arrangement of the words in the dictionary satisfies three properties: Reflexive property, Antisymmetric property, and Transitive property.

A partial ordering must meet three specific properties: 1) Reflexive - Every element is related to itself. For example, 'apple' is considered before 'apple' (implicitly true). 2) Antisymmetric - If 'a' is related to 'b' and 'b' is related to 'a', then 'a' must equal 'b'. There can't be two different words that both appear before each other in the list. 3) Transitive - If 'a' is before 'b' and 'b' is before 'c', then 'a' must also be before 'c'. Thus, the relationships create a structured ordering.

Consider a family tree. Each person is related to themselves (Reflexive), two people can't be cousins if they also consider each other siblings (Antisymmetric), and if person A is a grandparent of person B, and person B is the parent of person C, then person A is also the great-grandparent of person C (Transitive). This establishes a clear hierarchy and relationship.

Imagine that I have several modules and I have defined a relationship or a dependency between the modules by a relation R and I say that module i is related to module j if there is a dependency on the module j for the module i. So, I define a relationship R where module i is related to module j provided module j can start only after module i is over.

In a software project, there are often dependencies between different modules. If module 'A' must be completed before module 'B' can begin, we can say that 'A' is related to 'B'. This establishes an order where the execution of 'B' depends on the completion of 'A'. This dependency relationship also exhibits reflexivity, antisymmetry, and transitivity just like the dictionary example.

Think about cooking a recipe. You cannot bake a cake (module B) until you mix the batter (module A). Thus, the mixing step must be finished first. If mixing (step A) is done, then baking can happen (step B), making 'mixing' a prerequisite for 'baking'. This orderly dependency is crucial for the final outcome.

Now, we are now going to define a special type of relation which we call as a partial ordering. So, you are given a set S over which a relation R is defined and it will be called as a partial ordering, if the relation is reflexive, antisymmetric and transitive. In that case, the set S along with the relation R is called a poset.

A partial order set, or poset, is created when a set S has a relation R that meets the three properties of reflexivity, antisymmetry, and transitivity. This formalization allows one to represent complex structures and relationships in mathematics, computer science, and many other fields.

Consider a class of students taking various courses. The students might have different dependencies based on their course prerequisites. If a student can only take Course B after completing Course A, this relationship can be modeled as a poset, showing which course depends on others.

Let me give you some more examples of partial ordering here. So, I consider the set of all positive integers, so this set ℤ+ is the set of positive integers. And I define a relation divides which I am denoting by |. So, my relation R is the 'divides' relationship.

In this example, the relation 'divides' among positive integers demonstrates a partial order. For instance, the integer 2 divides 4 (2 | 4), and every positive integer divides itself (reflexivity). Also, different integers cannot mutually divide each other unless they are the same (antisymmetry). If 'a' divides 'b' and 'b' divides 'c', then 'a' divides 'c' (transitivity). Therefore, the 'divides' relation forms a poset.

Consider the organization of food on a buffet. A large serving platter for lasagna (4 servings) can be used to serve smaller plates (2 servings) but not vice versa. In this way, the relationship between different serving sizes represents a clear order that can be visualized in terms of dependency, just like the integers.

So, now if you are given an arbitrary poset instead of using the notation R for the relation, I use the abstract notation ≤. I stress here that ≤ is just a notation. It is just a substitute for R.

In the context of posets, we can replace explicit relationships with the notation ≤ to simplify discussions. However, it is crucial to remember that this notation does not represent numerical relationships but rather indicates that an element is related to another according to the defined relation R. This distinction helps maintain clarity when using various abstract relations.

Imagine a system of file permissions on a computer. Rather than saying 'file A allows read access to file B,' we might just say 'A ≤ B,' indicating the relationship in a simplified way. This notation helps streamline complex discussions of access rights without losing meaning.

So, let's take any two elements from the set S. They will be called comparable if P ≤ Q or Q ≤ P, incomparable otherwise.

In a poset, elements can be compared. If we can establish a clear relationship between two elements (either indicating one comes before the other), they are said to be comparable. If there is no way to determine a relationship, they are considered incomparable. This concept is critical for understanding the structure within partial orders, where all elements may not have direct relationships forming a hierarchy.

Imagine two students competing for roles in a play. If both are equally talented, they may not have a clear comparison; thus they remain incomparable. However, if one student has prior theater experience, they may be considered 'greater' or more qualified for a lead role, making them comparable.

That brings us to the definition of what we call as a total ordering. A total ordering is a special type of poset or partial ordering where you take any pair of elements from your set S, they will be comparable.

Total ordering is a refinement of partial ordering. In a total order, every pair of elements can be compared, meaning that for any two elements in the set, one is always before the other. For example, in numbers, 1 is less than 2, and 2 is less than 3; thus, every numerical element is comparable. In contrast, partial ordering allows for pairs that may not be comparably arranged.

Think of a ranked list of movies based on viewer ratings. For any two movies on the list, one has to have a higher or lower rating than the other, hence they can be completely ordered. This contrasts with a list of friends where their relationships might not always fit into a strict ranking, illustrating partial ordering.

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 a graphical way to represent the relationships in a poset. These diagrams simplify the relationships by removing redundant information like self-loops (reflecting reflexivity) and transitively implied edges, providing a clearer visual understanding of the relationships between elements in the set.

Imagine a flowchart illustrating the steps in a project. By focusing on key tasks and their dependencies, you can see how one task's completion leads to the start of another without cluttering the diagram with unnecessary details.

--