Partial orders
Partial orders describe rankings where not every pair needs to be comparable, such as task dependencies or subsets ordered by inclusion.
Definition
A partial order is reflexive, antisymmetric, and transitive. Examples: \(\le\) on numbers, \(\subseteq\) on sets, and 'divides' on positive integers. A set with a partial order is a poset.
Comparability
In a partial order, some pairs may be incomparable: neither \(\{1\} \subseteq \{2\}\) nor \(\{2\} \subseteq \{1\}\). A total order makes every pair comparable, like \(\le\) on the real numbers. Partial orders model situations where only some things can be ranked.
Hasse diagrams
A Hasse diagram draws a poset with larger elements higher and only the 'immediate' relations as lines; reflexive loops and transitive shortcuts are left out. The divisors of 12 under 'divides' form a diagram with 1 at the bottom and 12 at the top.
Special elements
A maximal element has nothing above it; a greatest element is above everything. A poset can have several maximal elements but at most one greatest. Least and minimal elements are defined similarly. In the subsets of \(\{a, b\}\), \(\varnothing\) is least and \(\{a, b\}\) is greatest.
Topological sorting
A topological sort lists a poset's elements in a total order consistent with the partial order. Course prerequisites, build systems compiling files, and spreadsheets recalculating cells all use topological sorting. It exists exactly when the dependency graph has no cycles.
Worked example
Tasks: A before B, A before C, B before D, C before D. Valid topological orders include A, B, C, D and A, C, B, D. Any order putting D before B or C would violate a dependency.
Lattices
A lattice is a poset where every pair has a least upper bound and a greatest lower bound. Subsets under \(\subseteq\) form a lattice with union and intersection as these bounds. Divisors under 'divides' form a lattice with lcm and gcd. Lattices appear in logic, security levels, and program analysis.
Common mistakes
Including transitive edges in a Hasse diagram. Confusing maximal with greatest. Trying to topologically sort a graph with a cycle. Treating a partial order as total.
Key takeaways
Partial orders are reflexive, antisymmetric, and transitive; some pairs may be incomparable. Hasse diagrams show the essential structure. Maximal and greatest elements differ. Topological sorting turns dependencies into a valid schedule when there are no cycles.
Flashcard
Reflexive, antisymmetric, transitive
Check your understanding
Which relation is a partial order but not a total order?