Section 15.1 Partial orders and their diagrams
In the last chapter we looked at equivalence relations, which generalize the idea of equality. Partial orders will do the same for inequalities. How can we say one object is “less than” another when the two objects are not numbers? You may be able to think of a way to order sets, or strings, or matrices. That way is probably a partial order.
Subsection 15.1.1 Introduction
In this chapter, “less than” means “less than or equal to”, denoted \(\le\text{.}\) If we want to refer to the relation symbolized by \(\lt\text{,}\) we will say “strictly less than”.
The secret ingredient to order is that an order must only go one way. If \(x\) is less than \(y\text{,}\) the only way that \(y\) should be able to be less than \(x\) is if the two are equal. Fortunately, we have a word for this: antisymmetry! Of course, order should be transitive, and the “or equal to” part implies reflexiveness. So, we are ready to define a partial order.
Definition 15.1.1.
A relation is a partial order if it is reflexive, antisymmetric, and transitive. If \(R\) is a partial order on a set \(X\) and \((x,y) \in R\text{,}\) we write \(x \le_R y\text{,}\) \(x \preceq y\text{,}\) or \(x \le y\text{.}\) The third is only used when the partial order is clear from context and there is no mistaking it with the usual order on the integers.
Example 15.1.2.
The prototypical partial order is the relation \(x \le y\) on the integers. This relation is reflexive (any integer is less than or equal to itself), antisymmetric (\(x \le y\) and \(y \le x\) means \(x=y\)), and transitive (as we used extensively when we wrote inductive proofs).
However, this isn't the only partial order on the positive integers. You could also \(m\) is related to \(n\) if and only if \(m|n\text{.}\) It's reflexive (every positive integer divides itself), transitive (if \(k\) divides \(m\) which divides \(n\text{,}\) then \(k|n\)), and antisymmetric (if \(m\) and \(n\) are positive then the only way for \(m|n\) and \(n|m\) is for \(n=m\)).
Example 15.1.3.
Given a family of sets, we can describe a partial order on them by defining \(E\) to be “less than” \(F\) if \(E \subseteq F\text{.}\)
To see why the relation described by \(E \subseteq F\) is a partial order, note that it is reflexive (\(E \subseteq E\)), antisymmetric (we often prove \(E = F\) by proving \(E \subseteq F\) and \(F \subseteq E\)), and transitive (if \(E \subseteq F\) and \(F \subseteq G\) then \(E \subseteq G\)).
Why the word “partial”? Take the example of the order defined by divisibility on the positive integers. Neither \(3|5\) nor \(5|3\text{.}\) Since we have two elements that cannot be ordered, the order is only partial.
Definition 15.1.4.
Suppose that \(R\) is a partial order on a set \(X\text{.}\) If \(x \preceq y\) or \(y \preceq x\) in the partial order, we say \(x\) and \(y\) are comparable; if not, they are incomparable.
Definition 15.1.5.
An order on a set \(X\) is total or linear if \(x\) and \(y\) are comparable for every \(x,y \in X\text{.}\)
Example 15.1.6.
The usual order on the integers is a total order. The divisibility order is total if restricted to the right set, for example, the set of powers of \(2\text{:}\)
Each of these numbers either divides or is divided by each of the others.
Definition 15.1.7.
A set \(X\) is well-ordered if it has a total order \(\preceq\) and an element \(x_0\) such that \(x_0 \preceq x\) for all \(x \in X\text{.}\)
In language we will learn later, a well-ordered set is a set with a total order and a “minimum” element.
Example 15.1.8.
The poster child for well-ordered sets is \(\mathbb{N}\text{,}\) with the usual total order and the least element \(0\text{.}\) Observe that one of the most important features of \(\mathbb{N}\text{,}\) the validity of mathematical induction, is not special to \(\mathbb{N}\) at all: all we need is somewhere to start and a way to move “forward” through the set. So, well-ordered sets are precisely those for which mathematical induction is possible.
Subsection 15.1.2 Partial order diagrams
As relations, partial orders can be represented with directed graphs. Let's give it a try with a simple partial order: the inclusion order on the power set of \(\{a,b,c\}\text{.}\)
The directed graph of the relation where a set \(E\) is related to a set \(F\) if \(E\) is a subset of \(F\text{.}\) The empty set sits at the bottom with \(\{a,b,c\}\) above and the rest of the power set in between. This digraph is a mess, with arrows crossing each other all over.
This visual is, in a word, awful. There are too many arrows! However, the fact that we are dealing with a partial order implies that certain arrows are redundant. Since every partial order is reflexive, we can lose the loops. Transitivity says that the edges from \(\varnothing\) to \(\{a\}\) and from \(\{a\}\) to \(\{a,b\}\) are sufficient; we do not need the edge from \(\varnothing\) to \(\{a,b\}\) (and etc.) Finally if we impose the restriction that all edges flow upward, we can draw the following, much more pleasant, picture.
The first directed graph has been refined by removing the redundant arrows. Now, we only have edges from the empty set up to \(\{a\}\text{,}\) \(\{b\}\text{,}\) and \(\{c\}\text{;}\) from \(\{a\}\) to \(\{a,b\}\) and \(\{a,c\}\text{,}\) from \(\{b\}\) to \(\{a,b\}\) and \(\{b,c\}\text{;}\) from \(\{c\}\) to \(\{a,c\}\) and \(\{b,c\}\text{;}\) and finally from \(\{a,b\}\text{,}\) \(\{b,c\}\text{,}\) and \(\{a,c\}\) to \(\{a,b,c\}\text{.}\)
We will call such a picture, that uses the properties of a partial order to remove redundant edges, a partial order diagram.
Definition 15.1.11.
Suppose \(X\) is partially ordered and \(x,y,z \in X\text{.}\) If \(x \preceq y\) and there is no intermediate element \(z\) such that \(x \preceq z\) and \(y \preceq z\text{,}\) we say \(y\) covers \(x\text{.}\)
Definition 15.1.12.
The partial order diagram of a partial order is a graph on a set \(X\) where there is an edge from a vertex \(x\) up to \(y\) if and only if \(y\) covers \(x\) in the order.
Notice that the definition of a partial order diagram requires the edges to “point up”. There are no edges that go “side-to-side”. If two elements are incomparable, then there is simply no edge between them.
Example 15.1.13.
Let \(X=\{a,b,c,d,e\}\) and
Draw the diagram for this partial order.
To draw a diagram out of a set of pairs, observe that the elements related to the most other elements should be on the bottom of the diagram, while the elements related to the fewest other elements should be near the top. You can typically then “fit in” the others. So, \(d\) should be near the bottom of the diagram (related to \(4\) elements, the most) and \(e\) should be near the top (related to only itself, the fewest).
The partial order diagram has \(d\) at the bottom related to \(c\) above it. The elements \(c\) and \(a\) next to it are both related to \(b\text{,}\) which is related to \(e\) at the top.
Note very carefully that the vertical positioning of the elements is not the only thing that matters. It is not true that \(d \preceq a\text{!}\) What matters most is where the edges are placed.