OctoInformBeta

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

Proposition 20: Ground tests and typed strong normalization coincide on source actual types whose profiles lie in the current region

A component interpretation identifies two normalization candidates.

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

For a dependent function, strong normalization of the function is compared with strong normalization after every tested sequence of applications. A component interpretation controls this comparison within a region of sort profiles.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of sorts SS, an arbitrary axiom relation π’œβŠ†S2\mathcal A\subseteq S^2, and an arbitrary product-rule relation β„›βŠ†S3\mathcal R\subseteq S^3.✦ Its terms are variables, sorts, applications MNM\,N, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ The judgement Ξ“βŠ’M:A\Gamma\vdash M:A is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of PP.✦ A valid context is built from the empty context by adjoining x:Ax:A when Ξ“βŠ’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 every term constructor, including annotations and binder bodies.✦ Here b[n/x]b[n/x] is the single-variable substitution instantiating the bound variable, and M[Οƒ]M[\sigma] denotes capture-avoiding simultaneous substitution. Renaming acts on free variables with capture avoided.✦ The equivalence generated by this reduction is Ξ²\beta convertibility, written ≃β\simeq_\beta.✦

A normal term MM is a term with no one-step reduct.✦ A weakly normalizing term MM is a term with a normal reduct, written M#M^\# for its chosen normal form. A strongly normalizing term MM is a term from which no infinite full Ξ²\beta reduction starts; this condition is written 𝖲𝖭(M)\mathsf{SN}(M).✦ A legal term MM in Ξ“\Gamma is a term that occurs as either the subject or the expected type of a typing judgement in Ξ“\Gamma.✦ System weak normalization means that every legal term in every valid context is weakly normalizing.✦ An expected type AA in Ξ“\Gamma is a term that is a literal sort or satisfies Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦

A saturated context tower Ξ©\Omega is a chain of valid contexts Ξ©n\Omega_n of length nn, each extended by a sorted declaration at the next stage. Every type over fixed free levels that is sorted at some stage is declared again beyond every later bound. Tower typing Ω⊒M:A\Omega\vdash M:A means that the subject and expected type admit ordinary typing in some finite prefix, after translating their fixed free levels to that prefix’s newest-first variable indices.✦ Named variables in the formulas denote these terms.

Ground Tests and Candidates

For a term TT, the top candidate Top⁡T\operatorname{Top}_T in Ξ©\Omega is the set of typed strongly normalizing terms defined by (1). Top⁡T={M∣Ω⊒M:Tand𝖲𝖭(M)}.\operatorname{Top}_T =\{M\mid \Omega\vdash M:T\ \text{and}\ \mathsf{SN}(M)\}.(1)✦

Write Mnβ†’M\,\vec n for left-associated iterated application, with M[]=MM\,[]=M.✦ A tested argument stack nβ†’\vec n at TT is a list of terms generated by (2). π–³π–Ύπ—Œπ—T([]),n∈Top⁡Dπ–³π–Ύπ—Œπ—(E[n/x])#(nβ†’)π–³π–Ύπ—Œπ—Ξ x:D.E(n::nβ†’).\mathsf{Test}_T([]), \qquad \frac{n\in\operatorname{Top}_D\qquad \mathsf{Test}_{(E[n/x])^\#}(\vec n)} {\mathsf{Test}_{\Pi x:D.E}(n::\vec n)}.(2) The ground tested-stack candidate GTG_T is the set in (3). GT={M∣Ω⊒M:Tandβˆ€nβ†’,π–³π–Ύπ—Œπ—T(nβ†’)⇒𝖲𝖭(Mnβ†’)}.G_T=\{M\mid \Omega\vdash M:T\ \text{and}\ \forall\vec n,\ \mathsf{Test}_T(\vec n) \Longrightarrow\mathsf{SN}(M\,\vec n)\}.(3)✦

Argument-list reduction is the relation on argument lists in which exactly one argument changes by one full Ξ²\beta step.✦ A strongly normalizing argument list nβ†’\vec n is an argument list that admits no infinite sequence of argument-list reductions; write 𝖲𝖭args(nβ†’)\mathsf{SN}_{\mathrm{args}}(\vec n) for this condition.✦ A set XX of terms is closed under head expansion at TT when it satisfies (4) for every annotation DD, body bb, argument nn, and further argument list nβ†’\vec n. Ω⊒((Ξ»x:D.b)n)nβ†’:T,𝖲𝖭(D),𝖲𝖭(b),𝖲𝖭(n),𝖲𝖭args(nβ†’),b[n/x]nβ†’βˆˆXβ‡’((Ξ»x:D.b)n)nβ†’βˆˆX.\begin{gathered} \Omega\vdash ((\lambda x:D.b)n)\,\vec n:T,\qquad \mathsf{SN}(D),\quad\mathsf{SN}(b),\quad\mathsf{SN}(n),\quad \mathsf{SN}_{\mathrm{args}}(\vec n),\\ b[n/x]\,\vec n\in X \quad\Longrightarrow\quad ((\lambda x:D.b)n)\,\vec n\in X. \end{gathered}(4)✦ A normalization candidate XX at TT is a set with GTβŠ†XβŠ†Top⁡TG_T\subseteq X\subseteq \operatorname{Top}_T that is closed under head expansion at TT.

Profiles and Processed Regions

The normal-form sort profile πΓ(T)\pi_\Gamma(T) and the tower profile πΩ(T)\pi_\Omega(T) are the sets in (5); they retain all possible sort witnesses. πΓ(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\}.(5) A feasible sort profile II is a nonempty set realized as πΓ(T)\pi_\Gamma(T) by a normal term TT in a valid context Ξ“\Gamma.✦ The product output profile Out⁡(I,J)\operatorname{Out}(I,J) of sets of sorts II and JJ is the set of sorts defined by (6). 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\}.(6) 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).✦

The signed primary profile graph has exactly the edges in (7). Iβ†’+JI,J feasible,J⊊I,Iβ†’βˆ’K(I,J,K) a feasible product profile triple,Jβ†’+K(I,J,K) a feasible product profile triple.\begin{array}{lll} I\xrightarrow{+}J &\quad I,J\text{ feasible},&J\subsetneq I,\\ I\xrightarrow{-}K &\quad (I,J,K)\text{ a feasible product profile triple},&\\ J\xrightarrow{+}K &\quad (I,J,K)\text{ a feasible product profile triple}.& \end{array}(7)✦ A signed directed walk is a finite directed walk whose sign is the parity of its number of negative edges; the empty walk is positive.✦ Directed reachability Iβ€³JI\leadsto J means that such a walk exists, with either sign.✦

Fix a current region CβŠ†π’«(S)C\subseteq\mathcal P(S). A source actual type TT is either a normal term with Ω⊒T:s\Omega\vdash T:s for some sort ss, or a literal sort.✦ A processed profile region UU relative to CC is a set of profiles satisfying (8). 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

Assume system weak normalization for PP. A tower-typed raw substitution Οƒ\sigma from Ξ“\Gamma to Ξ©\Omega is an assignment of a term to each context variable that satisfies Ξ©βŠ’Οƒ(x):A[Οƒ]\Omega\vdash\sigma(x):A[\sigma] whenever context lookup assigns xx the type AA, viewed in the full context.✦ A component interpretation for CC assigns to each context Ξ“\Gamma a set Env⁡(Ξ“)\operatorname{Env}(\Gamma) of environments ee with tower-typed image substitutions Οƒe\sigma_e, and represents every tower-typed raw substitution by an environment.

The extension relation Ext⁡(e,eβ€²,n)\operatorname{Ext}(e,e',n) relates an environment over Ξ“\Gamma to one over x:D,Ξ“x:D,\Gamma whose image substitution sends xx to nn and retains the old images. Such an extension exists whenever Ξ“βŠ’D:s\Gamma\vdash D:s and Ω⊒n:D[Οƒe]\Omega\vdash n:D[\sigma_e].

The interpretation ℐ(A,e)\mathcal I(A,e) of an expected type AA is a normalization candidate at (A[Οƒe])#(A[\sigma_e])^\#. Convertible expected types have equal interpretations. The outside law is (9) for every expected type AA. πΓ(A)βˆ‰CorπΩ(A[Οƒe])βˆ‰C⇒ℐ(A,e)=Top⁡(A[Οƒe])#.\pi_\Gamma(A)\notin C\ \text{or}\ \pi_\Omega(A[\sigma_e])\notin C \quad\Longrightarrow\quad \mathcal I(A,e)=\operatorname{Top}_{(A[\sigma_e])^\#}.(9) Weakening preserves ℐ(A,e)\mathcal I(A,e) along Ext⁡(e,eβ€²,n)\operatorname{Ext}(e,e',n) whenever Ξ“βŠ’D:s\Gamma\vdash D:s and AA is expected in Ξ“\Gamma, with AA renamed into the extended context.

For the product laws, put F=Ξ x:D.EF=\Pi x:D.E and Fe=(F[Οƒe])#F_e=(F[\sigma_e])^\#. Both laws apply when Ξ“βŠ’F:s\Gamma\vdash F:s, πΓ(F)∈C\pi_\Gamma(F)\in C, and πΩ(F[Οƒe])∈C\pi_\Omega(F[\sigma_e])\in C. Product introduction is the condition (10), with eβ€²e' ranging over environments on x:D,Ξ“x:D,\Gamma. h∈Top⁡Fe,βˆ€nβˆˆβ„(D,e),βˆ€eβ€²,Ext⁡(e,eβ€²,n)β‡’hnβˆˆβ„(E,eβ€²)β‡’hβˆˆβ„(F,e).\begin{gathered} h\in\operatorname{Top}_{F_e},\qquad \forall n\in\mathcal I(D,e),\ \forall e',\ \operatorname{Ext}(e,e',n)\Longrightarrow h\,n\in\mathcal I(E,e')\\ \Longrightarrow\quad h\in\mathcal I(F,e). \end{gathered}(10) Specialization is (11) for every NN with Ξ“βŠ’N:D\Gamma\vdash N:D. hβˆˆβ„(F,e),N[Οƒe]βˆˆβ„(D,e)β‡’h(N[Οƒe])βˆˆβ„(E[N/x],e).h\in\mathcal I(F,e),\quad N[\sigma_e]\in\mathcal I(D,e) \quad\Longrightarrow\quad h\,(N[\sigma_e])\in\mathcal I(E[N/x],e).(11)

The Claim

Theorem 1. Let PP be a system weakly normalizing pure type specification, let Ξ©\Omega be a saturated context tower, and let a component interpretation for CC be given. For a source actual type TT with πΩ(T)∈C\pi_\Omega(T)\in C, the candidates satisfy (12). GT=Top⁡T.G_T=\operatorname{Top}_T.(12)✦

What Is Checked

The claim is stated over the full Ξ²\beta reduction and typing judgements of an arbitrary pure type specification, a saturated context tower, and a component interpretation under system weak normalization.