Category Theory Illustrated – Orders
An exploration of the mathematical nature of orders, distinguishing between total and partial orders through the laws of reflexivity, transitivity, antisymmetry, and totality.
Given a set of objects, there can be numerous criteria, based on which to order them (depending on the objects themselves) — size, weight, age, alphabetical order etc.
However, currently we are not interested in the criteria that we can use to order objects, but in the nature of the relationships that define order. Of which there can be several types as well.
Mathematically, the order as a construct is represented (much like a monoid) by two components.
An order is a set of elements, together with a binary relation between the elements of the set, which obeys certain laws.
And the binary relation is a relation between two elements, which is often denoted with an arrow.
As for the laws, they are different depending on the type of order.
Let’s start with an example — the most straightforward type of order that you think of is linear order i.e. one in which every object has its place depending on every other object. In this case the ordering criteria is completely deterministic and leaves no room for ambiguity in terms of which element comes before which. For example, order of colors, sorted by the length of their light-waves.
In programming, orders are defined by providing a function which, given two objects, tells us which one of them is “bigger” (comes first) and which one is “smaller”.
[1, 3, 2].sort((a, b) => {
if (a > b) {
return true
} else {
return false
}
})
However, not all such functions define orders. To really define an order, it has to obey several rules.
A linear order is a set of elements, together with a binary relation between the elements of the set, which obeys the laws of reflexivity, transitivity, antisymmetry, totality.
- Reflexivity: each object has to be bigger or equal to itself ($a ≤ a$).
- Transitivity: if object $a$ is bigger than object $b$, it is automatically bigger than all objects that are smaller than $b$ ($a ≤ b \land b ≤ c \to a ≤ c$).
- Antisymmetry: the function should not give contradictory results ($x ≤ y \land y ≤ x \to x = y$).
- Totality: all elements that belong to the order should be comparable ($a ≤ b \lor b ≤ a$).
Orders that don’t follow the totality law are called partial orders (or posets). Every linear order is also a partial order, but not the other way around. Partial orders are much more interesting as they allow for elements that cannot be compared directly, representing more complex hierarchies.
Source: Hacker News
