Lemma 2 — Counterexample with whole-term potential
OpenMoserSchneckenreither.footprint_identity_counterexampleA footprint whose term uses only constructor-like symbols can violate the potential identity of Lemma 2 after a normalised substitution covering its context. The witness instantiates a variable beneath a constructor with a stuck defined normal form.
import Definitions.Def_MoserSchneckenreither_Typing
namespace MoserSchneckenreither
theorem footprint_identity_counterexample :
∃ (sig : Signature) (P : Problem sig) (F : AnnotatedSignature P) (Γ : Context)
(σ : Substitution sig) (t : Term sig) (q : Annotation) (k : ℚ≥0),
σ.Normalised P ∧ (∀ x ∈ Γ.keys, x ∈ σ.domain) ∧
Typing F .footprint Γ k t q ∧ (∀ f ∈ t.symbols, ConstructorLike P f) ∧
potential F (t.subst σ.apply) q ≠ contextPotential F σ Γ + k := by sorry
end MoserSchneckenreitherRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
footprint_identity_counterexample
A signature has symbols indexed by the integers from through for some , a natural-number arity for each symbol , a nonempty subset of constructor symbols, and at least one symbol of arity zero. A term is a variable labelled by a natural number or an application . A problem has a strict list and a weak list of rewrite rules. Each rule has left-hand side with outside the constructor subset, and every variable on its right-hand side occurs on its left-hand side. Call a symbol constructor-like for if it is in the constructor subset or occurs anywhere in a left-hand-side argument of some rule in either list. An annotation is a finitely supported sequence of nonnegative rationals indexed by , with pointwise addition and scalar multiplication. An annotated signature for gives each symbol a nonempty set of allowed declarations, each with one input annotation per argument, a nonnegative rational cost, and an output annotation. It also gives functions and on output annotations and, for , argument indices , returning an annotation and a nonnegative rational, respectively. For each constructor-like and each , the declaration with output , inputs and cost is allowed. Every allowed declaration of such an with output has precisely those inputs and cost. For these symbols and each applicable , the functions and preserve annotation addition and multiplication by every nonnegative rational. A context is a list of pairs of a natural-number variable name and an annotation. Write for the footprint typing judgment, the relation generated by the following five rules. Any allowed declaration of with inputs , cost , and output gives for pairwise distinct variable names , listing the pairs in argument order. A variable has judgment for every annotation . To compose, take a judgment with pairwise distinct and judgments for all . This gives the judgment on with output , cost , and context the concatenation of in argument order, provided every is absent from the names in every , different have disjoint name sets, and every variable occurs at most once in . Sharing starts with a judgment on in the context followed by , with pairwise distinct and absent from the names in . It gives the judgment with the same cost and output annotation on the term obtained by renaming both and to throughout , in the context followed by . The pairs of a context may be permuted without changing the term, cost, or output annotation. For a function assigning a term to each natural-number variable name, write for the term obtained by replacing each variable occurrence of by and retaining the application symbols and argument positions. For any term and annotation , define its potential to be zero unless is ground, meaning it has no variables, and every symbol occurring anywhere in is constructor-like for . When these two conditions hold, , where is zero on variables and is on an application for any symbol , with empty sum zero. The theorem asserts the existence of a signature, a problem on that signature, an annotated signature for , a context , a substitution consisting of a finite set of variable names and a total term assignment on natural-number names, a term , an annotation , and a nonnegative rational with all the following properties. For each , is ground and admits no single rewrite step at any position by a rule from either list of . Such a step replaces a rule's left-hand side by its right-hand side at that position, substituting both sides by the same arbitrary total term assignment and retaining all surrounding application symbols and the other arguments. Every variable name in belongs to . The judgment holds, and every symbol occurring anywhere in is constructor-like for . With for and the variable otherwise, the following inequality of values holds. The sum runs over the entries of with empty sum zero.