6.4 Ordering relations
The prototype for ordering relations is \(\leq\). Although a case could be made for using \(<\) as the prototypical ordering relation. These two relations differ in one important sense: \(\leq\) is reflexive and \(<\) is irreflexive. Various authors, having made different choices as to which of these is the more prototypical, have defined ordering relations in slightly different ways. The majority view seems to be that an ordering relation is reflexive (which means that ordering relations are modeled after \(\leq\)). We would really like to take the contrary position — we always root for the underdog — but one of our favourite ordering relation (divisibility) is reflexive and it would be eliminated if we made the other choice51. So…
Definition 6.7 A relation \(\mathsf{R}\) on a set \(S\) is an ordering relation iff \(\mathsf{R}\) is reflexive, anti-symmetric and transitive.
Now, we’ve used \(\leq\) to decide what properties an ordering relation should have, but we should point out that most ordering relations don’t do nearly as good a job as \(\leq\) does. The \(\leq\) relation imposes what is known as a total order on the sets that it acts on (you should note that it can’t be used to compare complex numbers, but it can be placed between reals or any of the sets of numbers that are contained in \({\mathbb R}\).) Most ordering relations only create what is known as a partial order on the sets they act on. In a total ordering (a.k.a. a linear ordering), every pair of elements can be compared and we can use the ordering relation to decide which order they go in. In a partial ordering, there may be elements that are incomparable.
Definition 6.8 If \(x\) and \(y\) are elements of a set \(S\) and \(\mathsf{R}\) is an ordering relation on \(S,\) then we say \(x\) and \(y\) are comparable if \(x\mathsf{R}y \; \lor \; y\mathsf{R}x\).
Definition 6.9 If \(x\) and \(y\) are elements of a set \(S\) and \(\mathsf{R}\) is an ordering relation on \(S,\) then we say \(x\) and \(y\) are incomparable if neither \(x\mathsf{R}y\) nor \(y\mathsf{R}x\) is true.
Consider the set \(S = \{1, 2, 3, 4, 6, 12 \}\). If we look at the relation \(\leq\) on this set, we get what is shown in Figure 6.15.
Figure 6.15: An illustration of the less-than-or-equal-to relation.
On the other hand, perhaps you noticed these numbers are the divisors of \(12\). The divisibility relation will give us our first example of a partial order as illustrated in Figure 6.16.
Figure 6.16: An illustration of the divisibility relation.
Exercise 6.7 Which elements in the above partial order are incomparable?
A set together with an ordering relation creates a mathematical structure known as a partially ordered set. Since that is a bit of a mouthful, the abbreviated form poset is actually heard more commonly. If one wishes to refer to a poset, it is necessary to identify both the set and the ordering relation. Thus, if \(S\) is a set and \(\mathsf{R}\) is an ordering relation, we write \((S, \mathsf{R})\) to denote the corresponding poset.
The digraphs given above for two posets having the same underlying set provide an existence proof — the same set may have different orders imposed upon it. They also highlight another issue — these digraphs for ordering relations get pretty crowded Hasse diagrams for posets (named after the famous German mathematician Helmut Hasse) are a way of displaying all the information in a poset’s digraph, but much more succinctly. There are features of a Hasse diagram that correspond to each of the properties that an ordering relation must have.
Since ordering relations are always reflexive, there will always be loops at every vertex in the digraph. In a Hasse diagram we leave out the loops.
Since ordering relations are anti-symmetric, every edge in the digraph will go in one direction or the other. In a Hasse diagram we arrange the vertices so that that direction is upward — that way we can leave out all the arrowheads without losing any information.
The final simplification that we make in creating a Hasse diagram for a poset has to do with the transitivity property — we leave out any connections that could be deduced because of transitivity.
Hasse diagrams for the two orderings that we’ve been discussing are shown in Figure 6.17
Figure 6.17: Hasse diagrams of the set \(\{1,2,3,4,6,12\}\) totally ordered by \(\leq\) and partially ordered by \(\mid\).
Often there is some feature of the elements of the set being ordered that allows us to arrange a Hasse diagram in “ranks.” For example, consider \({\mathcal P}(\{1,2,3\})\), the set of all subsets of a three element set — this set can be partially ordered using the \(\subseteq\) relation. (Technically, we should verify that this relation is reflexive, anti-symmetric and transitive before proceeding, but by now you know why subset containment is denoted using a rounded version of \(\leq\).) Subsets of the same size can’t possibly be included one in the other unless they happen to be equal! This allows us to draw the Hasse diagram for this set with the nodes arranged in four rows. (See Figure 6.18.)
Figure 6.18: Hasse diagram for the power set of \(\{1,2,3\}\) partially ordered by set containment.
Exercise 6.8 Try drawing a Hasse diagram for the partially ordered set \[ ({\mathcal P}(\{1,2,3,4\}),\subseteq). \]
Posets like \(({\mathcal P}(\{1,2,3\}), \subseteq)\) that can be laid out in ranks are known as graded posets. Things in a graded poset that have the same rank are always incomparable.
Definition 6.10 A graded poset is a triple \((S, \mathsf{R}, \rho)\), where \(S\) is a set, \(\mathsf{R}\) is an ordering relation, and \(\rho\) is a function from \(S\) to \({\mathbb Z}\).
In the example we’ve been considering (the graded poset of subsets of a set partially ordered by set inclusion), the grading function \(\rho\) takes a subset to its size. That is, \(\rho(A) = |A|\). Another nice example of a graded poset is the set of divisors of some number partially ordered by the divisibility relation \(\mid\). In this case, the grading function takes a number to its total degree — the sum of all the exponents appearing in its prime factorization. Figure 6.19 shows the poset of divisors of 72 and the grading.
Figure 6.19: Hasse diagram for the divisors of 72, partially ordered by divisibility. This is a graded poset.
We will end this section by giving a small collection of terminology relevant to partially ordered sets.
A chain in a poset is a subset of the elements, all of which are comparable. If you restrict your attention to a chain within a poset, you will be looking at a total order. An antichain in a poset is a subset of the elements, none of which are comparable. Thus, for example, a subset of elements having the same rank (in a graded poset) is an antichain.
Chains and antichains are said to be maximal if it is not possible to add further elements to them (whilst maintaining the properties that make them chains and/or antichains). An element \(x\), that appears above another element \(y\) — and connected to it — in a Hasse diagram is said to cover it. In this situation you may also say that \(x\) is an immediate successor of \(y\).
A maximal element is an element that is not covered by any other element. Similarly, a minimal element is an element that is not a cover of any other element. If a chain is maximal, it follows that it must contain both a maximal and a minimal element (with respect to the surrounding poset). The collection of all maximal elements forms an antichain, as does (separately) the collection of all minimal elements.
Finally, we have the notions of greatest element (a.k.a. top) and least element (a.k.a. bottom) — the greatest element is greater than every other element in the poset, the least element is smaller than every other element. Please be careful to distinguish these concepts from maximal and minimal elements — a greatest element is automatically maximal, and a least element is always minimal, but it is possible to have a poset with no greatest element that nevertheless has one or more maximal elements, and it is possible to have a poset with no least element that has one or more minimal elements.
In the poset of divisors of 72, the subset \(\{2, 6, 12, 24\}\) is a chain. Since it would be possible to add both 1 and 72 to this chain and still have a chain, this chain is not maximal. (But, of course, \(\{1, 2, 6, 12, 24, 72\}\) is.) On the other hand, \(\{8, 12, 18\}\) is an antichain (indeed, this is a maximal antichain). This poset has both a top and a bottom — 1 is the least element and 72 is the greatest element. Notice that the elements which cover 1 (the least element) are the prime divisors of 72.
6.4.1 Exercises
In population ecology, there is a partial order “predates” which basically means that one organism feeds upon another. Strictly speaking, this relation is not transitive; however, if we take the point of view that when a wolf eats a sheep, it is also eating some of the grass that the sheep has fed upon, we see that in a certain sense it is transitive. A chain in this partial order is called a “food chain” and so-called apex predators are said to “sit atop the food chain”. Thus, “apex predator” is a term for a maximal element in this poset. When poisons such as mercury and PCBs are introduced into an ecosystem, they tend to collect disproportionately in the apex predators — which is why pregnant women and young children should not eat shark or tuna but sardines are fine.
Figure 6.20 shows a small example of an ecology partially ordered by “predates”.
Figure 6.20: An illustration of the “predates” partial order.
Find the largest antichain in this poset.
Referring to the poset given in exercise 1, match the following.
- An (non-maximal) antichain
- A maximal antichain
- A maximal element
- A (non-maximal) chain
- A maximal chain
- A cover for “Worms”
- A least element
- A minimal element
- Grass
- Goose
- Fox
- \(\{ \mbox{Grass}, \mbox{Duck} \}\)
- There isn’t one!
- \(\{ \mbox{Fox}, \mbox{Alligator}, \mbox{Cow} \}\)
- \(\{ \mbox{Cow}, \mbox{Duck}, \mbox{Goose} \}\)
- \(\{ \mbox{Worms}, \mbox{Robin}, \mbox{Fox} \}\)
The graph of the edges of a cube is one in an infinite sequence of graphs. These graphs are defined recursively by “Make two copies of the previous graph then join corresponding nodes in the two copies with edges.” The 0-dimensional “cube” is just a single point. The 1-dimensional cube is a single edge with a node at either end. The 2-dimensional cube is actually a square and the 3-dimensional cube is what we usually mean when we say “cube.” These cubes are illustrated in Figure 6.21.
Figure 6.21: Cubes of dimension 0 to dimension 3.
Make a careful drawing of a hypercube — which is the name of the graph that follows the ordinary cube in this sequence.
Label the nodes of a hypercube with the divisors of 210 in order to produce a Hasse diagram of the poset determined by the divisibility relation.
Label the nodes of a hypercube with the subsets of \(\{a,b,c,d\}\) in order to produce a Hasse diagram of the poset determined by the subset containment relation.
Complete a Hasse diagram for the poset of divisors of 11025 (partially ordered by divisibility).
Find a collection of sets so that, when they are partially ordered by \(\subseteq\), we obtain the same Hasse diagram as in the previous problem.
If you insist on making the other choice, you will have a “strict ordering relation” a.k.a. an “irreflexive ordering relation”↩