Theorem 1 — Inversion, normalization, and admissible-model completeness
OpenBergerSchwichtenberg1991V2.theorem_1The inversion term of an admissible model inverts closed denotations and gives closed long normal representatives. In a typed substitution environment it returns an -variant of the result of substituting into a long -normal form of the original term. Equality in all environments entails -convertibility.
import Definitions.Def_BergerSchwichtenberg1991V2_Models
namespace BergerSchwichtenberg1991V2
universe u
/-- Theorem 1. The inversion term of an admissible model inverts closed denotations,
recovers substituted normal forms up to α-equivalence, and reflects semantic validity
of equations to βη-convertibility. -/
theorem theorem_1 (M : AdmissibleModel.{u}) :
(∀ (ρ : Ty) (a : M.Dom ρ),
M.IsLambdaDefinable ρ a →
∃ (t : Term) (ht : HasType t ρ),
M.IsPeResult ρ a t ∧ IsClosed t ∧ IsLongBetaNormal ρ t ∧
∀ η : M.Env, M.eqM ρ (M.eval ht η) a) ∧
(∀ (ρ : Ty) (r : Term) (ht : HasType r ρ) (θ : Substitution),
IsWellTypedSubst θ →
∃ rStar : Term,
HasType rStar ρ ∧ IsLongBetaNormal ρ rStar ∧ BetaEtaEq r rStar ∧
∃ t : Term,
M.IsPeResult ρ (M.eval ht (M.etaSubst θ)) t ∧
AlphaEq t (applySubst θ rStar)) ∧
(∀ {ρ : Ty} {r s : Term} (hr : HasType r ρ) (hs : HasType s ρ),
M.ModelsEq hr hs → BetaEtaEq r s) := 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. The following three assertions hold together.
- For every type and , if is lambda definable then there exist a raw term and a typing derivation of at such that satisfies the partial-evaluation result predicate at , is closed, is long -normal at , and satisfies for every environment .
- For every type , raw term , typing derivation of at , and substitution , if is well typed then there is a raw term of type which is long -normal at and satisfies . For this same there also exists a raw term satisfying the partial-evaluation result predicate at and -equivalent to . This assertion includes open and substitutions with open images. The explicit long-normality condition is on .
- For every type and raw terms with typing derivations at , if in every environment , then .
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.
An element is lambda definable if there exists a raw term with a typing derivation at and no free variables, whose evaluation at the default environment is to . A term is closed precisely when its free-variable list is empty. In this constant-free syntax there are no closed terms of type , so the lambda-definability premise never holds at .
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.
The relation on raw terms is generated by -equivalence, reflexivity, symmetry, transitivity, congruence in both children of an application and under abstractions with the same binder, and the and equations. The equation relates to with substituted for . The substitution replaces at variable leaves, recurses over applications, and stops under a binder equal to . Under a different binder free in it first renames that binder and its occurrences free in the body to a same-typed natural-number-named variable. Its name is one plus the maximum natural-number name among all variable occurrences and binders of the body, , and the variable , using maximum when none occur. It then continues under that renamed binder. A different binder absent from the free variables of is kept during recursion. The equation relates to when is absent from the free variables of . These relation rules are on raw terms.
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 .
The inverse at type is the model element constructed by denoting the lambda term for composing the recoding with . Its application satisfies for each . The partial-evaluation result predicate at is exactly the conjunction that has type and .