OctoInformBeta

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

Lemma 16: They agree at literal sorts and contain typed variables; under system weak normalization they are preserved by tested application

Ground candidates refine typed strong normalization.

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

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), where SS is a collection of sorts and π’œβŠ†S2\mathcal A\subseteq S^2 and β„›βŠ†S3\mathcal R\subseteq S^3 are arbitrary relations.✦ Terms over SS are generated by variables, sort constants, application MNM\,N, annotated abstraction Ξ»x:A.M\lambda x:A.M, and dependent product Ξ x:A.B\Pi x:A.B.✦ The displayed names are source notation; bound variables use de Bruijn indices, with zero denoting the nearest binder.

Full one-step Ξ²\beta reduction β†’Ξ²\to_\beta is the relation generated by head contraction (Ξ»x:A.M)Nβ†’Ξ²M[N/x](\lambda x:A.M)\,N\to_\beta M[N/x] and closed under application and under every annotation and binder body of abstractions and products.✦ Capture-avoiding simultaneous substitution replaces free indices by assigned terms, lifting the assignment beneath binders.✦ Bound variable instantiation M[N/x]M[N/x] uses the single variable substitution sending zero to NN and each index i+1i+1 to the variable of index ii.✦ Ξ²\beta convertibility is the smallest equivalence relation containing β†’Ξ²\to_\beta.✦

For a context Ξ“\Gamma of variable declarations and terms MM and AA, the typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A is the least relation generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ An axiom (s,t)βˆˆπ’œ(s,t)\in\mathcal A gives []⊒s:t[]\vdash s:t. Variable introduction declares x:Ax:A, and weakening preserves existing judgements, when Ξ“βŠ’A:s\Gamma\vdash A:s. A product has sort s3s_3 when its domain has sort s1s_1, its codomain has sort s2s_2 in the extended context, and (s1,s2,s3)βˆˆβ„›(s_1,s_2,s_3)\in\mathcal R. Abstraction types the body at the codomain in the extended context and requires the corresponding product to have a sort. Application gives faf\,a type B[a/x]B[a/x] when Ξ“βŠ’f:Ξ x:A.B\Gamma\vdash f:\Pi x:A.B and Ξ“βŠ’a:A\Gamma\vdash a:A. Conversion changes an expected type to a Ξ²\beta convertible type having some sort. A valid context Ξ“\Gamma is a finite newest-first list of variable declarations obtained from the empty context by extensions x:A,Ξ“x:A,\Gamma with Ξ“βŠ’A:s\Gamma\vdash A:s for some s∈Ss\in S.✦

A Ξ²\beta normal term MM is a term having no one-step reduct.✦ A weakly normalizing term MM is a term from which a finite sequence of Ξ²\beta reductions reaches a normal term;✦ a strongly normalizing term MM, written SN⁡(M)\operatorname{SN}(M), is a term from which no infinite sequence of Ξ²\beta reductions starts.✦ A legal term MM in a context Ξ“\Gamma is a term occurring as either the subject or the expected type of a typing judgement.✦ System weak normalization means that every legal term in every valid context is weakly normalizing.✦ Write M#M^\# for the chosen full Ξ²\beta normal form when one exists, with a fixed arbitrary value otherwise.✦

A saturated context tower Ξ©=(Ξ“n)nβˆˆβ„•\Omega=(\Gamma_n)_{n\in\mathbb N} is a family of valid contexts with |Ξ“n|=n|\Gamma_n|=n, each extended to the next by a type having some sort. Its free names are fixed levels, numbered by the order in which declarations enter the tower. Variable renaming by ρ\rho acts on free indices; beneath a binder its lift fixes zero and sends i+1i+1 to ρ(i)+1\rho(i)+1.✦ For nβˆˆβ„•n\in\mathbb N, the reversal rnr_n is the renaming that sends i<ni<n to nβˆ’1βˆ’in-1-i and leaves other indices unchanged.✦ Writing M[rn]M[r_n] for this renaming, tower typing is defined by (1). Ω⊒M:Aβ‡”βˆƒn,Ξ“n⊒M[rn]:A[rn].\Omega\vdash M:A \quad\Longleftrightarrow\quad \exists n,\ \Gamma_n\vdash M[r_n]:A[r_n].(1)✦ Saturation requires that, whenever Ξ“n⊒A[rn]:s\Gamma_n\vdash A[r_n]:s, every bound bb admits mβ‰₯n,bm\geq n,b with Ξ“m+1=A[rm]::Ξ“m\Gamma_{m+1}=A[r_m]::\Gamma_m.

Candidates and Tested Stacks

For a term TT, the top candidate TopT\mathrm{Top}_T is the set of strongly normalizing terms having type TT in Ξ©\Omega, as in (2). TopT={M∣Ω⊒M:TandSN⁡(M)}.\mathrm{Top}_T =\{M\mid \Omega\vdash M:T\ \text{and}\ \operatorname{SN}(M)\}.(2)✦ A tested stack Nβ†’\vec N at a term TT is a finite list generated by (3): the empty list is tested at every TT, and N::Nβ†’N::\vec N is tested at Ξ x:D.E\Pi x:D.E when N∈TopDN\in\mathrm{Top}_D and Nβ†’\vec N is tested at (E[N/x])#(E[N/x])^\#. Test⁡T([])N∈TopDTest⁡(E[N/x])#(Nβ†’)Test⁡Ξ x:D.E(N::Nβ†’).\frac{}{\operatorname{Test}_T([])} \qquad \frac{N\in\mathrm{Top}_D\qquad \operatorname{Test}_{(E[N/x])^\#}(\vec N)} {\operatorname{Test}_{\Pi x:D.E}(N::\vec N)}.(3)✦ For a term MM and a finite list Nβ†’\vec N of terms, iterated application MNβ†’M\,\vec N is the term obtained by applying the arguments in list order, associating to the left, and equals MM for the empty list.✦ The ground candidate GTG_T is the set of terms having type TT that remain strongly normalizing after every tested stack, as in (4). GT={M∣Ω⊒M:Tandβˆ€Nβ†’,Test⁡T(Nβ†’)β‡’SN⁡(MNβ†’)}.G_T=\{M\mid \Omega\vdash M:T\ \text{and}\ \forall\vec N,\ \operatorname{Test}_T(\vec N) \Rightarrow\operatorname{SN}(M\,\vec N)\}.(4)✦

The Claim

Theorem 1. For every term TT, GTβŠ†TopT.G_T\subseteq\mathrm{Top}_T.(5)✦ For every literal sort s∈Ss\in S, Gs=Tops.G_s=\mathrm{Top}_s.(6)✦ For a variable xx satisfying Ω⊒x:T\Omega\vdash x:T, x∈GT.x\in G_T.(7)✦ Suppose PP is weakly normalizing, M∈GΞ x:D.EM\in G_{\Pi x:D.E}, and N∈TopDN\in\mathrm{Top}_D. Then MN∈G(E[N/x])#.M\,N\in G_{(E[N/x])^\#}.(8)✦

What Is Checked

The assertions (5), (6), and (7) are stated over an arbitrary pure type specification and a saturated context tower; (8) additionally assumes system weak normalization. Equality of terms is decidable whenever equality of sorts is decidable.