Not everything can be put in a line. Numbers can: given two different numbers, one is always smaller than the other. But two tasks in a project may be independent, two sets may not be contained in each other, two versions of a document edited in parallel may not be "later" than each other. Partial orders are the mathematical structure that describes these situations, in which some elements are comparable and others are not.
Definition
A relation ≼ on a set A is a partial order if it is:
- reflexive: a ≼ a;
- antisymmetric: if a ≼ b and b ≼ a, then a = b;
- transitive: if a ≼ b and b ≼ c, then a ≼ c.
The pair (A, ≼) is called a partially ordered set, often shortened to poset. Two elements a and b are comparable if a ≼ b or b ≼ a; otherwise they are incomparable.
If every pair of elements is comparable, the order is called total (or linear). ≤ on numbers is total; inclusion between sets is not.
Typical examples
- Inclusion on 𝒫(A): {1} ⊆ {1, 2}, but {1} and {2} are incomparable.
- Divisibility on the positive integers: 3 divides 12, but 4 and 6 are incomparable.
- Lexicographic order on strings: it is total, and it is the dictionary order.
- Componentwise order on pairs: (a, b) ≼ (c, d) if a ≤ c and b ≤ d. (1, 3) and (2, 2) are incomparable.
- Precedence between tasks: "a must be finished before b".
The Hasse diagram
Drawing every arrow of a partial order produces a tangle, because reflexivity and transitivity create a great many arrows. A Hasse diagram keeps only the essentials:
- loops are omitted (reflexivity is understood);
- arrows implied by transitivity are omitted, keeping only the covering relations: b covers a if a ≺ b and there is no c with a ≺ c ≺ b;
- "larger" elements are drawn higher up, so the arrows become plain segments read from bottom to top.
Example: the divisors of 12 ordered by divisibility, {1, 2, 3, 4, 6, 12}. The covering relations are:
- 1 is covered by 2 and by 3;
- 2 is covered by 4 and by 6;
- 3 is covered by 6;
- 4 and 6 are covered by 12.
In the diagram 1 sits at the bottom, 2 and 3 on the next level, 4 and 6 above, 12 at the top. The relation "1 divides 12" does not appear as a direct segment, but it can be read by following an upward path.
Maximal and maximum are not the same
This is the distinction that causes the most confusion.
- An element is maximal if no element is strictly larger than it.
- An element is a maximum if it is greater than or equal to all the others.
A maximum, if it exists, is unique and is also maximal. But there can be many maximal elements, and a maximum may not exist. Take the set {2, 3, 4, 6} ordered by divisibility: 4 and 6 are both maximal (neither divides a larger element of the set), but there is no maximum, because 4 does not divide 6 and 6 does not divide 4. Minimal and minimum are defined in the same way.
In a project, the minimal elements of the precedence order are the tasks that can start immediately; the maximal ones are the tasks nothing else depends on.
Least upper bounds and lattices
An upper bound of two elements a and b is an element above both. The smallest upper bound, if it exists, is the least upper bound (or join), a ∨ b. Dually there is the greatest lower bound (or meet), a ∧ b.
A poset in which every pair has both a join and a meet is called a lattice. Examples:
| Poset | a ∨ b | a ∧ b |
|---|---|---|
| (𝒫(A), ⊆) | A ∪ B | A ∩ B |
| (ℤ⁺, divides) | lcm(a, b) | gcd(a, b) |
| (ℝ, ≤) | max(a, b) | min(a, b) |
Lattices turn up in computing more often than you might think. In multilevel security models, classification levels combined with categories form a lattice, and information that merges two sources receives their join. In static program analysis, abstract values form a lattice and the results of different branches are combined with the join.
Partial orders in distributed systems
When several nodes modify data in parallel, events have no natural total order. Vector clocks assign each event a vector of counters, one per node, and compare them with the componentwise order seen above. If one vector is less than or equal to the other in every position, the first event precedes the second; if neither dominates, the events are concurrent, that is incomparable, and the system knows it is facing a possible conflict to resolve.
To line up the elements of a partial order while respecting its constraints, you use topological sorting, which extends the partial order to a compatible total one.
In short
- A partial order is reflexive, antisymmetric and transitive; some elements may be incomparable.
- A Hasse diagram shows only the covering relations, with larger elements higher up.
- Maximal does not mean maximum: there can be several maximal elements and no maximum.
- A lattice guarantees a join and a meet for every pair, like union and intersection.
- Vector clocks and security levels are concrete applications of partial orders.
