Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Terms, substitutions, and relative innermost rewriting

Definition
MoserSchneckenreither_Syntax

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

amortized-analysiscomplexityresource-analysisterm-rewritingtype-systems

A finite signature separates constructors from defined symbols and contains at least one constant. Arity-correct terms use natural-number variables. Rules have a defined root and no extra right-hand-side variables; their patterns may be nonlinear and may contain defined symbols. The relative problem consists of finite strict and weak rule sets. Ordinary rewriting, normal forms, normalised finite substitutions, restricted innermost steps, relative steps, and finite derivations with only strict steps charged are defined directly from rules. A basic term has a defined root and constructor-term arguments, which may contain variables. Constructor-like symbols are precisely constructors and symbols appearing inside a left-hand-side argument. A supported term is ground and contains only these symbols. The two rule sets may overlap; membership in a chosen part determines the charge of that application.

Definition code
import Mathlib.Data.Finset.Basic
import Mathlib.Data.List.OfFn
import Mathlib.Logic.Relation

/-!
First-order syntax and relative innermost rewriting, following Moser and Schneckenreither,
*Automated Amortised Resource Analysis for Term Rewrite Systems*, arXiv:1811.09071v1,
Section 3, pp. 6–7. Mathematical authorship belongs to Georg Moser and Manuel Schneckenreither.
-/

namespace MoserSchneckenreither

/-- A finite signature with a nonempty constructor part and at least one constant. -/
structure Signature where
  count : ℕ
  arity : Fin count → ℕ
  constructors : Finset (Fin count)
  constructors_nonempty : constructors.Nonempty
  has_constant : ∃ f, arity f = 0

abbrev Symbol (sig : Signature) := Fin sig.count

/-- Variables are natural numbers; symbol arities are enforced by the term datatype. -/
inductive Term (sig : Signature) where
  | var : ℕ → Term sig
  | app (f : Symbol sig) : (Fin (sig.arity f) → Term sig) → Term sig

namespace Term

variable {sig : Signature}

def vars : Term sig → List ℕ
  | .var x => [x]
  | .app _ ts => (List.ofFn fun i ↦ vars (ts i)).flatten

def size : Term sig → ℕ
  | .var _ => 1
  | .app _ ts => 1 + (List.ofFn fun i ↦ size (ts i)).sum

def subst (σ : ℕ → Term sig) : Term sig → Term sig
  | .var x => σ x
  | .app f ts => .app f fun i ↦ subst σ (ts i)

def rename (ρ : ℕ → ℕ) (t : Term sig) := t.subst fun x ↦ .var (ρ x)

def Ground (t : Term sig) : Prop := t.vars = []

def Linear (t : Term sig) : Prop := t.vars.Nodup

/-- Constructor terms, including variables, as used in the definition of a basic term. -/
inductive Constructor : Term sig → Prop
  | var (x : ℕ) : Constructor (.var x)
  | app (f : Symbol sig) (ts : Fin (sig.arity f) → Term sig)
      (hf : f ∈ sig.constructors) (ht : ∀ i, Constructor (ts i)) : Constructor (.app f ts)

def Basic : Term sig → Prop
  | .var _ => False
  | .app f ts => f ∉ sig.constructors ∧ ∀ i, Constructor (ts i)

def symbols : Term sig → List (Symbol sig)
  | .var _ => []
  | .app f ts => f :: (List.ofFn fun i ↦ symbols (ts i)).flatten

end Term

/-- A rule has a defined root and may have arbitrary, nonlinear argument patterns. -/
structure Rule (sig : Signature) where
  head : Symbol sig
  args : Fin (sig.arity head) → Term sig
  rhs : Term sig
  defined_head : head ∉ sig.constructors
  no_extra_variables : ∀ x ∈ rhs.vars, x ∈ (Term.app head args).vars

def Rule.lhs {sig : Signature} (r : Rule sig) : Term sig := .app r.head r.args

/-- Lists present finite rule sets; order and duplicate membership do not affect rewriting. -/
structure Problem (sig : Signature) where
  strict : List (Rule sig)
  weak : List (Rule sig)

def Problem.rules {sig : Signature} (P : Problem sig) := P.strict ++ P.weak

/-- A finite simultaneous substitution, with identity outside its explicit domain. -/
structure Substitution (sig : Signature) where
  domain : Finset ℕ
  assignment : ℕ → Term sig

def Substitution.apply {sig : Signature} (σ : Substitution sig) (x : ℕ) : Term sig :=
  if x ∈ σ.domain then σ.assignment x else .var x

/-- Ordinary rewriting under arbitrary term contexts. -/
inductive Rewrites {sig : Signature} (rules : List (Rule sig)) : Term sig → Term sig → Prop
  | root (r : Rule sig) (hr : r ∈ rules) (σ : ℕ → Term sig) :
      Rewrites rules (r.lhs.subst σ) (r.rhs.subst σ)
  | arg (f : Symbol sig) (ts us : Fin (sig.arity f) → Term sig) (i : Fin (sig.arity f))
      (hstep : Rewrites rules (ts i) (us i)) (hrest : ∀ j, j ≠ i → ts j = us j) :
      Rewrites rules (.app f ts) (.app f us)

def Normal {sig : Signature} (rules : List (Rule sig)) (t : Term sig) : Prop :=
  ¬ ∃ u, Rewrites rules t u

def Substitution.Normalised {sig : Signature} (P : Problem sig) (σ : Substitution sig) : Prop :=
  ∀ x ∈ σ.domain, (σ.assignment x).Ground ∧ Normal P.rules (σ.assignment x)

/-- Restricted steps use rules in `rules` and normalise redex arguments with respect to `Q`. -/
inductive RestrictedStep {sig : Signature} (Q rules : List (Rule sig)) :
    Term sig → Term sig → Prop
  | root (r : Rule sig) (hr : r ∈ rules) (σ : ℕ → Term sig)
      (hnormal : ∀ i, Normal Q ((r.args i).subst σ)) :
      RestrictedStep Q rules (r.lhs.subst σ) (r.rhs.subst σ)
  | arg (f : Symbol sig) (ts us : Fin (sig.arity f) → Term sig) (i : Fin (sig.arity f))
      (hstep : RestrictedStep Q rules (ts i) (us i))
      (hrest : ∀ j, j ≠ i → ts j = us j) :
      RestrictedStep Q rules (.app f ts) (.app f us)

/-- One relative step is any finite weak prefix, one strict step, and any finite weak suffix. -/
def RelativeStep {sig : Signature} (P : Problem sig) (s t : Term sig) : Prop :=
  ∃ u v, Relation.ReflTransGen (RestrictedStep P.rules P.weak) s u ∧
    RestrictedStep P.rules P.strict u v ∧
    Relation.ReflTransGen (RestrictedStep P.rules P.weak) v t

/-- Counted elementary steps retain both the strict and weak parts, including possible overlap. -/
inductive CountedStep {sig : Signature} (P : Problem sig) : ℕ → Term sig → Term sig → Prop
  | strict {s t} (h : RestrictedStep P.rules P.strict s t) : CountedStep P 1 s t
  | weak {s t} (h : RestrictedStep P.rules P.weak s t) : CountedStep P 0 s t

/-- Finite derivations, charging only strict-rule applications. -/
inductive Derivation {sig : Signature} (P : Problem sig) : Term sig → ℕ → Term sig → Prop
  | refl (t) : Derivation P t 0 t
  | step {s t u n K} (hstep : CountedStep P K s t) (hrest : Derivation P t n u) :
      Derivation P s (K + n) u

/-- Defined symbols below a rule's root must be treated as constructor-like symbols. -/
def ConstructorLike {sig : Signature} (P : Problem sig) (f : Symbol sig) : Prop :=
  f ∈ sig.constructors ∨ ∃ r ∈ P.rules, ∃ i, f ∈ (r.args i).symbols

/-- Ground terms containing only constructors and constructor-like symbols. -/
def Supported {sig : Signature} (P : Problem sig) (t : Term sig) : Prop :=
  t.Ground ∧ ∀ f ∈ t.symbols, ConstructorLike P f

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 4, p. 6, preliminaries and Definition 1.
Read-back

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

readback_model: GPT-6 (Codex)

Signature. A signature is data consisting of a natural number nnn, an arity function a:{0,…,n−1}→Na:\{0,\ldots,n-1\}\to\mathbb Na:{0,…,n−1}→N, a finite set C⊆{0,…,n−1}C\subseteq\{0,\ldots,n-1\}C⊆{0,…,n−1}, a proof that CCC is nonempty, and a proof that there exists an index f∈{0,…,n−1}f\in\{0,\ldots,n-1\}f∈{0,…,n−1} with a(f)=0a(f)=0a(f)=0. The indices are the available symbols and CCC is the designated set of constructors. These requirements exclude n=0n=0n=0. The symbol of arity zero need not belong to CCC, and membership in CCC imposes no restriction on arity.

Symbol. For any signature Σ\SigmaΣ, consisting of a natural number nnn, arities a(f)∈Na(f)\in\mathbb Na(f)∈N for indices 0≤f<n0\le f<n0≤f<n, a nonempty set CCC of those indices, and the existence of at least one index of arity zero, a symbol of Σ\SigmaΣ is an index fff with 0≤f<n0\le f<n0≤f<n. This is the same type of indices used by the signature, including indices inside and outside CCC; the signature requirements imply that the type of symbols is nonempty.

Term. For every signature Σ\SigmaΣ with symbols 0≤f<n0\le f<n0≤f<n, an arity a(f)∈Na(f)\in\mathbb Na(f)∈N for each symbol, a nonempty designated constructor set CCC, and at least one symbol of arity zero, the terms over Σ\SigmaΣ form the inductively generated type with two constructions: a variable xxx for any x∈Nx\in\mathbb Nx∈N, and an application f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) for any symbol fff and any family of terms indexed by 0≤i<a(f)0\le i<a(f)0≤i<a(f). Thus terms are finite ordered trees, variable labels can be any natural numbers, and every application has exactly its head symbol's prescribed number of children. A symbol of arity zero gives an application with no children. Both constructor symbols and symbols outside CCC can head applications, and the construction does not require a term to contain a variable.

Term.vars. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term built from natural-number variables and applications f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​), the variable list is defined recursively as follows: the list for the variable xxx is the one-element list [x][x][x], and the list for an application is the concatenation of the variable lists of t0,t1,…,ta(f)−1t_0,t_1,\ldots,t_{a(f)-1}t0​,t1​,…,ta(f)−1​ in increasing child-index order. Every occurrence is retained, including repeated occurrences of the same variable. An application of arity zero has the empty variable list.

Term.size. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, the size of a finite term built from natural-number variables and symbol applications is a natural number defined recursively by size⁡(x)=1\operatorname{size}(x)=1size(x)=1 for every variable x∈Nx\in\mathbb Nx∈N and size⁡(f(t0,…,ta(f)−1))=1+∑i=0a(f)−1size⁡(ti)\operatorname{size}(f(t_0,\ldots,t_{a(f)-1}))=1+\sum_{i=0}^{a(f)-1}\operatorname{size}(t_i)size(f(t0​,…,ta(f)−1​))=1+∑i=0a(f)−1​size(ti​). Each variable occurrence and each application contributes one. For an application of arity zero the sum is empty and equals zero, so its size is one.

Term.subst. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, and every total function σ:N→T\sigma:\mathbb N\to Tσ:N→T into the finite terms TTT over these symbols and natural-number variables, substitution sends the variable xxx to σ(x)\sigma(x)σ(x) and sends f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) to f(t0[σ],…,ta(f)−1[σ])f(t_0[\sigma],\ldots,t_{a(f)-1}[\sigma])f(t0​[σ],…,ta(f)−1​[σ]), where the bracket notation denotes this recursively defined operation. The chosen term σ(x)\sigma(x)σ(x) is returned as it is, so variables inside it are not recursively substituted during that replacement. The function σ\sigmaσ is arbitrary and need not have finite support or ground values; nullary applications are unchanged.

Term.rename. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, every function ρ:N→N\rho:\mathbb N\to\mathbb Nρ:N→N, and every finite term ttt built from natural-number variables and symbol applications, renaming ttt by ρ\rhoρ means replacing every variable occurrence xxx by the variable ρ(x)\rho(x)ρ(x) and recursively retaining each application head and the ordering of all its children. Equivalently, it is simultaneous substitution with the variable term ρ(x)\rho(x)ρ(x) as the image of xxx. No injectivity or surjectivity is required of ρ\rhoρ, so distinct variable labels may become equal; an application of arity zero is unchanged.

Term.Ground. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term ttt built from natural-number variables and symbol applications, ttt is ground exactly when its variable-occurrence list is empty. That list is [x][x][x] at a variable xxx and is the ordered concatenation of the children's lists at an application. Consequently this predicate requires the absence of all variable occurrences; every nullary application is ground, regardless of whether its head belongs to the constructor set, whereas a variable term is not ground.

Term.Linear. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, and every finite term ttt built from natural-number variables and symbol applications, ttt is linear exactly when its variable-occurrence list has no duplicate entries. The list contains xxx once for a variable term xxx and is formed at each application by concatenating its children's lists in increasing index order, retaining all occurrences. Thus no natural-number variable label may occur twice anywhere in ttt. A variable term is linear, and every term with no variable occurrences, including every nullary application, is linear because its variable list is empty.

Term.Constructor. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty designated constructor set CCC, and at least one symbol of arity zero, the constructor-term predicate on finite terms is inductively generated by these clauses: for each x∈Nx\in\mathbb Nx∈N, the variable xxx satisfies the predicate; and for every symbol fff and family of terms (ti)0≤i<a(f)(t_i)_{0\le i<a(f)}(ti​)0≤i<a(f)​, the application f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) satisfies it whenever f∈Cf\in Cf∈C and every tit_iti​ satisfies it. Equivalently, every application symbol in the tree must belong to CCC, while variables are allowed without restriction or a requirement of distinctness. For a(f)=0a(f)=0a(f)=0 the child condition is vacuous, so a nullary application satisfies the predicate exactly when its head is in CCC. The signature's required nullary symbol is not required to be in CCC.

Term.Basic. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty designated constructor set CCC, and at least one symbol of arity zero, a variable term is not basic, and an application f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) is basic exactly when f∉Cf\notin Cf∈/C and each child tit_iti​ is a finite tree in which every application symbol belongs to CCC, with arbitrary natural-number variables permitted as leaves. In particular, the children need not be ground or have distinct variable occurrences. When a(f)=0a(f)=0a(f)=0 the child requirement is vacuous, and basicness is exactly f∉Cf\notin Cf∈/C. If every symbol belongs to CCC, there are no basic terms.

Term.symbols. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, the symbol list of a finite term over these symbols and natural-number variables is defined recursively by assigning the empty list to every variable and assigning to f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) the list beginning with fff followed by the concatenated symbol lists of t0,t1,…,ta(f)−1t_0,t_1,\ldots,t_{a(f)-1}t0​,t1​,…,ta(f)−1​ in increasing child-index order. This records every application-head occurrence, with repetitions retained. In particular, the list for a nullary application is [f][f][f].

Rule. For every signature Σ\SigmaΣ consisting of finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty designated constructor set CCC, and at least one symbol of arity zero, a rule consists of a head symbol hhh, a family of argument terms (ℓi)0≤i<a(h)(\ell_i)_{0\le i<a(h)}(ℓi​)0≤i<a(h)​, a right-hand term rrr, a proof that h∉Ch\notin Ch∈/C, and a proof that every natural number occurring as a variable in rrr occurs as a variable in the application h(ℓ0,…,ℓa(h)−1)h(\ell_0,\ldots,\ell_{a(h)-1})h(ℓ0​,…,ℓa(h)−1​). Terms here are finite trees of natural-number variables and applications of symbols with their prescribed arities; the variable list is obtained by listing variable leaves in child order, retaining repetitions, and the last requirement is membership inclusion of these lists, with no bound on the multiplicity of a permitted variable in rrr. The arguments may contain arbitrary symbols and repeated variables. If a(h)=0a(h)=0a(h)=0, the left-hand variable list is empty and hence rrr has no variables. A rule can exist only if some symbol lies outside CCC.

Rule.lhs. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set CCC, and at least one symbol of arity zero, and every rule consisting of a head h∉Ch\notin Ch∈/C, argument terms (ℓi)0≤i<a(h)(\ell_i)_{0\le i<a(h)}(ℓi​)0≤i<a(h)​, and a right-hand term rrr whose variable labels all occur in those arguments, the left-hand term is defined to be exactly the application h(ℓ0,…,ℓa(h)−1)h(\ell_0,\ldots,\ell_{a(h)-1})h(ℓ0​,…,ℓa(h)−1​). The terms are finite trees of natural-number variables and arity-respecting symbol applications. The right-hand term and the proofs attached to the rule contribute no children to this application. For a nullary head this is the nullary application hhh, and the rule condition then requires rrr to have no variables.

Problem. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty designated constructor set CCC, and at least one symbol of arity zero, a problem consists of two lists of rules, called its strict list and its weak list. Each rule has the form h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r, where h∉Ch\notin Ch∈/C, all terms are finite trees of natural-number variables and arity-respecting symbol applications, and every variable occurring in rrr occurs in some ℓi\ell_iℓi​. The two lists may each be empty, may contain repeated rules, and may share rules; there is no further field imposing a relation between the lists or a condition on their combined behavior.

Problem.rules. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty designated constructor set CCC, and at least one symbol of arity zero, and every problem PPP whose strict and weak components are lists of rules, its combined rule list is its strict list followed by its weak list. A rule here is an application h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r with h∉Ch\notin Ch∈/C and with every variable in rrr occurring in the arguments, where all terms are finite arity-respecting symbol trees with natural-number variable leaves. Concatenation preserves the order within each list and every repetition, including a rule appearing in both lists; either list, or both, may be empty.

Substitution. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, a substitution record consists of a finite set D⊆ND\subseteq\mathbb ND⊆N called its domain and a total assignment function A:N→TA:\mathbb N\to TA:N→T, where TTT is the type of finite trees of natural-number variables and arity-respecting applications of the symbols. The domain may be empty. The record includes an assigned term for every natural number, including numbers outside DDD, and imposes no condition on these values: neither groundness nor a relationship between DDD and the places where A(x)A(x)A(x) differs from the variable xxx is required.

Substitution.apply. For every signature Σ\SigmaΣ with finitely many symbols fff, natural-number arities a(f)a(f)a(f), a nonempty designated constructor set, and at least one symbol of arity zero, every substitution record (D,A)(D,A)(D,A) with finite D⊆ND\subseteq\mathbb ND⊆N and arbitrary total assignment A:N→TA:\mathbb N\to TA:N→T into the finite terms over these symbols and natural-number variables, and every x∈Nx\in\mathbb Nx∈N, its applied value at xxx is A(x)A(x)A(x) if x∈Dx\in Dx∈D, and is the variable term xxx if x∉Dx\notin Dx∈/D. Values of AAA outside DDD therefore do not affect this function. The domain may include an xxx for which A(x)A(x)A(x) is already the variable xxx, and for D=∅D=\varnothingD=∅ this function returns the variable xxx for every xxx.

Rewrites. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, and every list RRR of rules h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r having h∉Ch\notin Ch∈/C and no variable in rrr absent from the arguments, the one-step rewriting relation on finite terms is the least relation with the following two properties. For every rule in RRR and every total assignment σ:N→T\sigma:\mathbb N\to Tσ:N→T of finite terms to variables, it relates h(ℓ0[σ],…,ℓa(h)−1[σ])h(\ell_0[\sigma],\ldots,\ell_{a(h)-1}[\sigma])h(ℓ0​[σ],…,ℓa(h)−1​[σ]) to r[σ]r[\sigma]r[σ], where substitution simultaneously replaces original variable leaves by their assigned terms, retaining all application heads and their child order. Also, for every symbol fff, two families of terms (tj)j<a(f)(t_j)_{j<a(f)}(tj​)j<a(f)​ and (uj)j<a(f)(u_j)_{j<a(f)}(uj​)j<a(f)​, and an index i<a(f)i<a(f)i<a(f), it relates f(t0,…,ta(f)−1)f(t_0,\ldots,t_{a(f)-1})f(t0​,…,ta(f)−1​) to f(u0,…,ua(f)−1)f(u_0,\ldots,u_{a(f)-1})f(u0​,…,ua(f)−1​) if tit_iti​ rewrites to uiu_iui​ and tj=ujt_j=u_jtj​=uj​ for every j≠ij\ne ij=i. Thus one rule replacement may occur at any finite position inside a term, with all surrounding symbols and other children retained. The assignment is not required to be ground, finitely supported, or normal. There is no child-position case for a nullary application; with RRR empty no step exists. The source and target are not required to be different, and each relation instance represents one rule replacement rather than a sequence of several replacements.

Normal. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every rule list RRR, and every finite term ttt, normality of ttt means that there is no finite term uuu obtainable from ttt by one rule replacement anywhere in its tree. Each rule in RRR is h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r with h∉Ch\notin Ch∈/C and every variable of rrr occurring in the arguments; a replacement may use any total assignment of finite terms to natural-number variables, simultaneously substitute into both sides, and replace the resulting left side by the resulting right side at the root or inside any child, leaving the surrounding tree and all other children unchanged. Terms are built from natural-number variables and applications of the prescribed arities. The excluded target uuu includes u=tu=tu=t, so a self-replacement prevents normality. No groundness is required; if RRR is empty, every term is normal.

Substitution.Normalised. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every problem PPP comprising strict and weak rule lists, and every substitution record (D,A)(D,A)(D,A) with finite D⊆ND\subseteq\mathbb ND⊆N and total assignment of finite terms A:N→TA:\mathbb N\to TA:N→T, the record is normalised exactly when, for every x∈Dx\in Dx∈D, the term A(x)A(x)A(x) has no variable occurrences and admits no one-step rewrite using the concatenation of the strict and weak lists. Terms are finite trees of natural-number variables and arity-respecting symbol applications; each rule is h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r with h∉Ch\notin Ch∈/C and every variable of rrr present in the arguments. A one-step rewrite replaces at any position an instance of a rule's left side by the corresponding right-side instance under an arbitrary total simultaneous substitution, preserving the surrounding tree and other children; a rewrite back to the same term also violates the required absence of steps. There is no condition on A(x)A(x)A(x) for x∉Dx\notin Dx∈/D. For D=∅D=\varnothingD=∅ the predicate holds vacuously; if both rule lists are empty, its requirements on the assigned terms reduce to absence of variables.

RestrictedStep. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, and any two lists of rules QQQ and RRR, a restricted step is the least relation on finite terms generated as follows. A rule is h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r with h∉Ch\notin Ch∈/C and every variable of rrr occurring in the arguments; for each rule in RRR and each total assignment σ:N→T\sigma:\mathbb N\to Tσ:N→T of finite terms to variables, the relation goes from h(ℓ0[σ],…,ℓa(h)−1[σ])h(\ell_0[\sigma],\ldots,\ell_{a(h)-1}[\sigma])h(ℓ0​[σ],…,ℓa(h)−1​[σ]) to r[σ]r[\sigma]r[σ] provided that, for every i<a(h)i<a(h)i<a(h), there is no ordinary one-step rewrite from ℓi[σ]\ell_i[\sigma]ℓi​[σ] using QQQ. Substitution replaces variable leaves simultaneously and leaves symbol heads and child order intact; an ordinary rewrite can replace any substituted QQQ-rule instance anywhere inside the tested argument, without any further normality condition. For every symbol fff, term families (tj)j<a(f)(t_j)_{j<a(f)}(tj​)j<a(f)​ and (uj)j<a(f)(u_j)_{j<a(f)}(uj​)j<a(f)​, and i<a(f)i<a(f)i<a(f), a restricted step from tit_iti​ to uiu_iui​ also gives a restricted step between the corresponding fff-applications when tj=ujt_j=u_jtj​=uj​ for all j≠ij\ne ij=i. Accordingly the root condition is checked on the immediate arguments of the rule occurrence being replaced, even when that occurrence lies inside a larger term; the contextual clause adds no normality requirement on its other children. Terms may contain natural-number variables, substitutions are arbitrary total assignments, and the two rule lists are independent. The root condition is vacuous for a nullary rule, is automatic for all arguments when QQQ is empty, and cannot yield a step when RRR is empty. A source and target may coincide.

RelativeStep. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every problem PPP with strict list SSS and weak list WWW, and all finite terms s,ts,ts,t, a relative step from sss to ttt means that there exist finite terms u,vu,vu,v such that sss reaches uuu by a finite sequence of zero or more restricted WWW-steps, uuu makes one restricted SSS-step to vvv, and vvv reaches ttt by a finite sequence of zero or more restricted WWW-steps. Every restricted step uses SSS followed by WWW as its normality-test list: at a chosen position, a rule h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r from the step's designated list is simultaneously instantiated by an arbitrary total assignment of finite terms to natural-number variables, each instantiated argument ℓi\ell_iℓi​ must admit no ordinary one-step replacement anywhere within it by any instantiated rule from either list, and the instantiated left side is replaced by the instantiated right side, retaining the surrounding tree and all other children. All terms are finite arity-respecting symbol trees with natural-number variables; each rule has h∉Ch\notin Ch∈/C and no right-side variable absent from its arguments. For nullary rules the argument condition is vacuous. Either weak sequence may have length zero, allowing u=su=su=s or v=tv=tv=t, but a strict step is required. In particular no relative step exists if SSS is empty, and if WWW is empty this relation is exactly the stated single restricted strict step. The lists may overlap or contain repetitions, and the endpoints may coincide if the required steps exist.

CountedStep. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every problem PPP with strict list SSS and weak list WWW, every natural number KKK, and all finite terms s,ts,ts,t, a counted step of count KKK from sss to ttt is generated by precisely two alternatives: a restricted step using a rule in SSS gives count K=1K=1K=1, and a restricted step using a rule in WWW gives count K=0K=0K=0. In each alternative the normality-test list is the concatenation of SSS and WWW: at any chosen position one simultaneously instantiates a rule h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r by an arbitrary total assignment of finite terms to natural-number variables, requires every instantiated immediate argument to have no ordinary one-step rewrite at any position by any instantiated rule from either list, and replaces the instantiated left side by the right side while retaining its context. Rules have h∉Ch\notin Ch∈/C and no right-side variable absent from their arguments; terms are finite arity-respecting symbol trees with natural-number variable leaves. For a nullary rule the argument requirement is vacuous. No counted step has K≥2K\ge2K≥2, and an empty designated list provides no step of its corresponding kind. The two alternatives need not be disjoint: the same pair of terms can have both counts when both restricted relations hold, including when a usable rule belongs to both lists.

Derivation. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, and every problem PPP with strict list SSS and weak list WWW, the derivation relation associates an initial finite term, a natural-number count, and a final finite term by the following inductive clauses: every term ttt has a derivation from ttt to itself of count zero; and, for all finite terms s,t,us,t,us,t,u and all n,K∈Nn,K\in\mathbb Nn,K∈N, a counted step of count KKK from sss to ttt together with a derivation of count nnn from ttt to uuu gives a derivation of count K+nK+nK+n from sss to uuu. A counted step is one restricted strict-rule step with count one or one restricted weak-rule step with count zero. Such a step uses an arbitrary total substitution of finite terms for natural-number variables in a rule h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r, replaces the instantiated left side by the right side at any position while retaining its context, and requires every instantiated argument to admit no ordinary one-step rewrite using any rule in either list; this argument requirement is vacuous for a nullary rule. Rules have h∉Ch\notin Ch∈/C and every right-side variable occurs in their arguments, and terms are finite arity-respecting symbol trees with natural-number variables. Thus a derivation is a finite sequence of these steps whose count is the sum of its chosen zero-or-one step counts. A zero-count derivation need not be empty: its steps, if present, are weak steps, with no separate bound imposed on their finite number, and its endpoints may differ. The empty sequence always has equal endpoints and count zero. If both lists are empty, only the empty derivations exist. If both step classifications apply to the same pair, either classification can be used in a derivation.

ConstructorLike. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every problem PPP comprising strict and weak lists of rules, and every symbol fff, being constructor-like means that either f∈Cf\in Cf∈C, or there exist a rule h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r in the strict list followed by the weak list and an index i<a(h)i<a(h)i<a(h) such that fff occurs as an application symbol somewhere in the argument term ℓi\ell_iℓi​. Terms are finite trees of natural-number variables and arity-respecting symbol applications, each rule has h∉Ch\notin Ch∈/C and every variable of rrr occurs in its arguments, and a term's symbol occurrences include its application head and recursively all its children's application heads, with variables contributing none. The occurrence may therefore be at the root of ℓi\ell_iℓi​ or at any deeper position. The second alternative tests the actual argument terms of the rule, without substitution, and does not require that the rule can be used in a derivation. A nullary rule supplies no argument index and hence no witness for this alternative. If both lists are empty, the predicate reduces to f∈Cf\in Cf∈C; symbols outside CCC can satisfy it through occurrences in rule arguments.

Supported. For every signature Σ\SigmaΣ with finitely many symbols fff, arities a(f)∈Na(f)\in\mathbb Na(f)∈N, a nonempty constructor set CCC, and at least one symbol of arity zero, every problem PPP with strict and weak rule lists, and every finite term ttt, being supported means both that ttt has no occurrences of natural-number variables and that every symbol occurring as an application head anywhere in ttt either belongs to CCC or occurs as an application head somewhere in an argument of some rule in the concatenation of the strict and weak lists. Each such rule is h(ℓ0,…,ℓa(h)−1)→rh(\ell_0,\ldots,\ell_{a(h)-1})\to rh(ℓ0​,…,ℓa(h)−1​)→r with h∉Ch\notin Ch∈/C and every variable of rrr present in the arguments; all terms are finite trees of applications with their prescribed arities and natural-number variable leaves. More explicitly, for each symbol fff occurring in ttt, the second alternative requires a rule in that concatenated list and an index i<a(h)i<a(h)i<a(h) for which fff occurs at the root of ℓi\ell_iℓi​ or deeper in its tree; the rule and index may depend on fff, and its argument is examined without substitution. Variable terms fail the first conjunct. A nullary application satisfies the first conjunct automatically and is supported exactly when its head satisfies the stated symbol condition. A nullary rule cannot supply a witness through one of its arguments. If both rule lists are empty, supported terms are exactly variable-free terms all of whose application symbols belong to CCC; the signature's existence of some nullary symbol does not require that symbol to belong to CCC.

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