Corollary 6 — A numerical failure of the evaluation bound
OpenMoserSchneckenreither.evaluation_bound_counterexampleThere is a resource-bounded system and a typed initial term with a normalised substitution satisfying both closed-image consistency and the printed same-context condition. The instantiated term evaluates with one strict step to a normal form typable at the required annotation. One plus its whole-term potential exceeds the initial context potential plus the initial typing cost.
import Definitions.Def_MoserSchneckenreither_Typing
namespace MoserSchneckenreither
theorem evaluation_bound_counterexample :
∃ (sig : Signature) (P : Problem sig) (F : AnnotatedSignature P) (Γ : Context)
(σ : Substitution sig) (t v : Term sig) (q : Annotation) (k : ℚ≥0),
ResourceBounded F ∧ σ.Normalised P ∧ Consistent F σ Γ ∧
(∀ x ∈ σ.domain, ∀ p, (∃ j, Typing F .full Γ j (.var x) p) →
∃ j, Typing F .full Γ j (σ.apply x) p) ∧
Typing F .full Γ k t q ∧ Derivation P (t.subst σ.apply) 1 v ∧ Normal P.rules v ∧
(∃ j, Typing F .full [] j v q) ∧
¬ ((1 : ℚ≥0) + potential F v q ≤ contextPotential F σ Γ + k) := by sorry
end MoserSchneckenreitherRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
There exist a signature , a problem on , an annotated signature for , a context , a substitution , terms over , an annotation , and a cost with the following properties. The signature has symbols indexed by , a natural-number arity for each symbol, a nonempty designated set of constructors, and at least one symbol of arity zero. Terms are variables indexed by or symbols applied to ordered tuples of terms of their specified arity. The problem consists of a strict list and a weak list of rules. Each rule has a left-hand side with a symbol outside the designated constructor set at its root, a tuple of arguments, and a right-hand side whose variables all occur on the left. Write for the strict list followed by the weak list. A symbol is constructor-like if it is a designated constructor or occurs anywhere within an argument of the left-hand side of a rule in . An annotation is a finitely supported map , with pointwise addition, scalar multiplication, and order. The zero annotation and zero costs are allowed. A context is a list of pairs of a variable index and an annotation. The annotated signature assigns to each symbol a nonempty set of declarations, each with one input annotation per argument position, a nonnegative rational cost, and an output annotation. It also supplies functions and , giving an input annotation at position and a cost for any output annotation . For every constructor-like and every , the declaration with inputs , cost , and output belongs to the set for , and every declaration for with output has those inputs and cost. For constructor-like , each of these input functions and the cost function preserve addition and multiplication by nonnegative rational scalars. Write for a typing of term in context , at cost and output , where is either footprint or full. The typings are those generated by the following rules, using the same mode throughout each derivation. A variable has cost zero and output from the one-entry context . A declaration for types at the declared cost and output from the input-ordered context of pairs of distinct variables and the declared input annotations. To compose a typing of in the input-ordered context with typings of argument terms at outputs , the must be distinct and absent from all the argument contexts, the argument contexts must have pairwise disjoint key sets, and no variable may occur more than once in . The resulting typing of concatenates the argument contexts in input order, adds the head and argument costs, and keeps the head output. If distinct are absent from a context , a typing in followed by gives a typing in followed by at the same cost and output after replacing all occurrences of and in the term by . A typing also permits permutation of the context. Full mode additionally permits replacing the cost by a greater or equal cost, replacing the annotation at the last context entry by a greater or equal annotation, replacing the output annotation by a smaller or equal annotation, or appending a pair with a fresh key and any annotation, each leaving the other data fixed. The resource condition on requires, for every strict rule at charge and every weak rule at charge , the following for every declaration of the rule's head with inputs , cost , and output . There must exist a context , nonnegative rational costs , a tuple of terms with no variable index occurring more than once across the entire tuple, a single renaming which takes to the rule's th argument, and contexts and nonnegative rational costs such that each list of keys of is a permutation of the variable occurrence list of , and holds. The cost is . The context is obtained by concatenating the in input order, renaming their keys by , erasing duplicate renamed keys in the resulting key list, and pairing each remaining key with the sum of all annotations for that renamed key. One must have and , where is this rule's right-hand side. The substitution consists of a finite domain of variable indices and an assignment of terms to all variable indices. Its application, written for a variable , returns the assigned term on its domain and the variable itself elsewhere. The assigned terms on its domain must have no variable occurrences and admit no ordinary one-step rewrite by . An ordinary one-step rewrite replaces an instance of a rule's left-hand side by the corresponding instance of its right-hand side, recursively applying the same arbitrary mapping of variables to terms on both sides to form the instances. This replacement takes place at the root or recursively in one argument of an application with the other arguments fixed. Write for the term that replaces each variable of by . The keys of are pairwise distinct and for every in , the index belongs to the domain of and there exists with . For every in the domain of and every annotation , existence of a with implies existence of some with . This implication has no instances if the domain of is empty, and it holds automatically at any for which there is no indicated typing of . In addition, holds. A restricted step is an ordinary step using the strict list or the weak list as its chosen rule list, with the additional requirement that every instantiated argument of that rule's left-hand side to admit no ordinary one-step rewrite by . Such a step can take place at the root or recursively in one argument of an application with the other arguments fixed. There is a finite derivation from to whose steps are each taken as restricted strict steps with weight one or restricted weak steps with weight zero, and whose total weight is one. Thus the derivation has one step counted as strict and any number of weak steps, including none. The term admits no ordinary one-step rewrite by , and there exists such that . Define on every term and annotation by the recursion
where denotes a variable and a nullary application has an empty argument sum. Define to be if has no variable occurrences and every symbol in it is constructor-like, and zero otherwise. The context potential is , summed once per context entry with zero for an empty context. The following non-strict inequality of nonnegative rationals fails.