The Dershowitz–Manna ordering is well-founded
ProvedFamousTheorems.dershowitz_manna_well_foundedWell-foundedness of the Dershowitz–Manna ordering. If is a well-founded order on , then the Dershowitz–Manna multiset ordering on finite multisets over is well-founded.
In this ordering when is obtained from by removing a nonempty sub-multiset and adding a multiset each of whose elements is smaller than some element of . Dershowitz and Manna introduced it in 1979 to prove termination of programs and term-rewriting systems. It is a standard tool in rewriting theory and underlies the multiset path ordering.
Formalization note. Mathlib's Multiset.wellFounded_isDershowitzMannaLT. Multiset.IsDershowitzMannaLT M N is the relation above, and WellFoundedLT α says that on the preorder is well-founded.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem dershowitz_manna_well_founded {α : Type*} [Preorder α] [WellFoundedLT α] :
WellFounded (Multiset.IsDershowitzMannaLT : Multiset α → Multiset α → Prop) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Multiset.wellFounded_isDershowitzMannaLT`. Proof here reduces to that Mathlib result.