23.2.10. Definition of Total Ordering

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. That means either a will be related to b or b is related to a and that is why the name total ordering because you do not have any pair of incomparable elements.

In discrete mathematics, a total ordering is a specific kind of ordering for a set where each element can be compared with every other element. Specifically, for any two elements a and b in the set S, one of the following must hold true: either a is related to b or b is related to a. This implies that there is a clear way to arrange the elements according to the ordering relation, which makes it different from a general partial ordering where some pairs of elements may not be comparable.

Imagine a race where all participants are ranked based on their finishing times. If someone finishes before another, we can discuss their relative rankings. In this case, for any two racers, one will always have a better or equal rank compared to the other, which exemplifies total ordering. Conversely, consider a scenario where we are sorting books based on genres—some genres might not have a direct ranking, illustrating a partial ordering.

Whereas partial ordering the name partial denotes there, that you have ordering which is only partial. That means you may have a pair of incomparable elements and your relation R whereas a total ordering means you do not have any pair of incomparable elements. ∀a,b ∈ S, a ≤ b or b ≤ a.

The term 'partial ordering' implies that within the set, some elements may not be directly comparable with others; hence, their relationships may not be defined. In contrast, total ordering ensures that every element can relate to every other element in some way. The notation used for a general relation in a poset is ≤, which indicates that one element can be less than or equal to another, but total ordering solidifies that this relation must apply to all pairs within the set.

Consider a classroom of students where their scores on a test represent their ranks. In a total ordering scenario, every student can be compared based on their scores, where one student can be said to have a higher score than another. However, if we instead consider students sorted by their favorite subjects, we may find that some students don't have a clear winner over one another, hence illustrating a partial ordering.

If I consider the less than equal to relationship namely, the numerical less than equal to relationship over the set of integers, then it is a total ordering. You take any pair of integers numerically either the first integer will be less than equal to the second integer or the second integer will be less than equal to the first integer.

The less than or equal to relation (≤) on integers is a classic example of total ordering. For any two integers a and b, you can always state that either a is less than or equal to b or b is less than or equal to a. This universal comparability among all integers fulfills the criteria of a total ordering, thus making the set of integers a totally ordered set.

Think about organizing a collection of books on a shelf according to their publication year. Each book can be compared to every other book based on its publication date. This arrangement allows you to list books from the earliest published to the most recently published, reflecting a clear total order.

Whereas if you take the divides relationship, where a is related to b, provided a divides b then this is not a total ordering. Because 2 is not less than equal to 3 and 3 is also not less than equal to 2. So, 2 and 3 are incomparable elements.

The divides relationship, denoted by |, exemplifies a partial ordering rather than a total ordering. For example, considering the numbers 2 and 3, it becomes clear that neither divides the other. Hence, they are incomparable under the divides relation, demonstrating that not all pairs of elements relate under this ordering.

Imagine organizing tasks by deadlines in a project. Some tasks might not affect each other, meaning the completion of one does not dictate the completion of another. For example, Task A doesn't necessarily relate to Task B in terms of priority or dependency, showcasing a situation of incomparability akin to the divides relationship.

--