Higman's lemma
ProvedFamousTheorems.higman_lemma_7aHigman's lemma. Let be a preorder on a type and let be partially well-ordered by , meaning that every infinite sequence in has indices with . Then the set of finite lists with entries in is partially well-ordered by the embedding order: if there are indices with for every .
Graham Higman proved this in 1952. It is the finite-word case of Kruskal's tree theorem. It implies that every language closed under taking subwords is regular, and it is a standard tool in the termination analysis of rewriting systems and in the theory of well-structured transition systems.
Formalization note. Mathlib's Set.PartiallyWellOrderedOn.partiallyWellOrderedOn_sublistForall₂. List.SublistForall₂ r l₁ l₂ is the embedding order above, and PartiallyWellOrderedOn is the sequence condition.
import Mathlib
namespace FamousTheorems
theorem higman_lemma_7a {α : Type*} (r : α → α → Prop) [IsPreorder α r] {s : Set α} (hs : s.PartiallyWellOrderedOn r) :
{l : List α | ∀ x ∈ l, x ∈ s}.PartiallyWellOrderedOn (List.SublistForall₂ r) := by sorry
end FamousTheoremsConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.