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