• … and they led to some nice generalizations/theorems.
• We can do this again with another collection of properties and get something interesting.

• 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.

• 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\).

• \((\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\).

• 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.

• We can also write \(a\prec b\) to indicate \(a\preceq b\) and \(a\ne b\).

• 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\).

• 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.

• 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\).

• Similarly, a greatest element is one where for all \(b\in A\), we have \(b\preceq a\).

• 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.)∎

• 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.

• … 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.

• 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.

• \((\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.

• 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.

• \((\mathbf{Z}^{+}, \le)\) is.
• \((\mathbf{Z}, \le)\) isn't.

• 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.

• 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.∎

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\).

• 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.

• \((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\).

• 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.

• 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.

• \(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.

• Least: for all \(b\ne a\), \(a\prec b\).
• Minimal: for all \(b\ne a\), \(b\not\prec a\).

• 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.

• 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.

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 is called topological sorting.

procedure topological_sort(S, ⪯)
    ordered = []
    until S is empty:
        a = a minimal element from S under ⪯
        S = S - {a}
        ordered += [a]
    return ordered

• 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.