Partial Orders and Hasse Diagrams

A partial order is simply a "comes before" rule where some pairs are ranked and others aren't. It's called partial because it only orders part of the pairs: Calc I has to come before Calc II, but Linear Algebra and Calc II can go in either order. The formulas are the three rules from the last lesson, adjusted: $a \preceq a$ (everything is at or below itself), the middle one (if $a$ is below $b$ and $b$ is below $a$, they're the same thing, so no going in circles) and the last one (below something that's below $c$ means below $c$). The curly $\preceq$ just means "comes before or equals." Bear with the symbols; the pictures in this lesson make it very concrete.

Compare this with the equivalence relations from the last lesson. Those were reflexive, symmetric and transitive, which made them about sameness. Swap symmetric for antisymmetric and you get something about ranking instead.

In a total order like $\le$ on numbers, any two elements are comparable. In a partial order some aren't: under divisibility, neither of 6 and 10 divides the other.

A Hasse diagram shows a partial order compactly. Draw each element above the ones it covers (directly greater, with nothing in between), connect them with lines, and leave out anything transitivity already implies. Since $1 \mid 2$ and $2 \mid 6$, there's no need to draw a line from 1 to 6. The divisors of 30 under divisibility form a cube, because $30 = 2 \cdot 3 \cdot 5$ and each divisor is a choice of in or out for each of the three primes, just like the subsets of a 3-element set.

• A minimal element has nothing below it, a maximal one nothing above. A least element is below everything.
• A chain is a set of mutually comparable elements; an antichain has no two comparable.

A common mistake. It's tempting to treat "minimal" and "least" as the same. They aren't. Minimal means nothing is below it, while least means it's below everything. In the courses example, Calc I and Linear Algebra are both minimal, but neither is least, since neither one is a prerequisite for the other.

Topological sorting lists the elements so that everything comes after the things below it. Every finite partial order has one, and the reason is simple: there's always some minimal element (otherwise you could keep stepping down forever in a finite set, which would mean going in a circle), so take it, remove it, and repeat. That's how prerequisites become a course schedule and how build tools decide what to compile first.

Build systems, package managers and spreadsheets topologically sort a partial order of dependencies to decide what to compute first.