THE FOLD / GRIND / BACKPROP / THE MIRSKY
THE MIRSKY
covering an order by its widest levels
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Mirsky’s theorem is the elegant dual of Dilworth’s. In any partially ordered set, the minimum number of antichains needed to cover everything equals the length of the longest chain. The construction is immediate: give each element a height — the length of the longest chain ending at it — and elements of equal height form an antichain (two comparable elements always have different heights). The number of distinct heights is exactly the longest chain length, and no fewer antichains can work, since every element of a longest chain must land in a different antichain.
LIT verified live: for thousands of random posets, the height-layering produces exactly (longest-chain-length) layers, each layer is a genuine antichain, and the layers partition every element (window.__mirsky). FIG no framing; the longest chain and the antichain cover computed and compared.
LIT verified live: for thousands of random posets, the height-layering produces exactly (longest-chain-length) layers, each layer is a genuine antichain, and the layers partition every element (window.__mirsky). FIG no framing; the longest chain and the antichain cover computed and compared.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at backprop — assign every element the length of the longest chain reaching it, layer by layer, exactly the way a longest-path pass levels a graph; the layers fall out as antichains. That layering pass is the mechanic. AVAN (AI) built the instrument: the longest-chain height function, the layering into antichains, and the check that the layer count equals the longest chain.
Credit as content: Leon Mirsky (1971); the dual is Robert Dilworth (1950). The weave: David names backprop; I compute each element’s height as its longest chain, group equal heights into antichains, and confirm the number of antichains matches the longest chain length — a minimum cover, for free.
Credit as content: Leon Mirsky (1971); the dual is Robert Dilworth (1950). The weave: David names backprop; I compute each element’s height as its longest chain, group equal heights into antichains, and confirm the number of antichains matches the longest chain length — a minimum cover, for free.
3 ONE DIMENSION
Divisors of 12 ordered by divisibility: 1 < 2,3 < 4,6 < 12. Longest chain 1<2<4<12 has length 4, so 4 antichains cover it: {1}, {2,3}, {4,6}, {12}.
4 TWO DIMENSIONS · INTERACTIVE
A random poset laid out by height; the antichain layers coloured; the layer count vs longest chain checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: an order sliced into its widest levels.
AVAN’s addition (the inverse-companion): to cover an order with the fewest antichains, don’t search — give each element its longest-chain height and slice by height. The inverse of ‘find a minimum antichain cover’ is ‘the longest chain’s length is the answer, and the height layers realise it.’ Magenta is the longest chain (the lower bound); green is the antichain cover that meets it. Chains bound antichain covers.
LIT Genuine Mirsky's theorem (Leon Mirsky, 1971; dual of Dilworth's, 1950). Verified live: for 2000 random posets (transitively-closed DAGs), the height function (longest chain ending at each element) partitions the elements into exactly (longest-chain-length) layers, each of which is a genuine antichain (window.__mirsky.valid).
FIG No framing: the longest-chain height function, the layering into antichains, and the check that the layer count equals the longest chain all run in-browser. The AVAN inverse is honest — covering a poset with the fewest antichains via longest-chain heights (rather than searching) is the actual constructive proof, and the longest chain is the matching lower bound; magenta is the longest chain, green the antichain cover meeting it. Chains bound antichain covers.
FIG No framing: the longest-chain height function, the layering into antichains, and the check that the layer count equals the longest chain all run in-browser. The AVAN inverse is honest — covering a poset with the fewest antichains via longest-chain heights (rather than searching) is the actual constructive proof, and the longest chain is the matching lower bound; magenta is the longest chain, green the antichain cover meeting it. Chains bound antichain covers.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of BACKPROP · David Lee Wise (ROOT0), with AVAN