Order relations

An order relation is a binary relation on a set that is reflexive, antisymmetric and transitive.

Motivation

Ordering is a familiar idea that we use in everyday life. We can arrange plenty of things in some kind of order – words alphabetically, pupils at school by height, goods by price. An order relation describes all of this, and we usually write it with the symbol ≤. Related symbols are <, > and ≥, and their meaning is clear.

What would we expect from such a relation? The symbol already tells us that an element can be related to itself – we are defining the properties of “less than or equal to”. So the relation should be reflexive: a ≤ a must hold.

What else? Symmetry certainly won’t hold. If we order things by price and a car is cheaper than a loaf of bread, then bread can’t also be cheaper than the car. What would we expect if it happened that a ≤ b and at the same time b ≤ a? Would that ever make sense? Yes, if a = b. The only case where the order of the two elements in the relation doesn’t matter is when the elements are the same – so the order is antisymmetric.

Finally, if we know that a car costs more than a loaf of bread and a plane costs even more than the car, we expect the plane to cost more than the bread. This is described by transitivity.

Partial order

What we have just defined is in fact only a partial order – it is not total. Why not? Let’s try to define an order on sets. How could we compare two sets?

We say that a set A is less than or equal to a set B if A ⊆ B, that is, if A is a subset of B. This makes sense, because if A = {1, 2} and B = {1, 2, 3}, we can say A is smaller – B contains the same elements as A and, on top of that, the number three. So, for example, the following hold:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

The trouble comes when we want to compare these sets: A = {a, b} and B = {a, c}. Which of them is smaller or larger? Both sets contain the element a, but their second elements differ. Neither set is a subset of the other, so neither A ≤ B nor B ≤ A holds. With our order, such sets are incomparable.

So we define a totally ordered set, also called a chain, as a set in which any two elements are comparable. Examples are the number sets with the usual order. For any two real numbers a, b you can decide whether a ≤ b or b ≤ a.

Real-life examples

An example where it pays not to compare might be ordering by looks, where the relation < would mean “is less good-looking than”. Perhaps we should define it the other way round, with > meaning “is better-looking than”, to be more polite :-). It probably makes sense to compare two women with each other, for example “Amelia” < “Isla”, meaning Isla is better-looking than Amelia. Or two men: “Oliver” < “Harry”, meaning Harry is better-looking than Oliver.

The problem is that we can hardly compare the looks of a man and a woman. Is Isla or Harry better-looking? Is Amelia or Oliver less good-looking? Better not to investigate…

If in the last example we restrict ourselves to women only, we can say that we have a totally ordered set, because we can compare the looks of all the women.

Minimal and maximal elements, least and greatest elements

Suppose we have an ordered set M. We call an element min ∈ M minimal if there is no x ∈ M such that x < min. In other words, we cannot find an element that is smaller than min.

We call an element max ∈ M maximal if there is no x ∈ M such that x > max. In other words, we cannot find an element that is larger.

These two terms differ from the terms least and greatest.

We call an element a ∈ M the least element if a ≤ x for all x ∈ M. So the least element a is less than or equal to all the other elements of the set M.

We call an element b ∈ M the greatest element if b ≥ x for all x ∈ M. The greatest element b is greater than or equal to all the other elements of the set M.

What is the difference between a greatest element and a maximal element? There can be several maximal elements, because the set doesn’t have to be totally ordered. Going back to the example of comparing people by looks, we can say that Isla is the best-looking woman and Harry is the best-looking man. But we can’t compare these two with each other – we don’t know whether Isla or Harry is better-looking.

Both elements are therefore maximal. We can’t find anyone better-looking than Harry – Harry is better-looking than all the other men, and we can’t compare him with women. Similarly for Isla – she is better-looking than all the other women, and we can’t compare her with men.

But neither of them is the greatest, in this sense the best-looking. To be the best-looking/greatest, Harry would have to be better-looking than everyone, including all the women. But we have already said that we can’t compare him with women, so he cannot be the best-looking person; he is only, in the terminology of order theory, maximal.

It is easy to see that if a set has a greatest element, then this element is also maximal. If an element a is greater than all the other elements of the set (the definition of a greatest element), then we certainly won’t find an element that is greater still (the definition of a maximal element).

An example of a set that has a greatest and a least element is the closed interval [0, 1]. If we take the same interval but open, it has neither a greatest nor a least element: (0, 1).

If we wanted infinitely many minimal elements, we could define an order R as follows. First we define auxiliary sets M_x. For every x in the interval (0, 1) we define the set M_x = {y | y = x + n}, where n is a non-negative integer. This gives us, for example, these sets:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0.5;1.5;2.5;3.5;\dots \}\\ M_{0,7}& =& \{0.7;1.7;2.7;3.7;\dots \}\\ M_{0,8}& =& \{0.8;1.8;2.8;3.8;\dots \}\end{array}$$

On each set M_x we define the usual order, which we denote R_x. Finally, we simply take the union of these orders: R = ∪ R_x. In this order we can only ever compare within the original chains. So we can find out whether 0.5 ≤ 2.5, but we can’t find out whether 0.5 ≤ 2.7, because these numbers were not in the same set M_x and so their relationship is not defined.

In this order relation, every element of the interval (0, 1) is a minimal element.

Hasse diagrams

We can draw ordered sets using a Hasse diagram. It is a graph in which the vertices represent the elements of the set, and an edge between the vertices (a, b) tells us that a < b and that there is no c such that a < c < b. So there is no other element between a and b. In addition, vertex a must be lower in the graph than vertex b. An example of a Hasse diagram:

This Hasse diagram represents the ordered set {A, B, C, D, E, F}. Here A < B and B < E, so of course A < E as well, but there is no edge between these vertices, because there is a vertex B for which A < B < E. The elements E and D are incomparable, because neither is above or below the other.

Although Hasse diagrams are usually drawn neatly aligned like this, it isn’t strictly necessary. The previous Hasse diagram could also look like this:

Another example is the set A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. These are the positive factors of 60. The order by divisibility can be shown like this:

Ordering by divisibility means that (a, b) ∈ R if and only if a divides b. From the diagram we can see that every number has above it the numbers it divides. For example, above the number 6 are the numbers 12, 30 and 60. Above the number 4 are the numbers 12, 20 and 60, and so on. On the other hand, the number 3 does not have the number 10 above it, because 3 does not divide 10 – watch out: the number 10 is visually above the number 3, but no line leads to it from the bottom upwards. If we move only upwards from the number 3, we can go to the numbers 15 and 6 and from them to the number 30. We could reach the number 10 only by going back down, which we are not allowed to do.