OctoInformBeta

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

Lemma 14: Normal terms of sort type, with context conversion, typed renaming and substitution in weakly normalizing systems

Sort profiles obey shape and transport laws.

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 the set of sorts, with an arbitrary axiom relation π’œβŠ†SΓ—S\mathcal A\subseteq S\times S and product-rule relation β„›βŠ†SΓ—SΓ—S\mathcal R\subseteq S\times S\times S.✦ Terms are generated by variables, sort constants, applications MNM\,N, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ A normal form sort profile records every sort that types a term’s chosen normal form.✦

Full one-step Ξ²\beta reduction β†’Ξ²\longrightarrow_\beta on terms is the closure, under all term constructors, of the contraction in (1); this includes reduction in annotations and binder bodies.✦ The bound variable instantiation b[a/x]b[a/x] of a term bb is the term obtained by replacing the bound variable xx by aa, avoiding capture.✦ (Ξ»x:A.b)aβ†’Ξ²b[a/x].(\lambda x:A.b)\,a\longrightarrow_\beta b[a/x].(1) The relation ≑β\equiv_\beta of Ξ²\beta convertibility is the least equivalence relation containing β†’Ξ²\longrightarrow_\beta.✦ A normal term MM is a term with no one-step reduct.✦ A weakly normalizing term MM is a term that reaches a normal term by finitely many Ξ²\beta steps.✦ The chosen normal form T#T^\# is the unique normal form of TT when one exists, with a fixed fallback otherwise.✦ A neutral term MM is a variable or an application whose function is neutral; its argument is unrestricted.✦

A context Ξ“\Gamma is a finite sequence of declarations; Ξ“,x:A\Gamma,x:A extends it by the newest declaration. The typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A is generated by the axiom, variable and weakening rules, dependent product formation using β„›\mathcal R, abstraction, application with bound variable instantiation, and conversion between Ξ²\beta-convertible expected types when the new type has a sort.✦ A valid context Ξ”\Delta is a finite sequence of declarations built from the empty context by adjoining x:Ax:A whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some s∈Ss\in S, where Ξ“\Gamma consists of the preceding declarations.✦

A legal term TT in a context Ξ“\Gamma is a term occurring as either a subject or an expected type in a typing judgement in Ξ“\Gamma.✦ A weakly normalizing specification PP is a pure type specification for which every legal term in every valid context is weakly normalizing, including both MM and AA whenever Ξ“βŠ’M:A\Gamma\vdash M:A.✦

Profiles and Typed Substitutions

The normal form sort profile πΓ(T)\pi_\Gamma(T) of a term TT in a context Ξ“\Gamma is the set of all sorts typing T#T^\# in Ξ“\Gamma, as in (2).✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort s∈Ss\in S is the set of axiom successors of ss.✦ For sets I,JβŠ†SI,J\subseteq S, the product output profile Out⁡(I,J)\operatorname{Out}(I,J) is the set of outputs of rules whose first two sorts belong to II and JJ, respectively.✦ πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}.(2)✦ Ax⁡(s)={t∈S∣(s,t)βˆˆπ’œ},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J,(a,b,c)βˆˆβ„›}.\begin{aligned} \operatorname{Ax}(s)&=\{t\in S\mid(s,t)\in\mathcal A\},\\ \operatorname{Out}(I,J) &=\{c\in S\mid\exists a\in I\;\exists b\in J, \ (a,b,c)\in\mathcal R\}. \end{aligned}(3)

A variable renaming ρ\rho is a map from variables to variables; it acts on terms by replacing free variables by their images, fixing sort constants and respecting binders, and its action is written TρT^\rho.✦ A simultaneous substitution Οƒ\sigma is an assignment of terms to variables that acts recursively, avoiding capture under binders; write its action as T[Οƒ]T[\sigma].✦ Context lookup Ξ“(x)=A\Gamma(x)=A gives the declared type of xx viewed in the full context.✦ A typed simultaneous substitution Οƒ\sigma from a context Ξ“\Gamma to a context Ξ”\Delta is an assignment of terms to variables satisfying (4).✦ Ξ”βŠ’Οƒ(x):A[Οƒ]for every lookup Ξ“(x)=A.\Delta\vdash\sigma(x):A[\sigma] \qquad\text{for every lookup }\Gamma(x)=A.(4)✦

The Claim

Theorem 1. Let MM be normal and suppose Ξ“βŠ’M:s\Gamma\vdash M:s for a sort ss. Then M=t for some t∈S,or M is neutral,or M=Ξ x:A.B for some terms A,B.\begin{gathered} M=t\text{ for some }t\in S,\qquad\text{or }M\text{ is neutral},\\ \text{or }M=\Pi x:A.B\text{ for some terms }A,B. \end{gathered}(5)✦ For every valid context Ξ“\Gamma and sort ss, πΓ(s)=Ax⁡(s).\pi_\Gamma(s)=\operatorname{Ax}(s).(6)✦ If MM is normal and neutral, and Ξ“βŠ’M:s\Gamma\vdash M:s, then πΓ(M)={s}.\pi_\Gamma(M)=\{s\}.(7)✦ For a neutral term MM with Ξ“βŠ’M:s\Gamma\vdash M:s, without a normality assumption, Ax⁡(s)β‰ βŒ€.\operatorname{Ax}(s)\ne\varnothing.(8)✦ When AA and BB are normal, πΓ(Ξ x:A.B)=Out⁡(πΓ(A),πΓ,x:A(B)).\pi_\Gamma(\Pi x:A.B) =\operatorname{Out}\bigl(\pi_\Gamma(A),\pi_{\Gamma,x:A}(B)\bigr).(9)✦ Suppose PP is weakly normalizing, Ξ“βŠ’T:s\Gamma\vdash T:s, and Ξ”\Delta is valid. Let ρ\rho be a variable renaming such that every lookup Ξ“(x)=A\Gamma(x)=A satisfies Ξ”βŠ’Ο(x):Aρ\Delta\vdash\rho(x):A^\rho. Then πΔ(Tρ)=πΓ(T).\pi_\Delta(T^\rho)=\pi_\Gamma(T).(10)✦ Suppose Ξ“βŠ’A:s\Gamma\vdash A:s, Ξ“βŠ’Aβ€²:t\Gamma\vdash A':t, and A≑βAβ€²A\equiv_\beta A'. For every term MM, πΓ,x:A(M)=πΓ,x:Aβ€²(M).\pi_{\Gamma,x:A}(M)=\pi_{\Gamma,x:A'}(M).(11)✦ Suppose PP is weakly normalizing, TT is weakly normalizing, Ξ”\Delta is valid, and Οƒ\sigma is a typed simultaneous substitution from Ξ“\Gamma to Ξ”\Delta. Then πΓ(T)βŠ†Ο€Ξ”(T[Οƒ]).\pi_\Gamma(T)\subseteq\pi_\Delta(T[\sigma]).(12)✦

What Is Checked

The statements concern the typing judgement generated by PP and the normal form profiles of (2), with axiom and product-rule witnesses ranging over the relations in (3).

The library’s laws (10), (11) and (12) concern the renaming action, replacement of the newest declaration, and typed simultaneous substitution of (4), respectively.