Partial Order

Imagine you are shopping groceries online. Like any other task, it will have a subtasks to be performed. You will  first  open the shopping website, add the desired stuff in your cart and then finally proceed to make the payment. It is very clear that you cannot make payment without adding all your items to the cart nor can you add items to cart before opening the website. However, you can add items to the cart in any order. Clearly, there is an ordering between a few events and a few events are independent of each other. The ordering or relation here is happens before and is represented by "->". The independence of events is represented by "<>" or none happen before the other.

A -> B indicates event A  happens before event B.

A <> B indicates event A is independent/incomparable of event B.

Figure 1: Partial Order for online shopping

In formal terms, a partial order defines a  sequence or order  of elements in a set. The term partial determines that not all the elements are comparable. There may exist few pairs of elements that are incomparable i.e. there is no strict ordering between them, any one of the incomparable may happen before the other. A set of elements coupled with a binary relation operator R is a partial order set S  or a poset if the the properties listed below hold for the relation R over the set S.

A binary relation R (Let us take "≤" as an example) is a partial order on set S if and only if it is:
a. Reflexive: Every element is comparable to itself.
[a ≤ a] (This is why < is not a partial order)
b. Antisymmetric: If a ≤ b and b ≤ a, then a = b.
c. Transitive: if a ≤ b and b ≤ c, then a ≤ c.

Partial order sets  are represented using a mathematical diagram called hasse diagram. The vertices in a hasse diagram imply the elements of the set, whereas, the edges signify a relationship. An edge between a and b imply a R b holds true (R is the relationship). For example, Figure 2 represents a hasse diagram for set: {1, 2, 3, 4, 5, 6, 7, 8, 9} over relation "/" (divides), where there is an edge from b to a if a is divisible by b (or a % b =0) . The edge from 2 to 4 represents 4 is divided by 2, same way, no direct edge between 4 and 6 signifies 6 is not divisible by 4.

Figure 2: Hasse Diagram

A few notations used in posets are:
1. Least upper bound: Least upper bound or lub for a pair of elements (a,b) is the lowest element that is greater than both a and b. For example, lub(2,3 ) in the given example is 6.
2. Greatest Lower bound: Greatest lower bound or glb for a pair of elements (a,b) is is the largest element that is lower than both a and b. For example, lub(2,3 ) in the given example is 1.
3. Greatest and the Least element: A hasse diagram or a lattice has at most one greatest and  one least element. If all the other elements are smaller that some element x, then x is greatest element. Same way iff all the other elements re greater than some element y, then y is the least element.
In the above example there is no greatest element but 1 is the least element.
4. Minimal and Maximal elements: If No other element is greater than element x, then x  is the maximal element and vice versa foe minimal element. There can be any number of minimal and maximal elements.
For above example, 8, 9, 5 and 7 are maximal elements, and 1 is minimal.

Partial orders can be employed to model different problems. For example in program scheduling, when multiple  threads are executing there might not be a fixed order in which the program may execute. Like if there are two threads, say T1 and T2  each have two instructions I1 and I2, I1 of T1 may execute before I1 of T2 or vice versa. But I1 from T1 will always execute before I2 from T1(If they are not relaxed).