Total and Partial Ordering

Determining the order of events is a common problem that needs to be solved in software systems.

However, there are two different possible types of ordering: total ordering and partial ordering.

Total ordering

A total order is a binary relation that compares any two elements of a set with each other. As a direct consequence of this property, we can use this relation to derive only a single order for all the elements in a set. This is why it’s called a total order.

Example

If we totally order the set of unique integers $\lbrace 7, 9, 3, 2, 6 \rbrace$ using the relation less than $<$, the associated total order is $[2, 3, 6, 7, 9]$.

Partial ordering

A partial order is a binary relation that can be used to compare only some of the elements of a set with each other. Consequently, we can use this relation to derive multiple, valid orders for all the elements in the set.

Example

The set of the following sets of integers $\{\{0\},\{1\},\{2\},\{0,1\},\{1$ ...