Partial Orderings

• Equality relations are a nice collection of properties that a relation can have.
• … and they led to some nice generalizations/theorems.
• We can do this again with another collection of properties and get something interesting.
• A relation $$R$$ on a set $$S$$ is a partial ordering if is reflexive, antisymmetric, and transitive.
• Remember: antisymmetric means that if $$(a,b),(b,a)\in R$$ then $$a=b$$.
• A partial order on a set is often written $$(S,R)$$ and called a partially ordered set or poset.
• For example, $$(\mathbf{Z},\le)$$ is a poset.
• Reflexive: $$a\le a$$.
• Antisymmetric: if $$a\le b$$ and $$b\le a$$ then $$a=b$$.
• Transitive: if $$a\le b$$ and $$b\le c$$, then $$a\le c$$.
• More examples:
• $$(\mathbf{Z},\ge)$$, by reasoning just like the above.
• Divisibility: $$(\mathbf{Z}^{+},\mid)$$.
• Reflexive: $$a\mid a$$.
• Antisymmetric: if $$a\mid b$$ and $$b\mid a$$ then $$a=kb$$ and $$b=ma$$, so $$a=(km)b$$. Since $$k$$ and $$m$$ are integers, they must both be 1. Thus $$a=b$$.
• Transitive: if $$a\mid b$$ and $$b\mid c$$, then $$a\mid c$$. [Details with the constants earlier in notes.]
• Containment of sets. For a set of sets $$S$$: $$(S,\subseteq)$$. With $$A,B,C\in S$$ we have:
• Reflexive: $$A\subseteq A$$.
• Antisymmetric: if $$A\subseteq B$$ and $$B\subseteq A$$ then $$A=B$$.
• Transitive: if $$A\subseteq B$$ and $$B\subseteq C$$ then $$A\subseteq C$$.
• Informally, when we put these three properties together, we kind of get things put in an order.
• Being both antisymmetric and transitive feels like an ordering: can't be both greater and less; order has to increase in a kind-of-logical way.
• It's always going to be an “or equal to” relationship, since it has to be symmetric.
• We'll use the symbol $$(S,\preceq)$$ for a generic poset relation.
• It's like a less-than-or-equal, but a little more curvy. Sometimes pronounced “precedes or equal” (precede = 优于)
• Using $$\le$$ or $$\subseteq$$ or something else we already use for a specific poset would just cause confusion. We'd probably apply theorems specific specific to numbers/sets just because they looked right.
• The symbol can be used to indicate a relation in the obvious way: $$a\preceq b$$ if $$(a,b)$$ is in the set defining the relation.
• We can also write $$a\prec b$$ to indicate $$a\preceq b$$ and $$a\ne b$$.
• But notice that we haven't demanded that everything be compared.
• For sets under $$\subseteq$$ we have neither $$\{1\}\subseteq\{2\}$$ nor $$\{2\}\subseteq\{1\}$$.
• Everything can be compared under $$(\mathbf{Z},\le)$$. It is always the case that either $$a\le b$$ or $$b\le a$$.
• For a poset $$(S,\preceq)$$, we will say that $$a,b\in S$$ are comparable if either $$a\preceq b$$ or $$b \preceq a$$ (or both if $$a=b$$).
• So, every pair of integers are comparable under $$(\mathbf{Z},\le)$$.
• Under $$(\mathbf{Z}^{+},\mid)$$, 4 and 12 are comparable (since $$4\mid 12$$), but 4 and 13 are not.
• Another example we just saw: the set of partitions ordered by refinement.
• We don't have any nice notation for that, so we can use $$\preceq$$, and write $$P_1\preceq P_2$$ if $$P_1$$ refines $$P_2$$.
• This is reflexive: a relation refines itself since we didn't demand proper subsets in the definition.
• It is antisymmetric: if $$P_1\preceq P_2$$, then either $$P_1= P_2$$ or there is some set in $$P_1$$ that is a proper subset of one in $$P_2$$ and then $$P_2\not\preceq P_1$$.
• It's transitive: if $$P_1\preceq P_2$$ and $$P_2\preceq P_3$$ then all sets in $$P_2$$ are subsets of the sets in $$P_3$$, and sets in $$P_1$$ are subsets of sets in $$P_2$$. So, $$P_1\preceq P_3$$.
• We saw that not every partition is comparable, so there can be partitions where $$P_1\not\preceq P_2$$ and $$P_2\not\preceq P_1$$.
• For a poset $$(S,\preceq)$$, we will say that $$a$$ is a least element of $$A\subseteq S$$ if for all $$b\in A$$, we have $$a\preceq b$$.
• Similarly, a greatest element is one where for all $$b\in A$$, we have $$b\preceq a$$.
• For example,
• For $$(S,\subseteq)$$, the least element if $$\emptyset$$ and the greatest element is $$S$$.
• For $$(\mathbf{Z},\le)$$, there is no least or greatest element.
• For $$(\mathbf{Z}^{+},\le)$$, the least element is 1, and there is no greatest element.
• Theorem: A subset $$A$$ of poset $$(S,\preceq)$$ cannot have more than one least element (or greatest).

Proof: Suppose there are two least elements $$a,b\in A$$ with $$a\ne b$$. From the definition of least element, we have $$a\preceq b$$ and $$b\preceq a$$. Since $$\preceq$$ must be an antisymmetric relation, that implies $$a=b$$.

This is a contradiction, so there cannot be multiple least elements. (The logic is identical for greatest elements.)

Hasse Diagrams

• Suppose we try to draw the digraph for a poset.
• It had better be small. Let's do $$(P(\{1,2,3\}),\subseteq)$$:
• That's ugly.
• … but also unnecessarily complicated.
• If we know we're drawing a partial order, we don't need the loops, since the relation must be transitive.
• We can also get rid of the “extra” edges since it must be transitive.
• If we do:
• Much better.
• If we take the reflexive and transitive closures of this relation, we'll get the original back.
• If we make the rule that “smaller” items always have to be below “larger” ones, then we don't need the arrow heads either:
• Much better.
• This is a Hasse diagram for the poset.

Total and Well Orderings

• If every two elements in $$S$$ are comparable under $$(S,\preceq)$$, it is called totally ordered.
• … and $$\preceq$$ is a total ordering.
• $$(\mathbf{Z},\le)$$ is totally ordered.
• $$(S,\subseteq)$$ and $$(\mathbf{Z}^{+},\mid)$$ are not.
• But, $$(\{3^k\mid k\in\mathbf{Z}^{+}\},\mid)$$ is a total ordering.
• Refinement of partitions/relations is not total.
• If we construct the Hasse diagram for a subset of the integers under $$\le$$, we get:
• Because every pair of elements is comparable (the relation is a total order), the diagram is just a line.
• That will be true of any total order: they have boring Hasse diagrams.
• If $$(S,\preceq)$$ is a totally ordered set, then we will call it well ordered if every non-empty subset of $$S$$ has a least element.
• $$(\mathbf{Z}^{+}, \le)$$ is a well ordering.
• $$(\{3^k\mid k\in\mathbf{Z}^{+}\},\mid)$$ is a well ordering. The least element is the smallest $$3^k$$ in the subset.
• If we look at $$(\mathbf{Z}, \le)$$:
• The subset $$\{4,5,6,\ldots\}\subseteq\mathbf{Z}$$ has a least element (it's 4).
• But the subset $$\{-4,-5,-6,\ldots\}\subseteq\mathbf{Z}$$ does not.
• So, $$(\mathbf{Z}, \le)$$ is a total ordering, but not a well ordering.
• So, the set we're looking at affects whether it's a well order or not.
• $$(\mathbf{Z}^{+}, \le)$$ is.
• $$(\mathbf{Z}, \le)$$ isn't.
• So does the operation. Let's define a different ordering relation on $$\mathbf{Z}$$…
• We can make $$\mathbf{Z}$$ well ordered if we define an appropriate relation. For example…
• Let $$\preceq$$ be an relation on the integers where $$a\preceq b$$ when any of:
1. $$|a|<|b|$$
2. $$a=-b$$ and $$a<0$$
3. $$a=b$$
• Or in words: “smaller” means “closer to zero, but negative numbers win if there's a tie”.
• If we want something to be a well order, we have a lot to show…
• Reflexive: we said $$a\preceq b$$ when $$a=b$$.
• Antisymmetric: We have to check each case of $$a\preceq b$$. For $$a\ne b$$…
• If $$|a|<|b|$$ then definitely $$|b|\not <|a|$$, $$a\ne -b$$, and $$a\ne b$$. Thus, $$a\not\preceq b$$.
• If $$a=-b$$ and $$a<0$$, then $$b=-a$$, but $$b\not <0$$. (And $$a\ne b$$ and $$|a|\not <|b|$$.)
• If $$a=b$$ then we don't care about this case for antisymmetry.
• Transitive: We have nine ways to get both $$a\preceq b$$ and $$b\preceq c$$.
• Left as an exercise for you. [That's a fancy way to say “I don't feel like typing them all out.”]
• We now have $$(\mathbf{Z},\preceq)$$ is a partial order.
• If we have any $$a,b\in\mathbf{Z}$$, are they comparable?
• If $$|a|\ne|b|$$ then $$|a|<|b|$$ or $$|b|<|a|$$. In either case, yes.
• If $$|a|=|b|$$ then either $$a=b$$ or $$a=-b$$. In both cases, yes.
• $$(\mathbf{Z},\preceq)$$ is a total ordering.
• Does any subset of $$\mathbf{Z}$$ have a least element?
• Yes: it is the element with the smallest absolute value.
• (We know such a thing exists, because $$(\mathbf{Z}^{+}, \le)$$ is a well order.)
• If there are two such elements, then the negative one is the actual least element.
• $$(\mathbf{Z},\preceq)$$ is a well ordering.
• Can every set be well ordered by some relation, if we're clever enough with the definition?
• A surprisingly hard question to answer.
• After some deep set theory, the answer is “it depends”.
• Theorem: Any finite total ordering is also a well ordering.

Proof: We can do better than proving it exists, we can actually find it:

procedure find_a_least_element(S, ≤):
repeat |S|-1 times:
pick two elements a,b at random from S
if a ≤ b
remove b from S
else
remove a from S
return the remaining element from S

At the end of this algorithm, the returned element is $$\le$$ every element that has been removed, so it is the least element.

• If we have a well ordered set, we can do induction on it.
• Well-ordered induction.
• Proofs look like this to show that every element in $$(S,\preceq)$$ has the property $$P$$:
• Call the least element $$a$$.
• Base case: Show that $$P(a)$$ is true.
• Inductive case: For any $$y\in S$$, assume for induction that if $$x\prec y$$ then $$P(x)$$. Use that to show $$P(y)$$.
• Conclude that $$P(x)$$ for all $$x\in S$$.
• We can actually leave out the base case: if we can show if smaller elements have $$P$$ implies $$P(x)$$ is true, then it must be true for $$a$$ since there are no smaller elements. ($$T\rightarrow p \equiv p$$)
• … unless the inductive step relies on some smaller element existing.
• It turns out that the induction we have been doing was just a special case because $$(\mathbf{Z}^{+}, \le)$$ is a well ordering.

Lexicographic Order

• If we have two partial orderings, $$(A_1,\preceq_1)$$ and $$(A_2,\preceq_2)$$, then we can order $$A_1\times A_2$$ by saying that $$(a_1,a_2)\preceq(b_1,b_2)$$ when:
1. $$a_1\ne b_1$$ and $$a_1\preceq_1 b_1$$.
2. $$a_1 = b_1$$ and $$a_2\preceq_2 b_2$$.
• This is the lexicographic ordering of $$A_1\times A_2$$.
• We mentioned lexicographic ordering earlier when talking about ordering permutations. It's back.
• We can extend in the obvious way if we have more than two sets: look at pairs of elements left-to-right until you find two that are different; the order of the tuple is the order of that pair.
• Lexicographic ordering is basically dictionary order.
• Actually, “lexicographic ordering” is just a fancy way to say “dictionary ordering”: lexicography is the study/creation of dictionaries.
• But if we called it “dictionary ordering”, it wouldn't seem as difficult and we wouldn't feel as smart for understanding it.
• For example, with the integers under the usual less-than order,
• $$(1,8)\prec (3,5)$$ since $$1<3$$.
• $$(3,4)\prec (3,5)$$ since $$4< 5$$.
• $$(1,2,3,4,12,6)\prec(1,2,3,4,19,1)$$ since $$12<19$$.
• So, we can use lexicographic ordering to sensibly order elements of $$\mathbf{Z}^n$$ or $$\mathbf{R}^n$$.
• Another example: decimal expansions of the real numbers in $$[0,1]$$.
• If you look at two decimal expansions, you know how to order them: 0.123456 < 0.123490.
• Think of that as $$(1,2,3,4,5,6)<(1,2,3,4,9,0)$$ and it looks like lexicographic ordering.
• What you have always been doing is applying a lexicographic order based in the ordering of the digits.
• … with the special rule that a missing digit is actually a zero: 0.123 < 0.1234.
• That means that we'd compare $$0.4999\overline{9}<0.5000\overline{0}$$, which isn't actually right.
• We can also use lexicographic ordering on pairs of different types (which is why $$\preceq_1$$ and $$\preceq_2$$ were different in the definition).
• For example, pairs of integers and words: $$(4,\text{one})\prec (6,\text{apple})$$ and $$(4,\text{one})\succ (4,\text{apple})$$
• Theorem: If $$(A_1,\preceq_1)$$ and $$(A_2,\preceq_2)$$ are both partial orderings, then lexicographic ordering on $$A_1\times A_2$$ is actually a partial order.

• Proof left as an exercise (because again, dealing with all the cases is a pain, but not difficult). We need to show that the relation is reflexive, antisymmetric, and transitive for each case of the definition of the relation.

Maximal and Minimal Elements

• We'll define minimal and maximal elements for a poset $$(S,\preceq)$$ as…
• $$a\in S$$ is a maximal element if there is no $$b\in S$$ with $$a\prec b$$.
• Similarly, $$a\in S$$ is a minimal element if there is no $$b\in S$$ with $$b\prec a$$.
• Notice that we're not demanding a total or well ordering here: any partial ordering will do.
• Note that “minimal” elements and “least” from before aren't the same.
• Least: for all $$b\ne a$$, $$a\prec b$$.
• Minimal: for all $$b\ne a$$, $$b\not\prec a$$.
• We can see the difference for some non-total ordering like $$(\{\{1\},\{2\},\{1,2\}\},\subseteq)$$.
• There is no least element.
• There are two minimal elements: $$\{1\},\{2\}$$.
• Least elements are the unique smallest thing; minimal elements are ones where nothing is smaller.
• Another example: $$(\{4,5,12,14,15,30,300\}, \mid)$$.
• The minimal elements are the ones that nothing else divides: $$\{4,5,14\}$$
• The maximal elements are the ones that are not divisors of anything else: $$\{14,300\}$$
• Notice: 14 is both minimal and maximal; 12 is neither.
• Another example: $$(\mathbf{Z},\le)$$ has no minimal or maximal elements.
• Theorem: Every finite poset $$(S,\preceq)$$ has a minimal element.

Proof: The proof here is essentially the same as the proof that finite total ordering are also also a well orderings. We prove that a minimal element exists by finding it.

Let $$a_1$$ be an element of $$S$$. If $$a_1$$ is minimal, then we have found a minimal element. If not, then there is an $$a_2\in S-\{a_1\}$$ such that $$a_2\prec a_1$$. We repeat this procedure if $$a_2$$ is not minimal and find $$a_3\in S-\{a_1,a_2\}$$.

By repeating this procedure, we find a minimal element in at most $$|S|-1$$ steps. Thus one exists.

• This theorem implies that we could always extend a partial order to a total order if we needed to.
• This is called topological sorting.
• The algorithm is basically: find a minimal element and declare it the least element; repeat.
procedure topological_sort(S, ⪯)
ordered = []
until S is empty:
a = a minimal element from S under ⪯
S = S - {a}
ordered += [a]
return ordered
• We can use topological sorting to come up with an order to perform non-totally-ordered operations.
• For example, calculating values in a spreadsheet.
• Let two cells in the spreadsheet $$c_1$$ and $$c_2$$ be related if calculating the value in $$c_2$$ depends on the value in $$c_1$$.
• e.g. if cell D2 contains the formula C2+A2 then we would have $$(\text{C2},\text{D2}),(\text{A2},\text{D2})\in R$$.
• This is a partial order, if we don't allow circular-dependencies in the calculations.
• Creating a total order by topological sorting gives us an order we can calculate the values in the cells, without ever using out-of-date data.