Lemma 2 — Footprint identity for rootwise potential
OpenMoserSchneckenreither.footprint_identity_rootwiseLet be a footprint in which every symbol of is constructor-like. For every total assignment from variables to terms, the rootwise potential of at equals the sum of the rootwise potentials of the substitution images at their context annotations, plus . The assignment can take open terms as values.
import Definitions.Def_MoserSchneckenreither_Typing import Definitions.Def_MoserSchneckenreither_RootPotential
namespace MoserSchneckenreither
theorem footprint_identity_rootwise {sig : Signature} {P : Problem sig}
(F : AnnotatedSignature P) {Γ : Context} {k : ℚ≥0} {t : Term sig} {q : Annotation}
(h : Typing F .footprint Γ k t q) (hs : ∀ f ∈ t.symbols, ConstructorLike P f)
(σ : ℕ → Term sig) :
rootPotential F (t.subst σ) q = rootContextPotential F σ Γ + k := by sorry
end MoserSchneckenreitherRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
footprint_identity_rootwise
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. Define for every term and annotation , with values in the nonnegative rationals. It is zero on variables and on applications whose head is outside the constructor-like symbols. At an application with a constructor-like head, it is . An empty sum contributes zero, and the same recursion applies independently in each argument. 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 every signature, problem on that signature, annotated signature for , context , nonnegative rational , term , and annotation , assume and assume that every symbol occurring anywhere in is constructor-like for . The constructor-like condition concerns the occurrences in before substitution. For every total function from natural-number variable names to terms, including assignments to terms containing variables, the following equality holds, with the sum taken over the entries of and equal to zero for the empty list.