Structural Classification of Subterms of `r = nf(t F₁ ... Fₖ α)`
ProvedSchwichtenberg1976.normal_subterm_structurechurch-numeralsdefinabilitylambda-calculuspolynomialstype-theory
In any β-normal term r of type 0 → 0 whose free variables lie in {F₁, ..., Fₖ : ν} ∪ {α : 0 → 0}, every subterm has type 0, 0 → 0, or ν; the only subterms of type ν are the variables Fᵢ; and every subterm of type 0 → 0 belongs to the inductive grammar IsType00Subterm (clauses (1)-(3), p. 114).
Preamble
import Definitions.Def_Schwichtenberg1976_Lambda
Formal statement
namespace Schwichtenberg1976
/-- Structural classification of subterms of a β-normal term `r` of type `0 → 0`
whose free variables are contained in `F₁, ..., Fₖ` (of type `ν`) and `α` (of type `0 → 0`)
(p. 114, lines 3–13):
1. Every well-typed subterm `s` of `r` has type `0`, `0 → 0`, or `ν`.
2. Every subterm `s` of `r` of type `ν` is one of the variables `Fᵢ ∈ Fs`.
3. Every subterm `s` of `r` of type `0 → 0` is generated by clauses (1)–(3)
(`IsType00Subterm Fs α s`). -/
theorem normal_subterm_structure
(Fs : List Var) (α : Var) (r : Term)
(hFs : ∀ F ∈ Fs, F.ty = Ty.nu)
(hα : α.ty = Ty.endo)
(hr_ty : HasType r Ty.endo)
(hr_norm : IsBetaNormal r)
(hr_fv : ∀ v ∈ freeVars r, v ∈ Fs ∨ v = α) :
(∀ s τ, IsSubterm s r → HasType s τ → τ = .zero ∨ τ = Ty.endo ∨ τ = Ty.nu) ∧
(∀ s, IsSubterm s r → HasType s Ty.nu → ∃ F ∈ Fs, s = .var F) ∧
(∀ s, IsSubterm s r → HasType s Ty.endo → IsType00Subterm Fs α s) := by
sorry
end Schwichtenberg1976Source
Helmut Schwichtenberg, 'Definierbare Funktionen im λ-Kalkül mit Typen', Archiv für mathematische Logik und Grundlagenforschung 17, 1975/1976, pp. 113-114 (doi:10.1007/BF02011242). p. 114, lines 3-13.
Read-back
What the Lean code literally says, in plain math · Gemini 3.1 Pro (Independent Blind Auditor)
Mathematical Read-Back: Thm_Schwichtenberg1976_normal_subterm_structure.lean
All declarations below reside in the namespace Schwichtenberg1976 and depend on Definitions.Def_Schwichtenberg1976_Lambda.
1. Theorem Read-Back
normal_subterm_structure (Theorem)
Let be a finite list of typed variables, let be a typed variable, and let be a -term. Assume the following five hypotheses:
- Types of (
hFs): Every variable has the Church numeral type . - Type of (
hα): The variable has the endomorphism type (Ty.endo). - Type of (
hr_ty): The term is well-typed with type (HasType r Ty.endo). - -normality of (
hr_norm): The term is in -normal form (IsBetaNormal r), meaning contains no syntactic subterm of the form . - Free variables of (
hr_fv): Every free variable either belongs to the list or is equal to .
Then the following three structural properties hold simultaneously:
- Subterm type restriction: For every syntactic subterm (
IsSubterm s r, which includes itself and subterms occurring inside the bodies of -abstractions) and every type such that (HasType s τ), is one of the three types
- Classification of subterms of type : For every syntactic subterm such that (
HasType s Ty.nu), there exists a variable such that is the variable term (). - Inductive grammar of subterms of type : For every syntactic subterm such that (
HasType s Ty.endo), belongs to the inductively defined grammarIsType00Subterm Fs α s; that is, is generated by the mutually inductive clauses:- (Clause 1): ;
- (Clause 2): where and satisfies
IsType00Subterm Fs α s'; - (Clause 3): where , , (with either equal to or another variable of type ), and each () is generated by Clauses (1) and (2) (
IsBasicType00 Fs α).
2. Audit Notes: Edge Cases, Degenerate Cases, and Potential Issues
- Uniqueness and inheritability of typing for subterms:
Because every variable carries its intrinsic type directly in syntax and
HasTypehas no external context, every subterm of a well-typed term is automatically well-typed with a unique type . Thus the antecedentHasType s τin the first conjunct is satisfied for a unique for every subterm , andIsSubtermis purely syntactic (passing directly under -binders viaIsSubterm.lamBody). - Scope of variables of type in Clause (3):
In Clause (3) (
IsType00Subterm.chainLam), the inner variable at the base of the application chain is only required by the inductive definitionIsBasicType00Chainto satisfy . Whensis a subterm of located inside nested -abstractions (for example, inside the argument to some ), may be bound by the immediately enclosing () or by an outer of type in . Because and all variables in have types or , itself has no free variables of type ; therefore, for the root subterm itself (when is a -abstraction ), any variable of type not bound inside must equal the outer binder . - Empty list and duplicate elements in :
The theorem does not require to be non-empty or duplicate-free. When , the second conjunct states that has no subterms of type (
∃ F ∈ [], ...is false), and Clause (2) ofIsBasicType00becomes uninhabited, so every basic subterm of type is .