OctoInformBeta

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

Actual types, tested stacks, candidates, and the interface: Actual types, processed profiles, and interpretations over typed substitutions

Candidates between normalization and stack tests.

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

A normalization candidate at a type restricts its typed terms by their behavior under application. The tests are finite argument stacks whose successive arguments are strongly normalizing at the domains they encounter. Profile regions organize these candidates, and a component interpretation assigns them to types after substitution.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) with arbitrary axiom and product-rule relations.✦ Its terms form the collection 𝒯\mathcal T generated by variables, sorts s∈Ss\in S, applications MNM\,N, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ We use named binders in formulas; indexed variables are de Bruijn indices, with zero denoting the nearest binder, and finite contexts are written newest first. The typing judgement Γ⊢M:A\Gamma\vdash M:A is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules for PP. A valid context is obtained from the empty context by successive extensions x:A,Γx:A,\Gamma with Γ⊢A:s\Gamma\vdash A:s for some s∈Ss\in S.✦

Full one-step reduction →β\to_\beta contracts (λx:A.b)n(\lambda x:A.b)\,n to b[n/x]b[n/x] and is closed under every term position, including annotations and binder bodies.✦ Convertibility ≡β\equiv_\beta is its equivalence closure.✦ A normal term has no one-step reduct.✦ A weakly normalizing term MM reaches a normal term in finitely many steps; its chosen normal form is denoted M#M^\#. The choice has a fixed fallback for terms without a normal form. Write SN⁡(M)\operatorname{SN}(M) when reduction is well-founded from MM.✦ A term is legal in Γ\Gamma when it occurs as subject or expected type in a typing judgement.✦ System weak normalization requires weak normalization of every legal term in every valid context.✦

Substitutions and Tower Typing

A simultaneous substitution σ:ℕ→𝒯\sigma:\mathbb N\to\mathcal T is a function assigning a term to each free indexed variable; its action extends through every term constructor and lifts under binders to avoid capture.✦ Write A[σ]A[\sigma] for its action. Variable renaming acts in the same way with variable images.✦ The single-variable substitution for nn sends zero to nn and i+1i+1 to the variable ii; its action gives bound-variable instantiation b[n/x]b[n/x]. Substitution extension σ⋅n\sigma\cdot n sends zero to nn and i+1i+1 to σ(i)\sigma(i).✦

A saturated context tower Ω\Omega is a family of valid contexts Ωk\Omega_k of length kk, each extending its predecessor by a type having a sort there. Tower expressions use fixed levels for free names. For a tower expression MM, the term Mˆk\widehat M_k is obtained by the renaming that sends a free level i<ki<k to k−1−ik-1-i and leaves other free indices unchanged, with the renaming lifted under binders. Writing A::ΓA::\Gamma for the extension of Γ\Gamma by a newest declaration of type AA, saturation requires that, whenever Ωk⊢Aˆk:s\Omega_k\vdash\widehat A_k:s, every bound ℓ\ell admits an m≥k,ℓm\geq k,\ell with Ωm+1=Aˆm::Ωm\Omega_{m+1}=\widehat A_m::\Omega_m. Tower typing is the finite-stage judgement in (1). Ω⊢M:A⇔∃kΩk⊢Mˆk:Aˆk.\Omega\vdash M:A \quad\Longleftrightarrow\quad \exists k\;\Omega_k\vdash\widehat M_k:\widehat A_k.(1)✦

Context variable lookup Γ(i)=A\Gamma(i)=A gives the declared type at index ii as viewed in the full context: the newest declaration is shifted once, and passing another declaration shifts the lookup type again.✦ A tower-typed substitution σ:Γ→Ω\sigma:\Gamma\to\Omega is a simultaneous substitution assigning each variable with lookup Γ(i)=A\Gamma(i)=A a term with Ω⊢σ(i):A[σ]\Omega\vdash\sigma(i):A[\sigma].✦ An expected type AA in Γ\Gamma is a term that is a sort constant or satisfies Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

For a term MM and a finite list n‾=(n1,…,nk)\bar n=(n_1,\ldots,n_k), the iterated application Mn‾M\bar n is the term specified by Mn‾=((Mn1)⋯nk)M\bar n=((M\,n_1)\cdots n_k), with M()=MM()=M.✦ An argument list takes one reduction step by reducing one entry.✦ Write SN⁡args(n‾)\operatorname{SN}_{\mathrm{args}}(\bar n) when this list reduction is well-founded from n‾\bar n.✦ A strongly normalizing argument list n‾\bar n is a finite list of terms from which no infinite sequence of argument list reductions starts.

Sort Profiles and Their Predecessors

The normal-form sort profiles πΓ(T)\pi_\Gamma(T) and πΩ(T)\pi_\Omega(T) of a term TT in a context Γ\Gamma and in the tower Ω\Omega are the sets in (2); they retain every sort typing the chosen normal form. πΓ(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\}.(2) A feasible profile I⊆SI\subseteq S is a nonempty set equal to πΓ(T)\pi_\Gamma(T) for some valid context Γ\Gamma and normal term TT. For sets of sorts I,J⊆SI,J\subseteq S, the product output profile Out⁡(I,J)\operatorname{Out}(I,J) is the set of sorts cc with (a,b,c)∈ℛ(a,b,c)\in\mathcal R for some a∈Ia\in I and b∈Jb\in J.✦ 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 primary signed 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 domain edge I→KI\to K and a positive codomain edge J→KJ\to K; these are all its edges. A signed directed walk is a finite sequence of these edges, including the empty walk; its parity is the number of negative edges modulo two.✦ Directed reachability I≼JI\preceq J means that such a walk exists from II to JJ, with either parity.✦

The Definition

Definition 1. For the tower Ω\Omega, an actual type is a term T∈𝒯T\in\mathcal T satisfying (3). Actual⁡(T)⇔(T is normal and ∃s∈SΩ⊢T:s)∨∃s∈ST=s.\operatorname{Actual}(T) \quad\Longleftrightarrow\quad \bigl(T\text{ is normal and }\exists s\in S\;\Omega\vdash T:s\bigr) \ \lor\ \exists s\in S\;T=s.(3)✦ The set Top⁡T\operatorname{Top}_T of typed strongly normalizing terms at TT is defined by (4). Top⁡T={M∈𝒯∣Ω⊢M:T and SN⁡(M)}.\operatorname{Top}_T =\{M\in\mathcal T\mid\Omega\vdash M:T\text{ and }\operatorname{SN}(M)\}.(4)✦ The tested stacks Test⁡T\operatorname{Test}_T are the least family of finite argument lists generated by (5). ()∈Test⁡T,n∈Top⁡Dn‾∈Test⁡(E[n/x])#(n,n‾)∈Test⁡Πx:D.E.()\in\operatorname{Test}_T, \qquad \frac{n\in\operatorname{Top}_D\qquad \bar n\in\operatorname{Test}_{(E[n/x])^\#}} {(n,\bar n)\in\operatorname{Test}_{\Pi x:D.E}}.(5)✦ The ground candidate GTG_T is the set in (6). GT={M∈𝒯∣Ω⊢M:T and ∀n‾∈Test⁡TSN⁡(Mn‾)}.G_T=\{M\in\mathcal T\mid\Omega\vdash M:T \text{ and }\forall\bar n\in\operatorname{Test}_T\; \operatorname{SN}(M\bar n)\}.(6)✦

A set X⊆𝒯X\subseteq\mathcal T is closed under head expansion at TT if it satisfies (7) for every D,b,n,n‾D,b,n,\bar n. Ω⊢((λx:D.b)n)n‾:T,SN⁡(D),SN⁡(b),SN⁡(n),SN⁡args(n‾),(b[n/x])n‾∈X⇒((λx:D.b)n)n‾∈X.\begin{gathered} \Omega\vdash((\lambda x:D.b)\,n)\bar n:T,\qquad \operatorname{SN}(D),\quad\operatorname{SN}(b),\quad\operatorname{SN}(n),\\ \operatorname{SN}_{\mathrm{args}}(\bar n),\qquad (b[n/x])\bar n\in X \quad\Longrightarrow\quad ((\lambda x:D.b)\,n)\bar n\in X. \end{gathered}(7) A normalization candidate XX at TT is a set of terms satisfying (8). GT⊆X⊆Top⁡T,X is head expansion closed at T.G_T\subseteq X\subseteq\operatorname{Top}_T, \qquad X\text{ is head expansion closed at }T.(8)✦

For regions U,𝒞⊆𝒫(S)U,\mathcal C\subseteq\mathcal P(S), UU is processed relative to 𝒞\mathcal C when the conditions in (9) hold for all profiles I,JI,J and all terms TT. U∩𝒞=⌀,J∈U,I≼J⇒I∈U,J∈𝒞,I≼J⇒I∈U∪𝒞,Actual⁡(T),πΩ(T)∈U⇒GT=Top⁡T.\begin{aligned} &U\cap\mathcal C=\varnothing,\\ &J\in U,\ I\preceq J &&\Longrightarrow I\in U,\\ &J\in\mathcal C,\ I\preceq J &&\Longrightarrow I\in U\cup\mathcal C,\\ &\operatorname{Actual}(T),\ \pi_\Omega(T)\in U &&\Longrightarrow G_T=\operatorname{Top}_T. \end{aligned}(9)✦

Suppose PP is system weakly normalizing. A component interface on 𝒞\mathcal C is a family of environment sets Env⁡(Γ)\operatorname{Env}(\Gamma), tower-typed substitutions σe:Γ→Ω\sigma_e:\Gamma\to\Omega for e∈Env⁡(Γ)e\in\operatorname{Env}(\Gamma), an extension relation Ext⁡(e,e′,n)\operatorname{Ext}(e,e',n) for e′∈Env⁡(x:D,Γ)e'\in\operatorname{Env}(x:D,\Gamma) and terms nn, and interpretations RA(e)⊆𝒯R_A(e)\subseteq\mathcal T satisfying the laws in (10). Every tower-typed substitution from Γ\Gamma occurs as some σe\sigma_e. Put Te(A)=(A[σe])#T_e(A)=(A[\sigma_e])^\# and Le(A)⇔πΓ(A)∈𝒞 and πΩ(A[σe])∈𝒞L_e(A)\Longleftrightarrow \pi_\Gamma(A)\in\mathcal C\text{ and }\pi_\Omega(A[\sigma_e])\in\mathcal C. In the conversion and outside laws, A,BA,B are expected types as applicable; the candidate law also requires AA expected. In the weakening law, AA is expected and Γ⊢D:s\Gamma\vdash D:s. Both product laws require Γ⊢Πx:D.E:s\Gamma\vdash\Pi x:D.E:s and Le(Πx:D.E)L_e(\Pi x:D.E); specialization additionally requires Γ⊢N:D\Gamma\vdash N:D. For a term AA, the term A+A^+ is obtained by the renaming that increases every free index of AA by one. All the laws hold for every choice of the displayed terms and environments. Ext⁡(e,e′,n)⇒σe′=σe⋅n,Γ⊢D:s,Ω⊢n:D[σe]⇒∃e′Ext⁡(e,e′,n),RA(e) is a candidate at Te(A),A≡βB⇒RA(e)=RB(e),¬Le(A)⇒RA(e)=Top⁡Te(A),Ext⁡(e,e′,n)⇒RA+(e′)=RA(e),h∈Top⁡Te(Πx:D.E)∀n∈RD(e)∀e′Ext⁡(e,e′,n)⇒hn∈RE(e′)}⇒h∈RΠx:D.E(e),h∈RΠx:D.E(e),N[σe]∈RD(e)⇒h(N[σe])∈RE[N/x](e).\begin{aligned} &\operatorname{Ext}(e,e',n) &&\Longrightarrow\sigma_{e'}=\sigma_e\cdot n,\\ &\Gamma\vdash D:s,\quad\Omega\vdash n:D[\sigma_e] &&\Longrightarrow\exists e'\;\operatorname{Ext}(e,e',n),\\ &R_A(e)\text{ is a candidate at }T_e(A),&&\\ &A\equiv_\beta B &&\Longrightarrow R_A(e)=R_B(e),\\ &\neg L_e(A) &&\Longrightarrow R_A(e)=\operatorname{Top}_{T_e(A)},\\ &\operatorname{Ext}(e,e',n) &&\Longrightarrow R_{A^+}(e')=R_A(e),\\ &\left.\begin{gathered} h\in\operatorname{Top}_{T_e(\Pi x:D.E)}\\ \forall n\in R_D(e)\;\forall e'\; \operatorname{Ext}(e,e',n)\Rightarrow h\,n\in R_E(e') \end{gathered}\right\} &&\Longrightarrow h\in R_{\Pi x:D.E}(e),\\ &h\in R_{\Pi x:D.E}(e),\quad N[\sigma_e]\in R_D(e) &&\Longrightarrow h\,(N[\sigma_e])\in R_{E[N/x]}(e). \end{aligned}(10)✦

What Is Checked

The definitions are stated over an arbitrary pure type specification and a saturated context tower, with system weak normalization assumed for the component interface. Equality of terms is decidable whenever equality of the sorts is decidable.