Lemma 1 — Additivity and monotonicity of potential
OpenMoserSchneckenreither.lemma_1Fix a finite signature, a relative rewrite problem, and an annotated signature satisfying its constructor-like uniqueness and superposition requirements. For every ground normal form , sharing gives , and componentwise gives . Both conclusions include the zero annotation and unsupported normal forms.
import Definitions.Def_MoserSchneckenreither_Annotations
namespace MoserSchneckenreither
theorem lemma_1 {sig : Signature} {P : Problem sig} (F : AnnotatedSignature P)
(v : Term sig) (hv : v.Ground) (hn : Normal P.rules v) :
(∀ p p₁ p₂ : Annotation, Shares p p₁ p₂ →
potential F v p = potential F v p₁ + potential F v p₂) ∧
(∀ p q : Annotation, p ≤ q → potential F v p ≤ potential F v q) := by sorry
end MoserSchneckenreither
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
lemma_1. Let a signature consist of a natural number , the symbol set , an arity for every , a nonempty subset of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to , and nonemptiness of excludes . Terms are finite trees whose leaves may be variables indexed by and whose node labelled has exactly ordered children. Let consist of arbitrary finite lists and of rules; each rule has a left side with , an arbitrary right-side term, and the requirement that every variable occurring on the right also occurs on the left. Either rule list may be empty, and the lists need not be disjoint. Write for the finitely supported functions , with pointwise addition, scalar multiplication, and order, and write for the symbols that either belong to or occur, at any depth, in at least one argument of the left side of at least one rule in or . An annotated signature consists of a nonempty set of declaration triples for every , together with maps and . For every it is required that , that for all , and that for all and . For every such and every input index , it is additionally required that for all and that for all and . These quantifiers include zero annotations and ; for there are no such equations or required relation between and the maps, beyond nonemptiness of . Nullary symbols have empty input families, while the cost identities still apply to them when they belong to . Define for a variable and . Define if contains no variables and every symbol occurring in belongs to , and define otherwise. For every term containing no variables and normal under all rules of and , both of the following statements hold: for all annotations , if for every , then ; and for all annotations , if for every , then . Normality here means that no rule from either list, under any simultaneous assignment of terms to natural-number variables, can replace an instance of its left side by the corresponding instance of its right side at any subterm position of , even if the result would equal . The annotations in both assertions may be zero, the splitting equality and order are pointwise, and the inequalities are non-strict. There is no separate requirement that every symbol of lie in : if any occurring symbol lies outside , all the displayed potentials of are zero by definition. If both rule lists are empty, every term is normal; the theorem does not require the existence of any ground normal term.