Termination of the hydra game (Kirby–Paris): CutExpand is well-founded
ProvedFamousTheorems.hydra_cut_expand_well_founded_7aTermination of the hydra game. Let be a well-founded relation on . Then the relation on finite multisets of elements of is well-founded. Here relates to when is obtained from by removing one element and adding finitely many elements with .
In the hydra game of Kirby and Paris (1982), Hercules cuts off a head of a finite tree and the hydra regrows finitely many copies of part of the tree. The theorem gives the essential step of the proof that Hercules always wins. Kirby and Paris showed that this cannot be proved in Peano arithmetic. The transitive closure of this relation is the Dershowitz–Manna multiset ordering induced by , which is used to prove termination of rewriting systems.
Formalization note. Mathlib's WellFounded.cutExpand. Relation.CutExpand r is defined on Multiset α. In Mathlib the relation CutExpand r s' s holds when is obtained from by replacing one element by a finite multiset of elements that are -smaller than .
import Mathlib
namespace FamousTheorems
theorem hydra_cut_expand_well_founded_7a {α : Type*} {r : α → α → Prop} (hr : WellFounded r) : WellFounded (Relation.CutExpand r) := by sorry
end FamousTheorems