Corollary 6 — A normal form can lose its output annotation
OpenMoserSchneckenreither.evaluation_typability_counterexampleThere is a resource-bounded system and a typed initial term with a normalised substitution satisfying closed-image consistency and cost-preserving same-context consistency. The instantiated term evaluates with one strict step to a normal form. The whole-term resource inequality holds with equality, but the normal form has no closed typing at the original output annotation at any cost.
import Definitions.Def_MoserSchneckenreither_Typing
namespace MoserSchneckenreither
theorem evaluation_typability_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 →
Typing F .full Γ j (σ.apply x) p) ∧
Typing F .full Γ k t q ∧ Derivation P (t.subst σ.apply) 1 v ∧ Normal P.rules v ∧
((1 : ℚ≥0) + potential F v q = contextPotential F σ Γ + k) ∧
¬ ∃ j, Typing F .full [] j v q := by sorry
end MoserSchneckenreitherRead-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
There exist a signature, a rule problem , an annotated signature for , a context , a substitution , terms , an annotation and a nonnegative rational as follows. A signature has finitely many symbols with natural-number arities, a nonempty designated set of constructors and at least one arity-zero symbol. Terms are natural-numbered variables or applications with arity-many ordered arguments. The problem consists of two lists of rules, strict and weak, and each rule has a left side with outside the constructor set and a right side whose variables all occur on the left. Annotations are finitely supported sequences of nonnegative rational numbers indexed by , with coordinatewise addition, scaling and order. A context is a finite ordered list of pairs of variable names and annotations. The substitution has a finite domain of natural-numbered variables and a term assignment on all variable names. Write for the assigned term on the domain and the variable outside it. Substitution in a term replaces each variable by its image and acts recursively through applications. The annotated signature specifies a nonempty set of declarations for each symbol, each declaration giving one input annotation per argument, a nonnegative rational cost and an output annotation. It also gives functions and for arity-indexed inputs and cost at each output annotation . For every symbol that is a designated constructor or occurs in a left-side argument of a rule from either list, the declarations with any given output consist exactly of the one with input at each position and cost , and these functions preserve addition and nonnegative rational scaling in . In either footprint or full mode, a typing of a term assigns a context, a nonnegative rational cost and an output annotation, and the typing relation is generated by the following rules. A variable has output at zero cost in the singleton context . An application of a symbol to distinct variables has the input annotations, cost and output of any of the symbol's declarations, with the variable-annotation pairs in argument order. For composition, take a typing of applied to distinct placeholder variables with input annotations given by its context, and typings of the actual arguments with those corresponding outputs, all in the same mode. The placeholders must be absent from all the argument contexts, the argument contexts must have pairwise disjoint sets of names, and no variable may occur more than once in the resulting term. The application then has the concatenation of the argument contexts in argument order, the sum of the placeholder application's cost and all argument costs, and the placeholder application's output. Sharing replaces the last two context pairs by one pair and simultaneously renames and to in the term, keeping all other names fixed, when are pairwise distinct and absent from the preceding context. It preserves cost and output. Context permutation also preserves term, cost and output. Full mode additionally allows increasing the cost, increasing the annotation of the final context pair, decreasing the output annotation, and appending an arbitrary annotation for a variable absent from the context's names. The witnesses satisfy all of the following conditions. First, for every strict rule and every declaration of its head, there exist a context and nonnegative rational costs such that the declaration cost plus equals , and the right side has full typing in at cost with the declaration's output. The same requirement holds for every weak rule and declaration with in place of . In both cases there must exist a list of terms, one for each left-side argument, whose combined variable occurrences are all distinct, and a single renaming function on natural-numbered names sending these terms to the corresponding left-side arguments by recursive variable renaming. Each of those terms must have a footprint typing with output the corresponding input annotation of the declaration, in a context whose list of names is a permutation of the term's list of variable occurrences. The costs of these typings sum to . The context is obtained by concatenating those contexts in argument order, renaming the names with the same renaming function, and keeping the renamed names in order of first occurrence and summing the annotations of all entries with each name. Second, the term assigned to each variable in the domain of has no variable occurrences and is normal for the concatenated list of strict then weak rules. Normality means there is no ordinary one-step rewrite, where an ordinary rewrite replaces an instance of a rule's left side by the corresponding instance of its right side using an arbitrary variable-to-term assignment, at the root or in a single argument recursively with every other argument fixed. Third, the names in are distinct, and for each pair in , is in the domain of and has full typing with empty context, output and some nonnegative rational cost. Fourth, for every in the domain, every annotation and every nonnegative rational , if the variable has full typing with context , cost and output , then has full typing with that very context, cost and output. For any such without the premise typing, the implication holds vacuously. Fifth, has full typing with context , cost and output , and substituting into yields a term from which there is a finite sequence to of restricted rewrite steps with exactly one step counted as strict, each weak step counting zero. A restricted step uses the indicated list of rules, strict for a strict step and weak for a weak step, with the same root and single-argument rules as ordinary rewriting except that the substituted arguments of the left side of the rule instance must each be normal for the combined rule list. The end term is normal for that list. Finally, for a term and annotation define to be zero unless has no variable occurrences and every symbol in it is a designated constructor or occurs in a left-side argument of some rule of . When those conditions hold, is the value of a recursion that assigns zero to a variable and assigns plus the sum of the raw values at arguments with annotations to . The witnesses satisfy , and there is no nonnegative rational for which has full typing with empty context, cost and output . The weak steps may be absent. Strict and weak membership can overlap, and a step using a rule in both lists counts according to whether it is taken as strict or weak. An empty context gives an empty sum in the equality and makes the condition on members of vacuous. The annotation may be zero.