Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — Additivity and monotonicity of potential

Open
MoserSchneckenreither.lemma_1

by kmehltretter82 · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

Fix a finite signature, a relative rewrite problem, and an annotated signature satisfying its constructor-like uniqueness and superposition requirements. For every ground normal form vvv, sharing p=p1+p2p=p_1+p_2p=p1​+p2​ gives Φ(v:p)=Φ(v:p1)+Φ(v:p2)\Phi(v:p)=\Phi(v:p_1)+\Phi(v:p_2)Φ(v:p)=Φ(v:p1​)+Φ(v:p2​), and componentwise p≤qp\le qp≤q gives Φ(v:p)≤Φ(v:q)\Phi(v:p)\le\Phi(v:q)Φ(v:p)≤Φ(v:q). Both conclusions include the zero annotation and unsupported normal forms.

Preamble
import Definitions.Def_MoserSchneckenreither_Annotations
Formal statement
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
Source
Georg Moser and Manuel Schneckenreither, Automated amortised resource analysis for term rewrite systems, Science of Computer Programming 185 (2020), article 102306, https://doi.org/10.1016/j.scico.2019.102306. Section 5, p. 8, Lemma 1.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex)

lemma_1. Let a signature consist of a natural number NNN, the symbol set S={0,…,N−1}S=\{0,\ldots,N-1\}S={0,…,N−1}, an arity a(f)∈Na(f)\in\mathbb Na(f)∈N for every f∈Sf\in Sf∈S, a nonempty subset C⊆SC\subseteq SC⊆S of constructor symbols, and the requirement that at least one symbol has arity zero; that symbol need not belong to CCC, and nonemptiness of CCC excludes N=0N=0N=0. Terms are finite trees whose leaves may be variables indexed by N\mathbb NN and whose node labelled fff has exactly a(f)a(f)a(f) ordered children. Let PPP consist of arbitrary finite lists PsP_{\mathrm{s}}Ps​ and PwP_{\mathrm{w}}Pw​ of rules; each rule has a left side f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) with f∉Cf\notin Cf∈/C, 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 AAA for the finitely supported functions N→Q≥0\mathbb N\to\mathbb Q_{\ge0}N→Q≥0​, with pointwise addition, scalar multiplication, and order, and write E⊆SE\subseteq SE⊆S for the symbols that either belong to CCC or occur, at any depth, in at least one argument of the left side of at least one rule in PsP_{\mathrm{s}}Ps​ or PwP_{\mathrm{w}}Pw​. An annotated signature FFF consists of a nonempty set Df⊆Aa(f)×Q≥0×AD_f\subseteq A^{a(f)}\times\mathbb Q_{\ge0}\times ADf​⊆Aa(f)×Q≥0​×A of declaration triples for every f∈Sf\in Sf∈S, together with maps Uf:A→Aa(f)U_f:A\to A^{a(f)}Uf​:A→Aa(f) and Kf:A→Q≥0K_f:A\to\mathbb Q_{\ge0}Kf​:A→Q≥0​. For every f∈Ef\in Ef∈E it is required that Df={(Uf(q),Kf(q),q):q∈A}D_f=\{(U_f(q),K_f(q),q):q\in A\}Df​={(Uf​(q),Kf​(q),q):q∈A}, that Kf(p+q)=Kf(p)+Kf(q)K_f(p+q)=K_f(p)+K_f(q)Kf​(p+q)=Kf​(p)+Kf​(q) for all p,q∈Ap,q\in Ap,q∈A, and that Kf(λq)=λKf(q)K_f(\lambda q)=\lambda K_f(q)Kf​(λq)=λKf​(q) for all λ∈Q≥0\lambda\in\mathbb Q_{\ge0}λ∈Q≥0​ and q∈Aq\in Aq∈A. For every such fff and every input index 0≤i<a(f)0\le i<a(f)0≤i<a(f), it is additionally required that Uf(p+q)i=Uf(p)i+Uf(q)iU_f(p+q)_i=U_f(p)_i+U_f(q)_iUf​(p+q)i​=Uf​(p)i​+Uf​(q)i​ for all p,q∈Ap,q\in Ap,q∈A and that Uf(λq)i=λUf(q)iU_f(\lambda q)_i=\lambda U_f(q)_iUf​(λq)i​=λUf​(q)i​ for all λ∈Q≥0\lambda\in\mathbb Q_{\ge0}λ∈Q≥0​ and q∈Aq\in Aq∈A. These quantifiers include zero annotations and λ=0\lambda=0λ=0; for f∉Ef\notin Ef∈/E there are no such equations or required relation between DfD_fDf​ and the maps, beyond nonemptiness of DfD_fDf​. Nullary symbols have empty input families, while the cost identities still apply to them when they belong to EEE. Define RF(x,q)=0R_F(x,q)=0RF​(x,q)=0 for a variable xxx and RF(f(t0,…,ta(f)−1),q)=Kf(q)+∑i=0a(f)−1RF(ti,Uf(q)i)R_F(f(t_0,\ldots,t_{a(f)-1}),q)=K_f(q)+\sum_{i=0}^{a(f)-1}R_F(t_i,U_f(q)_i)RF​(f(t0​,…,ta(f)−1​),q)=Kf​(q)+∑i=0a(f)−1​RF​(ti​,Uf​(q)i​). Define VF(t,q)=RF(t,q)V_F(t,q)=R_F(t,q)VF​(t,q)=RF​(t,q) if ttt contains no variables and every symbol occurring in ttt belongs to EEE, and define VF(t,q)=0V_F(t,q)=0VF​(t,q)=0 otherwise. For every term vvv containing no variables and normal under all rules of PsP_{\mathrm{s}}Ps​ and PwP_{\mathrm{w}}Pw​, both of the following statements hold: for all annotations p,p1,p2∈Ap,p_1,p_2\in Ap,p1​,p2​∈A, if p1(k)+p2(k)=p(k)p_1(k)+p_2(k)=p(k)p1​(k)+p2​(k)=p(k) for every k∈Nk\in\mathbb Nk∈N, then VF(v,p)=VF(v,p1)+VF(v,p2)V_F(v,p)=V_F(v,p_1)+V_F(v,p_2)VF​(v,p)=VF​(v,p1​)+VF​(v,p2​); and for all annotations p,q∈Ap,q\in Ap,q∈A, if p(k)≤q(k)p(k)\le q(k)p(k)≤q(k) for every k∈Nk\in\mathbb Nk∈N, then VF(v,p)≤VF(v,q)V_F(v,p)\le V_F(v,q)VF​(v,p)≤VF​(v,q). 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 vvv, even if the result would equal vvv. 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 vvv lie in EEE: if any occurring symbol lies outside EEE, all the displayed potentials of vvv 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me