topoSort
plain-language theorem explainer
The topoSort definition constructs a linear extension of any well-founded precedence on a finite event set by recursively extracting minimal elements until the set empties. Researchers proving existence of one-per-tick schedules for finite recognition histories cite it as the constructive ordering primitive. The recursion matches on set emptiness, invokes the minimal-element existence result, and terminates by strict cardinality decrease.
Claim. Let $E$ be a type of events and let $e_1 prec e_2$ be a well-founded precedence relation on $E$. For any finite subset $H subset E$, the ordering $sigma(H)$ is the list obtained by repeatedly selecting a minimal element $e$ of the current set under $prec$ and removing it until the set is empty.
background
The Atomicity module supplies an axiom-free serialization result for finite recognition histories. A Precedence on events $E$ is the binary relation where $prec e_1 e_2$ asserts that $e_1$ must occur before $e_2$. The supporting lemma exists_minimal_in guarantees that every nonempty finite set possesses a minimal element under a well-founded precedence, allowing deterministic extraction of sequential schedules.
proof idea
The definition is a recursive function on Finset $H$. When $H$ is nonempty it extracts a minimal element via exists_minimal_in, prepends it to the result on the erased set, and otherwise returns the empty list. Termination is declared by $H.card$ and discharged by the fact that erasing a member strictly lowers cardinality.
why it matters
topoSort supplies the ordering primitive used by exists_sequential_schedule to assert a one-per-tick schedule for any finite history. It thereby tightens T2 by delivering a constructive, decidable serialization that respects ledger constraints without cost or convexity assumptions. The construction feeds directly into the preservation lemmas that close the atomicity argument.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.
papers checked against this theorem (showing 1 of 1)
-
Alignment widens logit gap on 98% of toxic prompts
"We adapt the classical unit-cost set-cover heuristic to the token-selection setting … sort C by descending F and append tokens until their running total overtakes the gap."