Lodha–Moore Lemma 5.6 fails when the commutation rule moves only positive letters
ProvedLodhaMoorePosCommute.not_forall_exists_derives_sufficientlyExpandedRead with the substitutions of LodhaMoorePosCommute.Step, Lemma 5.6 of Lodha and Moore (p. 11: "If is a standard form, then there is a sufficiently expanded standard form which can be derived from ") is false. LodhaMoorePosCommute.Step is the Lodha–Moore mission's substitution relation with the commutation applied only to letters with positive exponents. The statement says that not every standard form (LodhaMoore.IsStandardForm) derives a sufficiently expanded standard form (LodhaMoore.SufficientlyExpanded) by finitely many such substitutions.
The proof of Lemma 5.6 moves letters with negative exponents by this substitution: "We may therefore apply substitution of the form for incompatible and in order to move any two distinct occurrences of , , or to the same position" (p. 11). The letter there has exponent , so the printed rule, which carries no exponents, must be read with arbitrary exponents. The Lodha–Moore mission reads it that way (LodhaMoore.Step).
The counterexample is the standard form , where is the empty sequence. It is not sufficiently expanded: is not exposed and does not occur. Under the restricted rule, no word derived from ever has two adjacent positive -letters or two adjacent -letters with the same subscript. So commutation, cancellation and merging of -letters never apply, and no derived standard form is sufficiently expanded. With arbitrary exponents, derives , which is sufficiently expanded.
import Definitions.Def_LodhaMoorePosCommute import Definitions.Def_LodhaMooreWords import Mathlib
namespace LodhaMoorePosCommute
theorem not_forall_exists_derives_sufficientlyExpanded :
¬ ∀ Ω : LodhaMoore.Word, LodhaMoore.IsStandardForm Ω →
∃ Ω', Relation.ReflTransGen Step Ω Ω' ∧ LodhaMoore.IsStandardForm Ω' ∧
LodhaMoore.SufficientlyExpanded Ω' := by
sorry
end LodhaMoorePosCommute