Lemma 3 — Admissible expansions of pr-models
OpenBergerSchwichtenberg1991V2.lemma_3One fixed effective numbering of terms and indices works for every pr-model. Each has an admissible expansion using its ground type for both coding types and its numeral injection to encode the fixed numbering.
import Definitions.Def_BergerSchwichtenberg1991V2_Models
namespace BergerSchwichtenberg1991V2
universe u
/-- Lemma 3 with the coding used in its proof. There is one fixed effective numbering
for all pr-models. Each pr-model admits the stated expansion with both code types
at the ground type and its numeral injection giving the codes. -/
theorem lemma_3 :
∃ N : EffectiveNumbering,
∀ M : PRModel.{u},
∃ A : AdmissibleModel.{u},
A.toLambdaModel = M.toLambdaModel ∧
A.tyF = .base ∧ A.tyIdx = .base ∧
(∀ r : Term, HEq (A.codeTerm r) (M.nu (N.natOfTerm r))) ∧
(∀ k : Index, HEq (A.codeIdx k) (M.nu (N.natOfIdx k))) := by
sorry
end BergerSchwichtenberg1991V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
There exists a single effective numbering such that for every primitive-recursive model with domains in a fixed arbitrary universe, there exists an admissible model in that universe with the same underlying lambda-model structure as by literal equality of those structures. Both distinguished types of , the family type and the index type, are the syntactic base type . For every raw term , the term code of in is heterogeneously equal to , where is the term-to-natural-number map of . For every index , the index code of in is heterogeneously equal to , where is the index-to-natural-number map of . These equalities identify the carrier types using the stated structure and type equalities. They are equalities of elements themselves.
Types are generated by and the arrow constructor. Raw terms are typed-variable occurrences, applications, or abstractions, and indices are all finite Boolean lists. A lambda model has a domain and an equivalence for every type, with application respecting both equivalences. Two arrow elements are equivalent if their applications to every common argument are equivalent. It has a default assignment of a value of the specified type to every variable, and evaluation given a typing derivation and any such assignment. Typing gives variables their specified types, applications the result type of the function on an argument of its domain type, and abstractions the arrow from their binder type to their body type. The evaluation equations up to the corresponding equivalences give the assignment value at a variable, model application at an application, and evaluation of the body under the assignment updated at the bound variable when an abstraction is applied to an argument. A primitive-recursive model adds with implying . For each binary primitive-recursive , it has some with for every pair . Primitive recursiveness is generated in finite arities by constant zero, unary successor, projections, composition, and recursion on a first input with the step receiving the predecessor, the previous result, and the remaining inputs.
For a raw term , write for the raw term formed by renaming each binder using the index followed by its path from the root, and carrying that name to occurrences bound by that binder. Paths continue with in abstraction bodies and left application branches and with in right application branches. Binding uses the nearest matching full variable, and free variables are kept in full. For a family , let be evaluated at the all-zero index one bit longer than the longest index among all variable occurrences and binders of and , with maximum when there are none. An effective numbering consists of mutually inverse maps between and raw terms and between and indices. Write and for the decodings and and for their inverses. It requires primitive recursiveness of the coded operations
where is concatenation and is the variable of type with indexed name . The operations that use are required for each . There must also be a binary primitive-recursive such that for every raw term ,
An admissible model extends the lambda model with types , term codes , index codes , and elements , , , , , , and of the arrow types indicated by the following application laws. For all raw terms and indices in these laws, , , , and for each type where it occurs. Equivalent codes imply equal functions , and equal functions imply . Also . For each and raw term , if at every index , then .