Lemma 5 — Reification of substituted long normal forms
OpenBergerSchwichtenberg1991V2.lemma_5For a well-typed long -normal term and a well-typed substitution, quotation of the value in the substitution environment is the family of the substituted term. At ground type the value itself is the code of the representative selected by extraction.
import Definitions.Def_BergerSchwichtenberg1991V2_Models
namespace BergerSchwichtenberg1991V2
universe u
/-- Lemma 5. Evaluating a long normal term in the environment induced by a typed
substitution and quoting the result gives the family of the substituted term.
At ground type its value is the code of the representative selected by extraction. -/
theorem lemma_5 (M : AdmissibleModel.{u}) {ρ : Ty} {r : Term} (θ : Substitution)
(ht : HasType r ρ) (hnorm : IsLongBetaNormal ρ r) (hθ : IsWellTypedSubst θ) :
M.eqM M.tyF
(M.appM (M.phi ρ) (M.eval ht (M.etaSubst θ)))
(M.appM M.emb (M.codeTerm (applySubst θ r))) ∧
(∀ hbase : ρ = .base,
M.eqM .base
(hbase ▸ M.eval ht (M.etaSubst θ))
(M.codeTerm (EXTRACT (EMB (applySubst θ r))))) := by
sorry
end BergerSchwichtenberg1991V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
Fix any admissible model with domains in an arbitrary universe, any type , any raw term , and any substitution . Assume a typing derivation of at , a proof that is long -normal at , and a proof that is well typed. The claim has both of the following conclusions. First, . Second, for every equality of with , the value transported along into is to . At arrow types this second conclusion is vacuous because the required type equality has no witness. The first conclusion holds at all types with the given hypotheses, including for open terms.
Write for the base type, for the domain at type , and for the model's equivalence on that domain. All types are generated by and arrows. Raw terms are variable occurrences, applications, and abstractions. Variables consist of a type and a name, either a natural-number name or a finite Boolean list called an index. Typing derivations assign variables their specified types, derive type for application of a term of type to a term of type , and derive type for abstraction over a variable of type with body of type . An environment assigns a value in to every variable . In a lambda model there is a default environment and an evaluation given a typing derivation and an environment. The model has application, written by juxtaposition, that respects equivalences of both inputs. Arrow elements are equivalent if all their respective applications to the same arguments are equivalent. Up to model equivalence, evaluation of a variable gives its assigned value, evaluation of an application gives application of the two evaluations, and the application of an evaluated abstraction to a value gives evaluation of its body with the bound variable assigned that value.
The long -normal and neutral predicates are generated together. A variable is neutral at its specified type. An application of a neutral at to a long normal argument at is neutral at . At a neutral is long normal. At an arrow type the long normal constructor is an abstraction whose binder has the domain type and whose body is long normal at the codomain type.
To record bindings in a raw term, start at the empty path, append into the body of an abstraction or the left branch of an application, and append into the right branch. The resulting tree records binder types, the type and path of the nearest matching binder for each bound occurrence, and full variables for free occurrences. Equality of these trees is -equivalence. In , the raw term reconstructed from the tree of at prefix , each binder and its bound occurrences get the indexed name formed by followed by that binder's path. Free variables are kept in full. For a function from indices to terms, , where is the maximum length of all indices attached to variable occurrences and binders in and , with maximum if there are none.
An admissible model extends the lambda model with a family type , an index type , codes for all raw terms and for all indices , and the model elements used in the following laws. For every , for list concatenation . Write for the variable of type with indexed name . For every , . For all raw terms , . For every , . For all , implies as functions, and implies . For every , . For every and , if for every , then .
For family elements define and . The model constructs elements and by recursion on , using denotations of typed lambda terms for the function elements. At the base type and . For , for a step element with, for every ,
For and , .
A substitution assigns a raw term to each variable and is well typed if has type for every . Write for simultaneous substitution. It replaces each variable by and distributes over applications. Under , collect the images under of all free variables of other than . If is free in any collected image, use a binder of the same type with natural-number name one plus the maximum of the natural-number names on all occurrences and binders in , the variable , and every collected image. An empty maximum is . Otherwise set . The substituted abstraction has binder and body . The environment induced by assigns each the element .