23.2.2. Properties 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.

A partial ordering is a way of arranging elements where some elements can be compared to each other. For example, in a dictionary, words are arranged in alphabetical order. Here, a word A is said to precede word B if A appears before B in the dictionary. This arrangement helps us understand relationships between different words.

Think of a library where books are organized alphabetically by the last name of the author. If you are looking for a book by 'Smith', you know that all books by authors beginning with letters A to S will be before it, and you only need to check after S for authors who come after.

It turns out that this alphabetical arrangement of the words in the dictionary satisfies three properties. It satisfies the Reflexive property, it satisfies the Antisymmetric property and it satisfies the Transitive property.

Partial orderings are defined by three key properties:

1. Reflexive Property: Every word can be associated with itself (e.g., 'apple' is before 'apple').
2. Antisymmetric Property: If word A is before word B and word B is also before word A, then A and B must be the same word (you can't have two different words being both before each other in alphabetical order).
3. Transitive Property: If word A is before word B, and word B is before word C, then it implies word A is also before word C (for example, if 'apple' is before 'banana' and 'banana' is before 'cherry', then 'apple' is before 'cherry').

In school, when ranking students based on their grades, if student A has the same score as themselves (reflexive), cannot be ranked both above and below student B (antisymmetric), and if A is ranked above B and B is above C, then A is also ranked above C (transitive).

For instance, imagine I have a big software project. And typically in a big software project you identify various modules, various components which are independent of each other and each of them can be executed by a separate procedure. So, now imagine that I have several such modules and I have defined a relationship or a dependency between the modules by a relation R.

In the context of a software project, modules may depend on one another. If module A must finish before module B can start, we can say that A is 'less than' or precedes B in a partial ordering sense. This relationship, like the alphabetical example, can be reflexive (a module depends on itself), antisymmetric (two modules can't depend on each other without causing a deadlock), and transitive (if A leads to B and B leads to C, then A leads to C).

Consider a cooking scenario where you have to prepare a meal. You must first cook the chicken before adding it to a salad. Here, cooking chicken is before mixing it with other ingredients indicating a dependency just like software modules.

So, let us now generalize this theory. So, we now have 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.

A relation R over a set S qualifies as a partial ordering if it embodies the three previously discussed properties—reflexive, antisymmetric, and transitive. Thus, when we mention a 'partially ordered set' (or poset), we refer to the structure of the set along with this relation R.

Imagine different levels of hierarchy in an organization. Some positions may be equal (like two managers), others have a clear precedence (like a manager above a team leader), forming a partial ordering of authority.

Let me give you some more examples of partial ordering here. So, I consider the set of all positive integers. The relation divides which I am denoting by |, so my relation R is the divide relationship.

The divides relationship means if a number 'a' divides 'b', we can say that 'a' is less than or equal to 'b' in this context. This relation is reflexive (every number divides itself), antisymmetric (two different numbers can’t divide each other), and transitive (if a divides b and b divides c, then a divides c). Thus, this forms a poset over the positive integers.

Think about how you can arrange items into boxes. If one box can perfectly fit another box's contents, there's a division relationship that can be seen akin to how we view numbers dividing each other.

So, 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.

A total ordering ensures that for any two elements in the set, one must relate to the other (either A is less than B, or B is less than A). In contrast, a partial ordering may include elements that aren't comparable. For instance, in a total order, there are no pairs where the relation doesn't hold.

Think of ranking students based on test scores. In a total order, you can directly compare any two students' scores. Conversely, in a partial ordering, some students might not have any direct scores to compare, like students from different subjects.

--