Canonical-code inversion and strong completeness for pr-models
OpenBergerSchwichtenberg1991V2.completeness_pr_modelsOne effective numbering provides canonical codes for all pr-models. In each such model and at every type, there exists an element whose application to any lambda-definable value returns the code of a closed long -normal form denoting that value. If terms of the same type agree in every environment of a pr-model, they are -convertible.
import Definitions.Def_BergerSchwichtenberg1991V2_Models
namespace BergerSchwichtenberg1991V2
universe u
/-- The inversion and completeness theorems for pr-models (p. 208). One fixed
effective numbering provides the canonical term codes in every model. At each type
the model contains an inverse on λ-definable elements. Equality in every environment
of a pr-model implies βη-convertibility for terms of the same type. -/
theorem completeness_pr_models :
(∃ N : EffectiveNumbering,
∀ (M : PRModel.{u}) (ρ : Ty),
∃ inv : M.Dom (.arr ρ .base),
∀ a : M.Dom ρ, M.IsLambdaDefinable ρ a →
∃ (t : Term) (ht : HasType t ρ),
IsClosed t ∧ IsLongBetaNormal ρ t ∧
M.eqM .base (M.appM inv a) (M.nu (N.natOfTerm t)) ∧
∀ η : M.Env, M.eqM ρ (M.eval ht η) a) ∧
(∀ (M : PRModel.{u}) {ρ : 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)
The claim is a conjunction at a fixed arbitrary universe level for the model domains. First, there exists one effective numbering such that for every primitive-recursive model and every type , there exists a model element . For every that is lambda definable, there exist a raw term and typing derivation at such that is closed and long -normal at , , and for every environment . Here is the term-to-natural-number map of . The choice of is before the quantifier over . Second, for every primitive-recursive model , any type , and any raw terms with typing derivations at that type, if for every environment , then . This second assertion includes 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.
A primitive-recursive model extends a lambda model by a map such that implies . For each binary primitive-recursive map it supplies some model element with for every . The finite-arity primitive-recursive class is generated by the all-zero function at each arity, unary successor, projections of valid coordinates, composition, and recursion on the first input with the step receiving the predecessor, previous value, and remaining inputs.
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.
An effective numbering has bijections between natural numbers and raw terms and between natural numbers and indices, with both inverse equations for each bijection. Write and for the decodings, and for their respective inverse maps, and for the variable of type named by index . The required primitive-recursive operations are
where denotes concatenation and operations with are required for every type . There is also a binary primitive-recursive map with for every raw term .
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.