Mathematics behind Comparison #2: Ordering Relations in Math

In order to sort a collection of elements you need to provide a sorting predicate that determines when one element is less than the other. This predicate must “induce a strict total ordering on the equivalence classes” according to cppreference. Wait, what?

The upcoming C++ spaceship operator implements a three way comparison, i.e. it is a single function that can return the results of <, == and > combined. But related to it are terms like “strong equality” and “weak ordering” which are somewhat confusing if you don’t have the mathematical background.

So let’s untangle it: This series will explain both the mathematics behind equality and ordering, as well as give concrete guidelines for implementing the comparison operators and the spaceship operator.

This part covers the mathematics behind ordering relations. They are a lot more complicated than equivalence relations we’ve looked at before. As my blog posts are usually long anyway, I’ve decided to split it into two. So this part is only about the mathematics while the next part—already published—is about how they should be implemented in C++.

Ordering between Elements

Consider any two elements a,b from a set A. They can have one of the following relationships:

• a and b can be equal (i.e. a = b)
• a can be less than b
• a can be greater than b
• a can be equivalent to b (i.e. neither less nor greater but also not equal)
• a and b are incomparable (i.e. neither less nor greater nor equal nor equivalent)

As such the ideal comparison relation would be able to return the entire relationship between a and b at once. But if you remember the first part of the series, a binary relation is defined by listing all pairs that are in the relation. In other words: it can just give you a boolean result, either the pairs are in the relation or they aren’t.

Thus an ordering relation is defined in terms of a binary relation that will answer only one of those questions. The others are deduced based on that answer.

Candidates for the binary relation are “a less than b”, “a less than or equal to b”, “a greater than b” and “a greater or equal to b”. Sadly, two different theories were developed: one based on “a less than b” and one based on “a less than or equal to b”.

This can be confusing, so let’s be very careful when looking at them.

≤ Ordering Relations: Preorder

The most fundamental ordering relation for “less than or equal” is a preorder: It is a (very) generalized ≤.

What are the fundamental properties of ≤?

• Every element is less than or equal to itself, so it is reflexive (a ≤ a is true for all a).
• When a ≤ b and b ≤ c, then also a ≤ c, so it is transitive.

A preorder has only those two properties, which means it just barely qualifies to be an order.

As an example, consider a directed graph. We say that node B is reachable from A if there is a path starting at A that eventually leads to B. If B is reachable from A, we write A ↦ B.

This ↦ relation is a preorder: Every node is reachable from itself (A ↦ A) by simply staying where you are, thus it is reflexive. And if A ↦ B and B ↦ C then we can concatenate both paths and have a path from A to C, so A ↦ C meaning it is transitive as well.

But note that if we have a graph that is not connected, we can have two nodes A and B where neither A ↦ B nor B ↦ A, as there is simply no way to go from A to B in either direction!

So if you have a preorder, there is no guarantee that you can compare every element with every other elements, there are elements that are incomparable. If we don’t want want incomparable elements, we want a total relation: A binary relation R is total, if for every pair of elements a and b, a R b or b R a, or both.

As such a total preorder is a binary relation without incomparable elements: Either a is less than or equal to b or b is less than or equal to a (or both!). ↦ is total for graphs where we can reach every node from every other node.

Now, what does it mean if both a ≤ b and b ≤ a for an arbitrary preorder ≤?

Well, with a “traditional” ≤ it means that the elements are equal. So maybe with this more “general” ≤ it means they are equivalent?

And indeed they are: We can define an equivalence relation (let’s call it ~) by saying a ~ b if and only if a ≤ b and b ≤ a. Let’s check that it is actually an equivalence relation:

• for every a it is true that a ≤ a and so naturally a ~ a (reflexive)
• if a ~ b, then a ≤ b and b ≤ a, so also b ≤ a and a ≤ b, so b ~ a (symmetric)
• if a ~ b and b ~ c, then a ≤ b and b ≤ a and b ≤ c and c ≤ b, so due to the transitivity of ≤ it must also be true that a ≤ c and c ≤ a, meaning a ~ c (transitive)

For that reason preorders are often called ≲ because they are not < or = but < or ~. The equivalence relation defined by ↦ puts every element in a relationship that are reachable in both directions.

Finally, consider the example of a undirected graph. Now A ↦ B implies B ↦ A because we can just walk the path in reverse. This means that our preorder is symmetric. But a binary relation that is reflexive, transitive and symmetric is an equivalence relation! So an equivalence relation is just a specialized preorder.

Question for the reader: is an equivalence relation total?

To summarize, given a preorder ≲, two elements can either be:

• less than (i.e. a ≲ b but not b ≲ a)
• greater than (i.e. b ≲ a but not a ≲ b)
• equivalent (i.e. a ≲ b and b ≲ a)
• incomparable (neither a ≲ b nor b ≲ a), only for a preorder that is not total.

Note that there is no way to check for equality using a preorder.

≤ Ordering Relations: Partial and Total Order

What if we want to have an ordering relation where we can get true equality instead of some equivalence?

Then we need antisymmetry: A binary relation R is antisymmetric if a R b and b R a is both true, then also a = b (and vice-versa).

When we have a preorder that is antisymmetric we have a partial order: A binary relation that is reflexive, transitive and antisymmetric. Now we can truly use the symbol ≤ because it really means “less than or equal”.

The “is reachable from” relation ↦ was a preorder. But it is not a partial order: we can have A ↦ B and B ↦ A for A ≠ B (they just need to be part of the same cycle).

The canonical example for a partial order is related to sets: Sets just contain elements, but the same element can be in multiple sets. If we have a set A that contains some elements and a set B that contains the same elements (plus maybe some more), we say that A is a subset of B (every element of A is also an element of B), written as A ⊆ B.

Note that the ⊆ operator looks a lot like ≤!

For example, let A = {1, 2, 3, 4} and B = {0, 1, 2, 3, 4, 5}. Then A ⊆ B. However, for C = {2, 3, 4, 5} it is not true that A ⊆ C because A contains a 1 but C doesn’t.

The subset relation is obviously a preorder, but it is also a partial order: if every element of A is an element of B (A ⊆ B) and every element of B is an element of A (B ⊆ A), A and B must contain the same elements. So A = B meaning ⊆ is antisymmetric.

As the name implies, a partial order is, well, partial, i.e. not total. Consider A = {1, 2} and B = {3, 4, 5}. A and B contain completely different elements, so neither A ⊆ B nor B ⊆ A which means that they are incomparable.

If we have a partial order without incomparable elements, it is called a total order. This is a binary relation that is reflexive, transitive, antisymmetric and total.

They are the ≤ relations you intuitively now, like the ≤ relation on numbers.

To summarize, given a partial order ≤, two elements can either be:

• less than (i.e. a ≤ b but not b ≤ a)
• greater than (i.e. b ≤ a but not a ≤ b)
• equal (i.e. a ≤ b and b ≤ a)
• incomparable (neither a ≤ b nor b ≤ a), but only for a partial order.

Note that the only difference to a preorder is the equality instead of the equivalence.

< Ordering Relations: Strict Partial and Strict Total Order

Let’s look at the ordering relations defined in terms of < now. They are obviously not reflexive because a < a is never true. Instead they are irreflexive which just states that a < a is never true.

Let’s start in the similar spirit as we did with the preorder: With a binary relation that is irreflexive and transitive. Such a binary relation is called a strict partial order.

Wait, what?

Why is it not called a “strict preorder”?

Because it gets additional properties automatically: It is transitive so a < b and b < c implies a < c. This means that if we have a < b and b < a, it would imply that a < a! This is a contradiction with the irreflexive property, so there are no two elements a, b where a < b and b < a is true at the same time. A binary relation where this is true is called asymmetric. As such every binary relation that is irreflexive and transitive is also asymmetric.

And now consider what happens if we extend the < order to a ≤ by adding all (a, a) pairs to the set. If a ≤ b and b ≤ a is true, then the asymmetry means that a = b. This means the extension of an irreflexive and transitive binary relation is a partial order. And if we start with a partial order and remove all (a, a) pairs, we end up with an irreflexive and transitive binary relation.

So an irreflexive and transitive binary relation is called a strict partial order.

As an example of a strict partial order we can take the subset relation A ⊆ B and transform it into a strict subset relation A ⊂ B which is only true if B contains the same elements at A but is not equal to A. And again, a strict partial order doesn’t need to be total. The same set example is also valid now and shows to incomparable elements.

And yet again, if we have a strict partial order that is total, we call it a strict total order.

But wait: we said a binary relation is total if either a < b or b < a for all a and b. But the asymmetry means that a < a is never true, so it can’t be total!

So a strict total order isn’t actually total. Instead we have what’s called trichotomy: for every two elements a, b, either a < b or b < a or a = b (but only exactly one of those is true at the same time).

For a strict partial order if we have neither a < b nor b < a then either the elements are equal or they are incomparable. For a strict total order it means they are equal.

This means that strict partial orders are “less powerful” than partial orders. Given a strict partial order <, two elements can either be:

• less than (i.e. a < b)
• greater than (i.e. b < a)
• equal or incomparable (i.e. neither a < b nor b < a), but we don’t know which one!

Only for a strict total order can we deduce that two elements are actually equal.

< Ordering Relations: Strict Weak Order

Let’s try to define a strict preorder again, i.e. a strict ordering relation which (somehow) implies equivalence not equality.

Let’s look at the set of colors from the previous post again: C := {yellow, red, green, blue, cyan, magenta}. We can define a strict partial (and in this case, total) order “is uglier than” by arranging them in the following order: magenta < cyan < green < red < blue < yellow. We say that a color is < than another color if it is listed in this list first.

And yes, this is the only way to define that “is uglier than” relation. Every other order is wrong.

Last time we did my equivalence relation of colors, where cyan is just an ugly blue. The corresponding total preorder in terms of ≲ is easy to write: magenta ≲ green ≲ red ≲ blue ≲ yellow as well cyan ≲ blue and blue ≲ cyan. Now cyan and blue are considered equivalent.

We can define a strict order based on that very easily: If a < b is false, then a must be greater than b equivalent to b. In other words a < b is false if b ≲ a, and true otherwise. This is the complement of the total preorder.

In this case we get the following strict order: magenta < green < red < blue/cyan < yellow and neither cyan < blue nor blue < cyan. This is a strict partial order as it is irreflexive and transitive, but it is not a strict total order as we don’t have trichotomy but only a weaker version of it: Either a < b or b < a or a and b are equivalent.

Such an ordering relation is called a strict weak order. It is a binary relation that is irreflexive, transitive and where incomparability is transitive. What the last property means is this: If a and b are incomparable (i.e. neither a < b nor b < a) and b and c are incomparable, then a and c are incomparable.

And this property is precisely what allows us to define an equivalence relation ~, where a ~ b if a and b are incomparable. Let’s check the required properties:

• It is reflexive as a < a is always false because < is irreflexive.
• It is symmetric because a < b and b < a must both be false, so you can easily swap the roles of a and b.
• It is transitive by requirement.

This has an interesting mathematical consequence: A strict weak order over a set A defines a strict total order over a set called A/~. In this set, the set of equivalence classes, we’ve grouped all elements together that are equivalent (according to ~). No two elements of A/~ are equivalent, so the strict weak order on this set is a strict total order.

Disclaimer: I’m simplifying the notation a bit here.

So for our colors, C/~ based on my cyan is blue equivalence would be {yellow, red, green, blue, magenta} (because cyan is blue). And on this set we have a total order because either a < b or b < a or a = b (which really means equivalent, but we’ve cheated by modifying the set).

And now we can understand the cppreference quote from the introduction: The comparison predicate must “induce a strict total ordering on the equivalence classes”. We simply must have a comparison predicate that can be used to define an equivalence relation where equivalent elements must have a total order. In other words: the comparison predicate must be a strict weak order.

To summarize, for a strict weak order, two elements can either be:

• less than (i.e. a < b)
• greater than (i.e. b < a)
• equivalent (i.e. neither a < b nor b < a)

Summary

Okay, this was a lot of terminology. So here’s a graph that summarizes the ordering relations and how you can transform one into the other:

And this table tells you what you actually want: Given two elements a and b and some ordering relations, is a less than b, greater than, equivalent/equal or incomparable? For brevity, greater than is left out (just swap a and b) and equivalent and equal are merged. But you know that a partial order, total order and strict total order define true equality.

Note that a strict partial order is pretty useless because we can never know whether two elements are equal or just incomparable. And we can simplify the ordering relations even further based on two dimensions:

• Is the order partial or total (i.e. are the incomparable elements)?
• Does the order define equality or equivalence?

Again, a strict partial order is useless, so I’ve left it out.

Why are there two options in the total column?

It is just the question between a < and a ≤ relation, both are equally good. And a quick spoiler from the future part about sorting and searching: In order to, e.g. quick sort, a sequence you need a total order, but equivalence is good enough. So you can either pass it a total preorder, or a strict weak order, depending on your taste. The C++ standard library decided to base everything around a total, equivalency <, i.e. a strict weak order. But it could have just used a total preorder as well. Then the default would not be std::less but std::less_equal.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.