Theorem 5 — Fixed residual typing can exceed the budget
OpenMoserSchneckenreither.fixed_residual_counterexampleWith rootwise potential, a resource-bounded relative system admits a one-step instance between a typed source and a fixed residual term with normalised substitutions at both ends. The initial substitution satisfies closed-image and printed same-context consistency. For the fixed residual term and substitution there is no residual context, cost, or output annotation that satisfies both full typing and the rootwise resource inequality with charge one.
import Definitions.Def_MoserSchneckenreither_Typing import Definitions.Def_MoserSchneckenreither_RootPotential
namespace MoserSchneckenreither
theorem fixed_residual_counterexample :
∃ (sig : Signature) (P : Problem sig) (F : AnnotatedSignature P) (Γ : Context)
(σ τ : Substitution sig) (t u : Term sig) (p : Annotation) (k : ℚ≥0),
ResourceBounded F ∧ σ.Normalised P ∧ τ.Normalised P ∧ Consistent F σ Γ ∧
(∀ x ∈ σ.domain, ∀ q, (∃ j, Typing F .full Γ j (.var x) q) →
∃ j, Typing F .full Γ j (σ.apply x) q) ∧
Typing F .full Γ k t p ∧ RelativeStep P (t.subst σ.apply) (u.subst τ.apply) ∧
¬ ∃ (Δ : Context) (ℓ : ℚ≥0) (q : Annotation), Typing F .full Δ ℓ u q ∧
rootContextPotential F τ.apply Δ + ℓ + 1 ≤ rootContextPotential F σ.apply Γ + 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 , substitutions , 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. Each of the substitutions consists of a finite domain of variable indices and an assignment of terms to all variable indices. For or , its application 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 chain from to , with the latter formed by recursive substitution using , consisting of zero or more restricted weak steps, one restricted strict step, and zero or more restricted weak steps. To state the final condition, define for every term and annotation by
Here denotes a variable, and a nullary application has an empty argument sum. For a substitution , put , summing once per list entry, with zero for an empty context. This recursion applies to arbitrary terms, including terms with variables. There do not exist a context , a nonnegative rational cost , and an annotation satisfying both and