OctoInformBeta

OpenAI preprint, September 2026 · §3. Sort profiles and normalization candidates

Lemma 19: Under the processed invariant and a component interpretation, at every admissible environment

Strong normalization yields substitution transport.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Substituting terms for the variables of a typed expression changes both the expression and its expected type. A component interpretation assigns candidates to these substituted types, while admissibility prescribes different conditions on variable images according to their sort profiles.

Fix a pure type system specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations.✦ Its terms are variables, sort constants, applications, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Named variables are source notation; contexts are newest-first lists and variables use de Bruijn indices, with zero referring to the nearest binder. The typing judgement Γ⊢M:A\Gamma\vdash M:A is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules. Product formation uses a triple (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R; abstraction requires its product type to have a sort, and conversion requires the new expected type to have a sort. A valid context Γ\Gamma is a context obtained from the empty context by successive extensions x:A,Γx:A,\Gamma with Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

Full one-step β\beta reduction contracts (λx:A.b)n(\lambda x:A.b)\,n to b[n/x]b[n/x] and is closed under all term constructors, including annotations and binder bodies.✦ Its generated equivalence relation is β\beta convertibility, written ≡β\equiv_\beta.✦ A term MM is normal if it has no one-step reduct.✦ Write SN(M)\mathrm{SN}(M) when no infinite reduction starts at MM.✦ A term MM is weakly normalizing if a normal term is reachable from it by finitely many reductions; M#M^\# denotes the chosen normal form when one exists, with a fixed fallback otherwise.✦ A neutral term MM is a term consisting of a variable followed by any finite list of arguments.✦

A legal term MM in a context Γ\Gamma is a term that occurs as either the subject or the expected type of a typing judgement in Γ\Gamma.✦ The pure type system PP is system weakly normalizing if every legal term in every valid context is weakly normalizing; assume this property for PP.✦ An expected type AA in Γ\Gamma is a literal sort or a term satisfying Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

For a term MM and a substitution σ\sigma assigning terms to free indices, the substituted term MσM\sigma is obtained by replacing the free indices of MM by their images under σ\sigma, lifting under binders to avoid capture.✦ For a term MM and a map ρ\rho of indices, the renamed term MρM\rho is obtained by replacing the free indices of MM according to ρ\rho, lifting under binders to avoid capture. The bound variable instance b[n/x]b[n/x] of a term bb by a term nn is the term obtained by the single-variable substitution sending zero to nn and each successor i+1i+1 to the variable ii.✦ The extension (n⋅σ)(n\cdot\sigma) of a substitution σ\sigma by a term nn is the substitution that sends zero to nn and i+1i+1 to σ(i)\sigma(i).✦ Write Mn→M\vec n for left-associated iterated application.✦ Argument list reduction reduces exactly one entry by one β\beta step✦; a strongly normalizing argument list n→\vec n is a list of terms that admits no infinite sequence of argument list reductions.

A saturated context tower Ω=(Γn)n∈ℕ\Omega=(\Gamma_n)_{n\in\mathbb N} is a family of valid contexts of length nn, each extending its predecessor by a type having a sort. For fixed-level free names, let ρn(i)=n−1−i\rho_n(i)=n-1-i when i<ni<n, and ρn(i)=i\rho_n(i)=i otherwise; this is index to level reversal.✦ Saturation requires that whenever Γn⊢Aρn:s\Gamma_n\vdash A\rho_n:s, arbitrarily large stages m≥nm\geq n satisfy Γm+1=Aρm::Γm\Gamma_{m+1}=A\rho_m::\Gamma_m. Bound variables remain de Bruijn indices. The tower typing judgement is defined by (1). Ω⊢M:A⇔∃n,Γn⊢Mρn:Aρn.\Omega\vdash M:A \quad\Longleftrightarrow\quad \exists n,\ \Gamma_n\vdash M\rho_n:A\rho_n.(1)✦

Context variable lookup Γ(i)=B\Gamma(i)=B gives the declared type of index ii as viewed in the full context, shifting free indices once for each intervening extension.✦ A tower typed substitution σ\sigma from Γ\Gamma is an assignment satisfying (2). Γ(i)=B⇒Ω⊢σ(i):Bσ.\Gamma(i)=B\quad\Longrightarrow\quad \Omega\vdash\sigma(i):B\sigma.(2)✦

Candidates and Processed Profiles

The top candidate Top⁡T\operatorname{Top}_T and ground candidate GTG_T at a term TT are the sets of terms in (3), where a tested argument stack at TT is written n→∈Test(T)\vec n\in\mathrm{Test}(T). Top⁡T={M∣Ω⊢M:T,SN(M)},GT={M∣Ω⊢M:T,∀n→∈Test(T),SN(Mn→)}.\begin{aligned} \operatorname{Top}_T &=\{M\mid\Omega\vdash M:T,\ \mathrm{SN}(M)\},\\ G_T &=\{M\mid\Omega\vdash M:T,\ \forall\vec n\in\mathrm{Test}(T),\ \mathrm{SN}(M\vec n)\}. \end{aligned}(3) A tested stack n→\vec n at a term TT is an argument list generated by the clauses in (4). []∈Test(T),n∈Top⁡Dn→∈Test((E[n/x])#)n::n→∈Test(Πx:D.E).[]\in\mathrm{Test}(T),\qquad \frac{n\in\operatorname{Top}_D\qquad \vec n\in\mathrm{Test}\bigl((E[n/x])^\#\bigr)} {n::\vec n\in\mathrm{Test}(\Pi x:D.E)}.(4)✦

A set KK of terms has head expansion closure at TT if, whenever Ω⊢(λx:D.b)nn→:T\Omega\vdash(\lambda x:D.b)\,n\,\vec n:T, the terms D,b,nD,b,n are strongly normalizing, and n→\vec n is a strongly normalizing argument list, the condition in (5) holds.✦ A normalization candidate KK at a term TT is a set of terms with GT⊆K⊆Top⁡TG_T\subseteq K\subseteq\operatorname{Top}_T and head expansion closure at TT.✦ b[n/x]n→∈K⇒(λx:D.b)nn→∈K.b[n/x]\,\vec n\in K \quad\Longrightarrow\quad (\lambda x:D.b)\,n\,\vec n\in K.(5)

The normal-form sort profiles πΓ(T)\pi_\Gamma(T) and πΩ(T)\pi_\Omega(T) of a term TT in a finite context Γ\Gamma and the tower Ω\Omega are the sets of sorts in (6). A source actual type TT is a term that is either a literal sort or a normal term with Ω⊢T:s\Omega\vdash T:s for some sort ss.✦ πΓ(T)={s∈S∣Γ⊢T#:s},πΩ(T)={s∈S∣Ω⊢T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\},\qquad \pi_\Omega(T)=\{s\in S\mid\Omega\vdash T^\#:s\}.(6) A feasible sort profile II is a nonempty set of sorts satisfying I=πΓ(T)I=\pi_\Gamma(T) for some valid context Γ\Gamma and normal term TT. A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J), where the product output profile is given by (7).✦ Out⁡(I,J)={c∈S∣∃a∈I,∃b∈J,(a,b,c)∈ℛ}.\operatorname{Out}(I,J) =\{c\in S\mid\exists a\in I,\ \exists b\in J,\ (a,b,c)\in\mathcal R\}.(7)✦

The signed primary profile graph has a positive edge I→JI\to J for feasible profiles with J⊊IJ\subsetneq I. Each feasible product profile triple (I,J,K)(I,J,K) gives a negative edge I→KI\to K and a positive edge J→KJ\to K. A signed directed walk ww in the primary profile graph is a finite walk, allowing repeated edges, whose sign is the parity of its negative edges; the empty walk is positive.✦ Directed reachability I⤳JI\leadsto J means existence of such a walk of either parity.✦

A processed profile region UU relative to a current region CC is a set of profiles satisfying (8).✦ The last condition is the processed invariant. U∩C=⌀,J∈U,I⤳J⇒I∈U,J∈C,I⤳J⇒I∈U∪C,T a source actual type,πΩ(T)∈U⇒GT=Top⁡T.\begin{gathered} U\cap C=\varnothing,\\ J\in U,\ I\leadsto J\quad\Longrightarrow\quad I\in U,\\ J\in C,\ I\leadsto J\quad\Longrightarrow\quad I\in U\cup C,\\ T\text{ a source actual type},\ \pi_\Omega(T)\in U \quad\Longrightarrow\quad G_T=\operatorname{Top}_T. \end{gathered}(8)

The Component Interpretation

A component interpretation 𝒥\mathcal J for CC assigns to each context Γ\Gamma a family of environments Env(Γ)\mathrm{Env}(\Gamma), with raw images σe(i)\sigma_e(i) for an environment ee. Every σe\sigma_e is a tower typed substitution, and every tower typed substitution from Γ\Gamma is the image assignment of some environment. The extension relation ExtD(e,e′,n)\mathrm{Ext}_D(e,e',n) relates e∈Env(Γ)e\in\mathrm{Env}(\Gamma) to e′∈Env(x:D,Γ)e'\in\mathrm{Env}(x:D,\Gamma) and requires σe′=n⋅σe\sigma_{e'}=n\cdot\sigma_e. Such an extension exists whenever Γ⊢D:s\Gamma\vdash D:s and Ω⊢n:Dσe\Omega\vdash n:D\sigma_e.

The interpretation RΓ,A(e)R_{\Gamma,A}(e) is a set of terms assigned to AA and ee. For an expected type AA, it is a normalization candidate at Ae=(Aσe)#A_e=(A\sigma_e)^\#. Interpretations of β\beta convertible expected types are equal. The outside law is (9), for every expected AA. πΓ(A)∉CorπΩ(Aσe)∉C⇒RΓ,A(e)=Top⁡Ae.\pi_\Gamma(A)\notin C\ \text{or}\ \pi_\Omega(A\sigma_e)\notin C \quad\Longrightarrow\quad R_{\Gamma,A}(e)=\operatorname{Top}_{A_e}.(9) Under an extension ExtD(e,e′,n)\mathrm{Ext}_D(e,e',n) with Γ⊢D:s\Gamma\vdash D:s, the weakening law for an expected type AA is (10); A↑A^\uparrow increases each free index by one. Rx:D,Γ,A↑(e′)=RΓ,A(e).R_{x:D,\Gamma,A^\uparrow}(e')=R_{\Gamma,A}(e).(10)

The product introduction law applies when Γ⊢Πx:D.E:s\Gamma\vdash\Pi x:D.E:s and both πΓ(Πx:D.E)\pi_\Gamma(\Pi x:D.E) and πΩ((Πx:D.E)σe)\pi_\Omega((\Pi x:D.E)\sigma_e) belong to CC. For h∈Top⁡(Πx:D.E)eh\in\operatorname{Top}_{(\Pi x:D.E)_e}, the introduction condition is (11). for every n∈RΓ,D(e) and e′∈Env(x:D,Γ),ExtD(e,e′,n)⇒hn∈Rx:D,Γ,E(e′)⇒h∈RΓ,Πx:D.E(e).\begin{gathered} \text{for every }n\in R_{\Gamma,D}(e)\text{ and } e'\in\mathrm{Env}(x:D,\Gamma),\\ \mathrm{Ext}_D(e,e',n)\Longrightarrow h\,n\in R_{x:D,\Gamma,E}(e') \end{gathered} \quad\Longrightarrow\quad h\in R_{\Gamma,\Pi x:D.E}(e).(11) For the same product typing and profile conditions, specialization requires that if Γ⊢N:D\Gamma\vdash N:D, h∈RΓ,Πx:D.E(e)h\in R_{\Gamma,\Pi x:D.E}(e), and Nσe∈RΓ,D(e)N\sigma_e\in R_{\Gamma,D}(e), then h(Nσe)∈RΓ,E[N/x](e)h\,(N\sigma_e)\in R_{\Gamma,E[N/x]}(e).

An admissible environment e∈Env(Γ)e\in\mathrm{Env}(\Gamma) relative to UU satisfies (12) for every context variable lookup Γ(i)=B\Gamma(i)=B. πΓ(B)∈C⇒σe(i)∈RΓ,B(e),πΓ(B)∈U⇒SN(σe(i)),πΓ(B)∉U∪C⇒σe(i)∈GBe.\begin{aligned} \pi_\Gamma(B)\in C &\quad\Longrightarrow\quad\sigma_e(i)\in R_{\Gamma,B}(e),\\ \pi_\Gamma(B)\in U &\quad\Longrightarrow\quad\mathrm{SN}(\sigma_e(i)),\\ \pi_\Gamma(B)\notin U\cup C &\quad\Longrightarrow\quad\sigma_e(i)\in G_{B_e}. \end{aligned}(12)✦

The transported candidate membership predicate 𝒯Γ,A(M,e)\mathcal T_{\Gamma,A}(M,e) is defined by (13). 𝒯Γ,A(M,e)⇔Mσe∈RΓ,A(e)∧(M neutral,πΓ(A)∉C⇒Mσe∈GAe).\mathcal T_{\Gamma,A}(M,e)\quad\Longleftrightarrow\quad M\sigma_e\in R_{\Gamma,A}(e)\ \land\ \bigl(M\text{ neutral},\ \pi_\Gamma(A)\notin C \Longrightarrow M\sigma_e\in G_{A_e}\bigr).(13)✦ The substitution transport property Trans𝒥,U(M)\mathrm{Trans}_{\mathcal J,U}(M) of a term MM is the condition in (14). Trans𝒥,U(M)⇔for every judgement Γ⊢M:A and every admissiblee∈Env(Γ),𝒯Γ,A(M,e).\mathrm{Trans}_{\mathcal J,U}(M)\quad\Longleftrightarrow\quad \begin{gathered} \text{for every judgement }\Gamma\vdash M:A\text{ and every admissible}\\ e\in\mathrm{Env}(\Gamma),\quad\mathcal T_{\Gamma,A}(M,e). \end{gathered}(14)✦

The Claim

Theorem 1. Let PP be system weakly normalizing, Ω\Omega a saturated context tower, and UU a processed profile region relative to CC. Let 𝒥\mathcal J be a component interpretation for CC. For a strongly normalizing term MM, the substitution transport property is (15). Trans𝒥,U(M).\mathrm{Trans}_{\mathcal J,U}(M).(15)✦

In the paper, the result reads: assuming the processed invariant GT=Top⁡TG_T=\operatorname{Top}_T on UU and an implementation of the three interface requirements of Section 3.3 for the current component CC, if Γ⊢M:A\Gamma\vdash M:A, MM is strongly normalizing, and (ξ,θ)(\xi,\theta) is an admissible environment with raw substitution ξ\xi, then Mξ∈RΓ,A#(ξ,θ)M\xi\in R_{\Gamma,A^\#}(\xi,\theta).

What Is Checked

The statement is over full β\beta reduction and typing for an arbitrary pure type specification, system weak normalization, a saturated context tower, processed profile regions, and a component interpretation with its admissible environments and transport predicate.