OctoInformBeta

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

Lemma 18: Indexed product tests use system weak normalization in a saturated context tower

Constructing candidates by intersection and application.

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), with arbitrary axiom relation π’œβŠ†S2\mathcal A\subseteq S^2 and product-rule relation β„›βŠ†S3\mathcal R\subseteq S^3.✦ Its term set 𝖳𝗆S\mathsf{Tm}_S consists of variables, sort constants, applications MNM\,N, annotated abstractions Ξ»x:D.b\lambda x:D.b, and dependent products Ξ x:D.E\Pi x:D.E.✦ Named bound variables denote de Bruijn terms, with index zero referring to the nearest binder. Contexts are listed newest first.

Full one-step reduction Mβ†’Ξ²NM\to_\beta N contracts (Ξ»x:D.b)n(\lambda x:D.b)\,n to b[n/x]b[n/x] and permits reduction in every subterm, including annotations and binder bodies.✦ Here b[n/x]b[n/x] is capture-avoiding substitution for the bound variable.✦ Beta convertibility is the least equivalence relation containing β†’Ξ²\to_\beta.✦ The typing judgement Ξ“βŠ’M:A\Gamma\vdash M:A uses π’œ\mathcal A for sort axioms and β„›\mathcal R for product formation, together with the variable, weakening, abstraction, application, and conversion rules; conversion requires the new expected type to have a sort.

A normal term MM is a term with no one-step reduct.✦ A term MM is weakly normalizing if some finite reduction reaches a normal term, and strongly normalizing, written SN(M)\mathrm{SN}(M), if no infinite reduction starts at MM.✦ Write M#M^\# for its chosen normal form when one exists, with a fixed fallback otherwise.✦ A valid context Ξ”\Delta is a context obtained from the empty context by adjoining declarations x:Ax:A with Ξ“βŠ’A:s\Gamma\vdash A:s for some s∈Ss\in S, where Ξ“\Gamma is the context preceding each declaration.✦ 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.✦

A saturated context tower Ξ©=(Ξ“n)nβ‰₯0\Omega=(\Gamma_n)_{n\geq0} is a sequence of valid contexts of length nn, each extended by one declaration whose type has a sort in the preceding context. Every type available at a stage is declared afresh at arbitrarily late stages. Free variables retain their declaration levels across the tower. The tower typing judgement Ω⊒M:A\Omega\vdash M:A holds when Ξ“n⊒M:A\Gamma_n\vdash M:A at some stage, with both the subject and expected type expressed in that prefix’s variables.✦

Candidate Conditions

For a term TT, the set TopT\mathrm{Top}_T of typed strongly normalizing terms at TT is (1): TopT={Mβˆˆπ–³π—†S∣Ω⊒M:TandSN(M)}.\mathrm{Top}_T =\{M\in\mathsf{Tm}_S\mid \Omega\vdash M:T\ \text{and}\ \mathrm{SN}(M)\}.(1) For a finite argument list nβ†’\vec n, write Mnβ†’M\,\vec n for left-associated iterated application, with M[]=MM\,[]=M.✦ Argument list reduction changes exactly one component by one beta step.✦ A strongly normalizing argument list nβ†’\vec n is a finite argument list that admits no infinite sequence of argument list reduction steps, written SNargs(nβ†’)\mathrm{SN}_{\mathrm{args}}(\vec n).✦

A tested stack nβ†’\vec n at TT is a finite argument list generated by the clauses in (2); n::nβ†’n::\vec n denotes adjoining nn at the front of the list: Test⁡T([]),n∈TopDTest⁡(E[n/x])#(nβ†’)Test⁡Ξ x:D.E(n::nβ†’).\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)}.(2) The ground set GTG_T consists of the tower-typed terms that pass every tested stack, as specified in (3): GT={Mβˆˆπ–³π—†S∣Ω⊒M:Tandβˆ€nβ†’,Test⁡T(nβ†’)β‡’SN(Mnβ†’)}.G_T=\{M\in\mathsf{Tm}_S\mid \Omega\vdash M:T\ \text{and}\ \forall\vec n,\ \operatorname{Test}_T(\vec n) \Rightarrow\mathrm{SN}(M\,\vec n)\}.(3)✦

A term set CC is head expansion closed at TT when it contains ((Ξ»x:D.b)n)nβ†’((\lambda x:D.b)\,n)\,\vec n whenever this term has tower type TT, the annotation DD, body bb, and argument nn are strongly normalizing, the argument list nβ†’\vec n is strongly normalizing, and (b[n/x])nβ†’βˆˆC(b[n/x])\,\vec n\in C.✦

Definition 1. The family π’ž(T)\mathcal C(T) of normalization candidates at TT consists of the term sets with the bounds and head expansion closure in (4): π’ž(T)={CβŠ†π–³π—†S∣GTβŠ†CβŠ†TopT,C is head expansion closed at T}.\mathcal C(T)= \{C\subseteq\mathsf{Tm}_S\mid G_T\subseteq C\subseteq\mathrm{Top}_T, \ C\text{ is head expansion closed at }T\}.(4)✦

The bounded intersection 𝖬T(β„±)\mathsf M_T(\mathscr F) of a family β„±\mathscr F of term sets is their intersection restricted to TopT\mathrm{Top}_T, as in (5).✦ The bottom set βŠ₯T\bot_T is the bounded intersection of all normalization candidates at TT, as in (6).✦ 𝖬T(β„±)={M∈TopTβˆ£βˆ€Cβˆˆβ„±,M∈C}.\mathsf M_T(\mathscr F) =\{M\in\mathrm{Top}_T\mid \forall C\in\mathscr F,\ M\in C\}.(5)✦ βŠ₯T=𝖬T(π’ž(T)).\bot_T=\mathsf M_T(\mathcal C(T)).(6)✦

For a product T=Ξ x:D.ET=\Pi x:D.E and an argument nn, put Tn=(E[n/x])#T_n=(E[n/x])^\#. Given an argument set AA and a family β„±n\mathscr F_n of term sets for each nn, the indexed product test 𝖯D,E(A,β„±)\mathsf P_{D,E}(A,\mathscr F) is the set of terms in (7): 𝖯D,E(A,β„±)={h∈TopΞ x:D.Eβˆ£βˆ€n∈Aβˆ€Cβˆˆβ„±n,hn∈C}.\mathsf P_{D,E}(A,\mathscr F) =\{h\in\mathrm{Top}_{\Pi x:D.E}\mid \forall n\in A\ \forall C\in\mathscr F_n,\ h\,n\in C\}.(7)✦

The Claim

Theorem 1. Fix a term TT, and let β„±βŠ†π’ž(T)\mathscr F\subseteq\mathcal C(T) be any family of candidates. Then (8), (9), and (10) hold: 𝖬T(β„±)βˆˆπ’ž(T).\mathsf M_T(\mathscr F)\in\mathcal C(T).(8)✦ TopTβˆˆπ’ž(T).\mathrm{Top}_T\in\mathcal C(T).(9)✦ βŠ₯Tβˆˆπ’ž(T).\bot_T\in\mathcal C(T).(10)✦ Assume that PP is system weakly normalizing. Let AβŠ†TopDA\subseteq\mathrm{Top}_D, and for each n∈An\in A let β„±nβŠ†π’ž(Tn)\mathscr F_n\subseteq\mathcal C(T_n) be any family of candidates. The indexed product test satisfies (11): 𝖯D,E(A,β„±)βˆˆπ’ž(Ξ x:D.E).\mathsf P_{D,E}(A,\mathscr F)\in\mathcal C(\Pi x:D.E).(11)✦

In the paper, the result reads: the inclusion-ordered family π’ž(T)\mathcal C(T) is a complete lattice with largest element TopT\mathrm{Top}_T and least element βŠ₯T\bot_T, and for an actual product T=Ξ x:D.ET=\Pi x:D.E, any AβŠ†TopDA\subseteq\mathrm{Top}_D, and any families Cn,aβˆˆπ’ž(Tn)C_{n,a}\in\mathcal C(T_n) indexed by sets QnQ_n for n∈An\in A, the set {h∈TopTβˆ£βˆ€n∈Aβˆ€a∈Qn,hn∈Cn,a}\{h\in\mathrm{Top}_T\mid\forall n\in A\ \forall a\in Q_n,\ h\,n\in C_{n,a}\} is a candidate at TT.

What Is Checked

The statements concern term sets in a saturated context tower of an arbitrary pure type specification, with system weak normalization required for the indexed product test.