Represent orders with lower sets and cover diagrams

Try

Return to the divisibility order on P consisting of 1, 2, 3 and 6. Instead of representing a part by its size, represent it by every available part that can divide it. The representation of 2 is the set containing 1 and 2; the representation of 6 is all of P. This changes the objects into sets while preserving the comparisons.

Read each middle cell as a set, not an ordered list. Compare the sets for 2 and 3. Their equal sizes do not make them equal, and neither contains the other. By contrast, the set for 2 is contained in the set for 6, exactly matching 2 dividing 6. Keeping only a count would lose information that the full set retains.

Predict

A lower set U contains every predecessor of each of its members: if x belongs to U and y≤x, then y belongs to U. Is the set containing 1, 2 and 3 a lower set? Yes. Does it occur as a principal lower set in the table? No. Adding the top element 6 would force the whole set, while neither middle element has both middle elements below it.

Predict whether every lower set must have an element generating it. The empty set already gives another counterexample in any nonempty poset: every principal lower set contains its generating element. The representation can be faithful without reaching every set in its target. This distinction is the difference between an embedding and a bijection onto all lower sets.

Experiment

Build a second order whose elements are pairs (a,b), where a is 0 or 1 and b is 0, 1 or 2. Declare (a,b)≤(c,d) exactly when a≤c and b≤d. Draw the six points using a as the horizontal coordinate and b as the vertical coordinate. A horizontal move right or a vertical move upward increases one coordinate while keeping the other fixed.

List everything above (0,1): itself, (0,2), (1,1), (1,2). Now test (0,2) against (1,0). One coordinate increases while the other decreases, so the elements are incomparable. Repair the mistaken rule “strictly below means both coordinates strictly smaller”: (0,0) is strictly below (1,0), despite equal second coordinates.

Understand

For any non-strict poset, define ↓x to contain all z satisfying z≤x. It is a lower set: if w≤z≤x, transitivity gives w≤x. More importantly,

x≤y if and only if ↓x is contained in ↓y.

For the forward implication, take any z in ↓x and use z≤x≤y. For the reverse implication, reflexivity puts x in ↓x; inclusion then puts x in ↓y, which means x≤y. Consequently equal principal sets imply x≤y and y≤x, so antisymmetry gives x=y. This proves injectivity and both directions of order preservation. No finiteness assumption was used.

The self-member is essential. If we record only strict predecessors, two incomparable minimal elements both get the empty set. Adding each element itself repairs that collision and recovers the principal construction. For strict comparisons, x is strictly below y exactly when ↓x is a proper subset of ↓y: inclusion gives x≤y, and equality is excluded by injectivity. Conversely, if x is strictly below y, inclusion holds and y cannot lie below x without forcing equality.

The product construction also works for arbitrary posets. Reflexivity holds in each coordinate. Mutual comparisons give equality in each coordinate by antisymmetry. Two successive comparisons compose in each coordinate by transitivity. The associated strict order requires all coordinate comparisons weakly and at least one coordinate different; it does not require every coordinate to change.

Finally, y covers x when x is strictly below y and no element lies strictly between them. In a finite poset, every strict comparison can be recovered by a directed path of cover edges. Prove this by induction on the number of elements strictly between x and y. With none, the comparison is a cover. Otherwise choose an intermediate z. Both smaller intervals have fewer interior elements, so their cover paths exist by induction; concatenate them. Conversely, every cover path gives a comparison by transitivity.

This also proves a uniqueness statement about compressed diagrams on the same vertices. Any directed graph with exactly the strict-order reachability must include every cover edge: a longer path for a cover would supply a forbidden intermediate element. The cover graph already generates all comparisons, so any extra edge is unnecessary. Thus it is the unique inclusion-minimal such graph. Reflexive comparisons are recovered separately by allowing a path of length zero.

Apply

Compare the integers and the rational numbers with their usual orders. In the integers, n+1 covers n. Every m strictly below n has the finite path m, m+1, …, n. The cover representation works even though the set is infinite.

In the rationals, every x strictly below y has the intermediate rational (x+y)/2. There are no covers at all. The empty cover graph cannot recover even the comparison 0 strictly below 1. The failure is not merely “infinity”: the integer example rules out that explanation. The finite induction also extends when each individual interval has finitely many intermediate elements. Rational intervals do not satisfy that condition.

Return to the six-point product and remove (0,1). Redraw its covers on the remaining domain. Now (0,2) covers (0,0), because the former intermediate point is gone. However, (1,1) does not cover (0,0), because (1,0) remains between them. A cover is determined by the full remaining order, not by the original drawing’s edges.

Continue

In the written tasks, provide both implications for a proposed representation. Demonstrating that comparisons create inclusions is only half an embedding proof: you must also show that inclusions cannot create false comparisons. Likewise, a compressed picture needs a reconstruction argument, not just a visually plausible layout. Keep the three targets distinct: principal lower sets preserve every order; product orders compare coordinates; cover paths reconstruct finite orders, with additional interval assumptions needed beyond the finite setting.

For a refresher on directed paths and acyclic graphs, return to directed graphs and topological order. Revisit strict and non-strict orders if a diagonal comparison or an extreme-element definition caused difficulty.