Lemma 3 — Substitution preserves typability
OpenMoserSchneckenreither.lemma_4Let be a normalised finite substitution that covers the context , with a closed typing at the assigned annotation for every context entry. If , then admits a closed typing with result annotation and some nonnegative rational cost . This uses closed-image consistency.
import Definitions.Def_MoserSchneckenreither_Typing
namespace MoserSchneckenreither
theorem lemma_4 {sig : Signature} {P : Problem sig} (F : AnnotatedSignature P)
(Γ : Context) (σ : Substitution sig) (hn : σ.Normalised P) (hc : Consistent F σ Γ)
(t : Term sig) (q : Annotation) (k : ℚ≥0) (ht : Typing F .full Γ k t q) :
∃ k' : ℚ≥0, Typing F .full [] k' (t.subst σ.apply) q := by sorry
end MoserSchneckenreither
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex)
Signature. The underlying signature consists of a natural number , symbols , an arity for each symbol , and a nonempty designated set of constructor symbols. At least one symbol has arity zero; that symbol is not required to belong to . In particular the symbol set is nonempty, and individual symbols may have arity zero.
Terms, variables, and renaming. Terms are finite expressions formed from variables indexed by and applications . The list of variable occurrences is for the variable and the concatenation, in argument order, of the lists for an application; repetitions are retained. A term is ground when this list is empty and linear when this list has no repeated entry. For a total map , replaces every variable in by , recursively through applications; this does not recursively apply inside its replacement terms. A renaming by a total map is the substitution sending to the variable . The symbols occurring in a term are all its application labels, including those below its root.
Rules and problems. A rule consists of a head symbol , exactly argument terms , and a right-hand term , with the requirement that each variable occurring in occurs somewhere in . Its left-hand term is this application. The arguments are not required to be constructor terms or to contain distinct variables. A problem consists of finite lists and of such rules, called strict and weak respectively, and its combined rule list is followed by . Either list may be empty, may repeat rules, and may overlap the other list. Let be the set of symbols that either belong to or occur anywhere inside an argument of a rule in either list.
Annotations and declarations. An annotation is a finitely supported function ; addition, multiplication by a nonnegative rational scalar, and comparison are pointwise. The zero annotation is permitted. An arity- declaration is a triple consisting of input annotations, a cost , and an output annotation ; is permitted.
Annotated signature. For the given signature and problem, supplies, for each symbol , a nonempty collection of arity- declarations, and, for every output annotation , input annotations for and a cost . For every and every annotation , the declaration belongs to ; every declaration for such an has for all and . For every and annotations , one has and, for every , . For every , scalar , and annotation , one has and, for every , . The cost equations apply also to nullary symbols. No corresponding uniqueness, addition, or scaling condition is imposed on symbols outside , although their declaration collections must still be nonempty and their functions are still supplied.
Contexts. A context is a finite ordered list of pairs with and an annotation. Its key list is the list of first components, retaining order and repetitions; it is valid exactly when this list has no repeated entry. The empty context is permitted, and arbitrary contexts are not presumed valid. Concatenation of contexts is list concatenation, and a permutation of a context preserves its entries with their multiplicities. All sums over empty lists or empty argument families are zero.
Finite-domain substitutions. A substitution consists of a finite domain and a total assignment . Its effective action is when and the variable otherwise. Write for . No requirement is imposed on the assignment outside , and the domain may be empty.
Rewriting and normality. For a rule list , an ordinary rewrite step replaces an instance of the left-hand side of a rule by , for an arbitrary total variable-to-term map , either at the root or recursively inside one argument of an application while every other argument stays equal. A term is normal for exactly when it has no outgoing ordinary rewrite step using ; this definition does not itself require groundness. A substitution is normalised for exactly when, for every , the assigned term is ground and normal for the combined list followed by . This condition is vacuous for an empty domain; assigned terms are not additionally required to use only designated constructors.
Typing. For the given , write for the least family of relations with mode equal to footprint or full, context , cost , term , and annotation , generated by the following rules. All cost variables in these rules are nonnegative rationals, all annotation variables are finitely supported nonnegative-rational sequences, and all variable names are natural numbers. In either mode, for every symbol , declaration , and pairwise distinct names indexed by , the ordered context types at cost with output ; also for every . For composition, choose a symbol , terms , names , annotations , contexts , and costs for , and a cost and output annotation . If the are pairwise distinct and each is absent from every key list of every , contexts at distinct indices have disjoint sets of keys, the concatenation of the variable-occurrence lists of the has no repetitions, , and for every , then the concatenation types in the same mode at cost with output . For sharing, for every context , pairwise distinct names all absent from its keys, annotations with , term , and cost , a judgment gives , where replaces every variable named or by and leaves all other names unchanged. In either mode, any permutation of the context preserves a judgment with the same cost, term, and output. In full mode there are four additional rules: from and obtain ; from and obtain , with no extra freshness premise in this rule; from and obtain ; and from and a name absent from 's keys obtain for any annotation . The five shared rules keep the same mode in all their premises and conclusion. Nullary symbols, zero costs, and zero annotations are included; argument-index conditions for a nullary symbol are vacuous, its ordered argument context is empty, and its argument-cost sum is zero.
Consistency. For every , substitution , and context , consistency means the conjunction of the following requirements: the keys of have no repetitions, and for every variable name and annotation such that is an entry of , one has and there exists a cost with . The witness may depend on the entry. This definition alone does not require the substitution to be normalised. The empty context is consistent with every substitution.
Lemma 4. For every signature and problem , every annotated signature with all the properties stated above, every context , every substitution normalised for and consistent with , every term , every annotation , and every , if , then there exists such that . The output annotation is the same , while the assertion places no numerical relationship between and . It assumes no resource boundedness condition on . Empty contexts and substitution domains, zero annotations, and zero costs are included whenever the stated premises hold; consistency with an empty context supplies no conditions on entries because there are none.