Session arrangement

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

Motivation

Arrangement is a common concept that we work with in everyday life. We can arrange many things in some way - words by alphabet, students at school by height, goods by price. These are all described by an ordering relation, which we usually denote by the symbol ≤. The related symbols are: <, >, ≥. Their meaning is obvious.

What would we expect from such a session? It is already clear from the symbol that there will be elements in the ordering session that are equal - so our point is to define the properties of the session to be less than or equal to. Such a session should thus be reflexive. It must be true that a ≤ a.

What next? Surely symmetry will not hold - if we have an ordering by price, then if a car is cheaper than bread, surely bread will not also be cheaper than a car. What would we generally expect if it happened that a ≤ b and at the same time b ≤ a? Would that ever make sense? Yes, if a = b held true . The only case where the order of the elements embedded in the session doesn't matter is when the elements are the same - the ordering is thus antisymmetric.

After all, if we know that a car is more expensive than bread and an airplane is even more expensive than a car, we expect that the airplane will certainly be more expensive than the bread. This is what transitivity describes.

Partial ordering

What we have just defined is in fact only a partial ordering, it is not complete. Why is it not complete? Let's try to define ordering on sets. In what way could we compare two sets?

We say that the set A is less than or equal to the set B, if A ⊆ B, that is, if A is a subset of B. This makes sense, because if we have A = {1, 2} and B = {1, 2, 3}, then we could say that A is smaller - B contains the same elements as A, and it also contains the number three. So, for example, the following would apply:

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

But the trouble is, if we want to compare these sets: A = {a, b} and B = {a, c}. Which one is smaller or larger? The trouble is that although both sets contain the element a, the second element is always different. Neither set is a subset of the other, so neither A ≤ B nor B ≤ A applies. Such sets are incomparable using our ordering.

Therefore, we define a completely ordered set or also a string if every two elements of the set are comparable. For example, numerical sets with classical ordering are such sets. For every two real numbers a, b you are able to decide whether a ≤ b or b ≤ a.

Examples from life

An example where it pays not to compare might be an ordering by beauty, so the session < would mean "be uglier". Maybe we should define it the other way around > as "being prettier" to be more correct :-). It probably makes sense to compare two women to each other, for example "Helenka Vondráčková" < "Agáta Hanychová" in the sense of Agáta is prettier than Helenka. Or two men: "Jirka Paroubek" < "Vojta Kotek" in the sense Kotek is prettier than Paroubek.

The problem is that we can hardly compare the beauty of a man and a woman. Is Agata or Vojta prettier? Is our national treasure, Helen, or the sexy brain Jirka uglier? I'd rather not investigate...

If we limit ourselves to women in the last example, we can say that we have a completely ordered set, because we can compare the beauty of all women.

The minimum and maximum element, the smallest and largest element

If we have an ordered set M, then we call the element min ∈ M the minimal element if there is no x ∈ M such that x < m. Thus we are unable to find an element that is smaller than the element min.

We call an element max ∈ M maximal if there is no x ∈ M such that x > max. That is, we are unable to find an element that is greater.

The previous two notions are different from the notions of smallest and largest.

We call an element a ∈ M the smallest if for all x ∈ M it is true that a ≤ x. That is, the smallest element a is less than or equal to all other elements in the set M.

We call an element b ∈ M the largest if for all x ∈ M it holds that b ≥ x. The largest element b is greater than or equal to all other elements in the set M.

What is the difference between the largest element and the maximum element? There can be more than one maximal element because the set is not necessarily completely ordered. Going back to the example of comparing people based on appearance, we can say that Carmen Electra is the prettiest woman and Johnny Depp is the prettiest man. But we are no longer able to compare these two people to each other, we don't know if Carmen Electra or Johnny Depp is prettier.

So both elements are maximum. We are not able to find a person who is more handsome than Johnny Depp - Johnny is more handsome than all other men and we cannot compare him with women. Similarly for Carmen Electra - she is prettier than all women and we cannot compare her with men.

But neither is the greatest, in that sense, the prettiest. Because for Johnny Depp to be the prettiest/biggest, he would have to be prettier than all people, including all women. But we've already established that we can't compare him to women, so he can't be the most beautiful person, he's just, in the terminology of order theory, the maximum.

It is probably easy to see that if a set has a greatest element, then that element is also a maximum. If the element a is greater than all the other elements of the set (the definition of the largest element), then surely we cannot find an element that is even greater (the definition of the maximal element).

An example of a set that has a largest and a smallest element is the closed interval <0, 1>. If we choose the same interval but open, it would have neither the largest nor the smallest element: (0, 1).

If we wanted infinitely many minimal elements, we could define the ordering of R as follows. First, we define the auxiliary sets M_x. The sets will take the following form: for all x of the interval (0, 1), we define the set M_x = {y | y = x + n}, where n is a non-negative integer. This gives us sets such as the following:

$$\begin{eqnarray} M_{0{,}5}&=&\left\{0{,}5;, 1{,}5;, 2{,}5;, 3{,}5; \ldots\right\}\\ M_{0{,}7}&=&\left\{0{,}7;, 1{,}7;, 2{,}7;, 3{,}7; \ldots\right\}\\ M_{0{,}8}&=&\left\{0{,}8;, 1{,}8;, 2{,}8;, 3{,}8; \ldots\right\} \end{eqnarray}$$

On each set M_x we define a classical ordering, which we denote by R_x. At the end, we just unify these arrangements: R = ∪ R_x. Thus, in this arrangement we can always compare only within the original strings. Thus we can find out if 0,5 ≤ 2,5, but we can no longer find out if 0,5 ≤ 2,7 because these numbers were not in the same M_x set and so we do not have their relationship defined.

In this ordering relation, then, every element in the interval (0, 1) is a minimal element.

Hasse diagrams

We can plot ordered sets using a Hasse diagram. This is a graph in which the vertices represent elements of the set, and the edge between the vertices of (a, b) tells us that a < b while there is no c such that a < c < b. Thus, there is no more element between the elements of a and b. In doing so, it must be true that in the graph the vertex a is lower than the vertex b. Example of a Hasse diagram:

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

Although Hasse diagrams are usually plotted in this nicely aligned way, it is not strictly necessary. The preceding Hasse diagram may look like this:

Another example might be a set: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. They are natural divisors of a number 60. The ordering by divisibility can be shown like this:

Ordering by divisibility means that [a, b] ∈ R just when a divides b. From the diagram we can notice that each number has numbers above it that 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. Etc. Conversely, the number 3 does not have the number 10 above it because it does not divide it - note that the number 10 is visually above the number 3, but there is no line leading to it "from the bottom up". If we only go up from 3, we can go to 15 and 6, and from them to 30. We would only get to 10 by going down, which we must not do.