# 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:
- \(|a|<|b|\)
- \(a=-b\) and \(a<0\)
- \(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.

- Let \(\preceq\) be an relation on the integers where \(a\preceq b\) when any of:
- 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:
- \(a_1\ne b_1\) and \(a_1\preceq_1 b_1\).
- \(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.