23.1. Discrete Mathematics

Hello everyone, welcome to this lecture on partial orderings. So, we will introduce the definition of partial ordering in this lecture. We will discuss Hasse diagram and we will compute with Topological sorting.

This lecture begins with an introduction to partial orderings, which are ways of arranging elements based on a particular relation. The lecture will cover the definition, properties, and representations of partial orderings, including Hasse diagrams and topological sorting.

Think of partial orderings like a food chain. Some animals rely on others for survival. In this chain, there is a relationship (dependency) between the animals—a lion may depend on a deer, but the deer is not reliant on the lion. This interdependence creates a natural, ordered structure.

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. This alphabetical arrangement of the words can be considered as a relationship.

To understand partial orderings, one can consider how words in a dictionary are arranged. This arrangement forms a relationship based on alphabetical order, which can be described using specific properties: reflexive, antisymmetric, and transitive. If we say 'a appears before b', that creates a directed relationship between the two words.

Imagine a school library where all books are arranged alphabetically by title. When looking for a particular book, you can easily find it because of this systematic arrangement. In a similar way, partial ordering helps in organizing elements based on certain properties, making it easier to analyze relationships.

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.

Reflexive property because implicitly I can always say or I can always assume that a word always appear before itself. That is not true in the sense of the dictionary, but I can always have this implicit order. The alphabetical arrangement of the words satisfies antisymmetric properties because you cannot have two different words such that the word a appears before the word b and simultaneously the word b appears before the word a. And this alphabetical arrangement of the words satisfies the transitive property because if you have the word b appearing after the word a, and if you have the word c appearing after the word b, then you can say that the word c is appearing after the word a.

The properties of a partial ordering include:

1. Reflexive Property: Every element is related to itself. For example, 'word A' can be considered as appearing before 'word A'.
2. Antisymmetric Property: If two different elements are related in both directions, then they must be the same element. In terms of the dictionary, if 'word A' comes before 'word B', then 'word B' cannot come before 'word A'.
3. Transitive Property: If 'word A' comes before 'word B', and 'word B' comes before 'word C', then it follows that 'word A' comes before 'word C'.

Think of a marathon race where three runners compete: Alice, Bob, and Charlie. If Alice finishes before Bob, and Bob finishes before Charlie, we can deduce that Alice finished before Charlie. This reflects the transitive property, and the other properties explain the relationships among runners like their positions and scores.

Imagine that I have several such 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.

This example illustrates how partial orderings can be applied to software development. For instance, if module A must be completed before module B can start, this creates a dependency which satisfies the properties of reflexivity, antisymmetry, and transitivity:

• Each module relies on itself (reflexive),
• No two modules can depend on each other in both ways (antisymmetric), and
• If module A depends on module B, and module B depends on module C, then module A also depends on module C (transitive).

Consider a construction project, where laying foundation (module A) must be finished before constructing walls (module B), and constructing walls must be completed before adding the roof (module C). This structured order follows the principles of partial ordering, ensuring work progresses efficiently.

So, we 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 ordering can be formally defined in terms of set theory. If a set S has a relation R which adheres to the properties of being reflexive, antisymmetric, and transitive, then the combination of set S and relation R forms what is called a 'partially ordered set' or 'poset'. This formal definition allows mathematicians to explore orderings in various mathematical contexts.

Consider a group of students ranked according to their grades. If a student earns a grade (like ‘A’) that is higher than another student’s grade (like ‘B’), and no two students can receive the same rank in reverse, then we can view their grading as a partial ordering system that organizes students according to performance.

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 defined a relation divides which I am denoting by |. So, my relation R is the divides (|) relationship.

Several examples illustrate partial orderings:

1. The set of positive integers with the 'divides' relation (R = a divides b) is a partial ordering. Here, 4 divides 8, while 3 does not divide 4. This satisfies reflexive (every number divides itself), antisymmetric (4 does not divide 3), and transitive (if 4 divides 8 and 2 divides 4, then 2 divides 8).
2. The subset relation in set theory also serves as a partial order, where one set is related to another if it is a subset.
3. The relationship of 'less than or equal to' among real numbers is another example, fulfilling the same properties.

Visualize a hierarchy of tasks in a project. Task A might be a prerequisite for Task B, which in turn is necessary to complete Task C. Each task's completion relates them, fulfilling the conditions for a partial ordering where each task depends on others in a structured way.

Now you take any two elements from the set S. They will be called comparable if a ≤ b or b ≤ a, incomparable otherwise. So again to demonstrate these two concepts let us consider the divide relationship.

In the context of a poset, elements can be classified as comparable or incomparable. Two elements are comparable if one relates to the other via the partial ordering relation (for example, if 4 can be divided by 2). If no such relation exists, they are deemed incomparable (like 5 and 6 in the divides example). This concept helps in understanding the structure of the poset.

Think of two friends looking for different types of jobs—one is seeking a technical role while the other seeks a creative position. While their job searches are important, they do not relate to each other’s conditions and thus are incomparable. This independence is similar to the concept of incomparable elements in partial ordering.

--