OctoInformBeta

OpenAI preprint, September 2026 Β· Β§4. Two component constructions

Proposition 25: When no profile triple lies wholly in the component; product tests use both choices of the new polarity bit

One-child candidates furnish component interpretations.

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

The construction concerns normalization candidates for dependent products in a component of the sort-profile graph, with a polarity attached to each variable. An argument extends both the substitution and the polarity assignment used to interpret a codomain.

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.✦ Variable names are source notation; variables in the library have de Bruijn indices, with zero at the nearest binder, and contexts are newest-first lists. The judgement Ξ“βŠ’M:A\Gamma\vdash M:A is pure type system typing, with the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ Product formation uses triples in β„›\mathcal R; conversion replaces an expected type by a Ξ²\beta-convertible type that itself has a sort. A valid context is obtained from the empty context by extensions D::Ξ“D::\Gamma with Ξ“βŠ’D:s\Gamma\vdash D: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 application, annotations, and both binder bodies.✦ A normal form is a term with no such reduct.✦ Weak normalization means reaching a normal form in finitely many steps✦; strong normalization means that no infinite reduction sequence starts at the term.✦ Conversion =Ξ²=_\beta is the least equivalence relation containing this reduction.✦ A term is legal in Ξ“\Gamma when it occurs as either subject or expected type in a typing judgement.✦ System weak normalization requires every legal term in every valid context to be weakly normalizing.✦ Write M#M^\# for the chosen normal form when one exists, with a fixed fallback otherwise.✦

The normal form sort profile πΓ(T)\pi_\Gamma(T) and product output profile Out⁡(I,J)\operatorname{Out}(I,J) are the sets in (1). πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \operatorname{Out}(I,J)&= \{c\in S\mid \exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\}. \end{aligned}(1) A feasible profile II is a nonempty set of sorts realized as πΓ(T)\pi_\Gamma(T) by a normal term TT in a valid context Ξ“\Gamma.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

The signed primary profile 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. A signed directed walk is a finite walk, allowing repetitions, whose sign is the parity of its negative edges; the empty walk is positive.✦ Directed reachability means the existence of such a walk of either sign.✦ A strongly connected component CC is the set of vertices mutually reachable with some vertex r∈Cr\in C.✦

Tower Candidates and Environments

A saturated context tower Ξ©\Omega is a sequence of valid contexts Ξ“n\Gamma_n of length nn, each extending its predecessor by a type with a sort. Tower terms use fixed levels for free variables. At stage nn, index-to-level reversal sends i<ni<n to nβˆ’1βˆ’in-1-i and fixes other indices; its action by variable renaming translates these free levels to context indices and leaves bound variables fixed. Tower typing Ω⊒M:A\Omega\vdash M:A means that some stage types both translated expressions.✦ Saturation requires that every fixed-level type sorted at a stage nn be declared again at a stage m+1m+1, with mβ‰₯nm\geq n, beyond any prescribed bound. The tower profile πΩ(T)\pi_\Omega(T) of a term TT in the tower Ξ©\Omega is the set of sorts in (2). πΩ(T)={s∈S∣Ω⊒T#:s}.\pi_\Omega(T)=\{s\in S\mid\Omega\vdash T^\#:s\}.(2)✦

The top candidate TopT\mathrm{Top}_T at a tower type TT in Ξ©\Omega is the set in (3). TopT={M∣Ω⊒M:T and M is strongly normalizing}.\mathrm{Top}_T=\{M\mid\Omega\vdash M:T\text{ and }M\text{ is strongly normalizing}\}.(3) Write Mnβ†’M\,\vec n for left-associated iterated application to an argument list.✦ Argument-list reduction reduces exactly one entry by one full Ξ²\beta step✦; an argument list is strongly normalizing when this relation admits no infinite sequence from it.✦ A tested stack at TT is an argument list generated by the empty stack at every type and by n::nβ†’n::\vec n 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])^\#.✦ The ground candidate GTG_T at a tower type TT in Ξ©\Omega is the set in (4). GT={M∣Ω⊒M:T and every tested stack nβ†’ at T makes Mnβ†’ strongly normalizing}.G_T=\{M\mid\Omega\vdash M:T\text{ and every tested stack }\vec n \text{ at }T\text{ makes }M\,\vec n\text{ strongly normalizing}\}.(4) A normalization candidate XX at TT is a set with GTβŠ†XβŠ†TopTG_T\subseteq X\subseteq\mathrm{Top}_T that is closed under head expansion.✦ This closure means that ((Ξ»x:D.b)n)nβ†’((\lambda x:D.b)\,n)\,\vec n belongs to XX whenever it has tower type TT, the terms D,b,nD,b,n and the argument list nβ†’\vec n are strongly normalizing, and b[n/x]nβ†’βˆˆXb[n/x]\,\vec n\in X.✦

A simultaneous substitution Οƒ\sigma is a map from variable indices to terms that acts recursively on terms, with capture avoided under binders.✦ Its lift fixes index zero and sends i+1i+1 to Οƒ(i)\sigma(i) with its free indices increased by one. Single-variable substitution sends zero to nn and i+1i+1 to variable ii; applying it to EE is the bound-variable instantiation E[n/x]E[n/x]. Write A↑A^\uparrow for the variable renaming that increases every free index by one. Context variable lookup reads a declaration’s type in the full context, increasing its free indices once for the declared variable and once for each newer declaration.✦

A typed substitution Οƒ:Ξ“β†’Ξ©\sigma:\Gamma\to\Omega is a substitution satisfying Ξ©βŠ’Οƒ(i):A[Οƒ]\Omega\vdash\sigma(i):A[\sigma] whenever context lookup assigns AA to ii in Ξ“\Gamma.✦ A variable polarity assignment is a map ΞΈ:β„•β†’{0,1}\theta:\mathbb N\to\{0,1\}.✦ An environment e∈Env⁡Ξ©(Ξ“)e\in\operatorname{Env}_\Omega(\Gamma) is a pair (Οƒe,ΞΈe)(\sigma_e,\theta_e) with Οƒe:Ξ“β†’Ξ©\sigma_e:\Gamma\to\Omega typed.✦ Substitution extension Οƒ[n]\sigma[n] and bit extension ΞΈ[b]\theta[b] are defined by (5). Οƒ[n](0)=n,Οƒ[n](i+1)=Οƒ(i),ΞΈ[b](0)=b,ΞΈ[b](i+1)=ΞΈ(i).\begin{aligned} \sigma[n](0)&=n,&\sigma[n](i+1)&=\sigma(i),\\ \theta[b](0)&=b,&\theta[b](i+1)&=\theta(i). \end{aligned}(5) A one-variable environment extension f∈Env⁡Ξ©(D::Ξ“)f\in\operatorname{Env}_\Omega(D::\Gamma) of e∈Env⁡Ξ©(Ξ“)e\in\operatorname{Env}_\Omega(\Gamma) by nn is an environment satisfying (6); its new polarity ΞΈf(0)\theta_f(0) is unrestricted. Ext⁡(e,f,n)quad⇔σf=Οƒe[n]andΞΈf(i+1)=ΞΈe(i)for every i.\operatorname{Ext}(e,f,n)quad\Longleftrightarrow\quad \sigma_f=\sigma_e[n]\quad\text{and}\quad \theta_f(i+1)=\theta_e(i)\ \text{for every }i.(6)✦

The One-child Interpretation

An expected type AA in Ξ“\Gamma is a literal sort or an expression with Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ The recursive one-child interpretation β„°C(Ξ“,A,Οƒ,ΞΈ)\mathcal E_C(\Gamma,A,\sigma,\theta) is a set of tower terms. It takes the top candidate at (A[Οƒ])#(A[\sigma])^\# unless both πΓ(A)\pi_\Gamma(A) and πΩ(A[Οƒ])\pi_\Omega(A[\sigma]) lie in CC. In that active case, a product Ξ x:D.E\Pi x:D.E uses the raw product candidate: its functions belong to Top((Ξ x:D.E)[Οƒ])#\mathrm{Top}_{((\Pi x:D.E)[\sigma])^\#}, and application to each term nn in the recursive domain interpretation must belong to the recursive codomain interpretation under Οƒ[n]\sigma[n] and ΞΈ[b]\theta[b] for each bit bb. For a nonproduct with a variable head, let ii be the index of that head variable. The interpretation then selects Top(A[Οƒ])#\mathrm{Top}_{(A[\sigma])^\#} when ΞΈ(i)=1\theta(i)=1 and the lower candidate Bottom(A[Οƒ])#\mathrm{Bottom}_{(A[\sigma])^\#} when ΞΈ(i)=0\theta(i)=0; with no variable head it selects the top candidate. The normal-form candidate interpretation RC(A,e)R_C(A,e) of an expected type AA in Ξ“\Gamma under an environment e∈Env⁡Ξ©(Ξ“)e\in\operatorname{Env}_\Omega(\Gamma) is the set of tower terms defined in (7). RC(A,e)=β„°C(Ξ“,A#,Οƒe,ΞΈe).R_C(A,e)=\mathcal E_C(\Gamma,A^\#,\sigma_e,\theta_e).(7)✦

A component interpretation ℐ\mathcal I for Ξ©\Omega and CC is a family of environments realizing every typed substitution and admitting an extension by nn whenever Ξ“βŠ’D:s\Gamma\vdash D:s and Ω⊒n:D[Οƒe]\Omega\vdash n:D[\sigma_e], together with an interpretation of expected types by normalization candidates. Its laws are conversion invariance, the top interpretation outside CC, preservation under sorted weakening, product introduction, and specialization to a typed argument. Write CI⁡(Ξ©,C)\operatorname{CI}(\Omega,C) for the class of these interpretations.

The Claim

Theorem 1. Let PP be weakly normalizing, let Ξ©\Omega be a saturated context tower, and let CC be a set of profiles. Suppose Ξ“βŠ’Ξ x:D.E:s\Gamma\vdash\Pi x:D.E:s, let e∈Env⁡Ξ©(Ξ“)e\in\operatorname{Env}_\Omega(\Gamma), and assume that both πΓ(Ξ x:D.E)\pi_\Gamma(\Pi x:D.E) and πΩ((Ξ x:D.E)[Οƒe])\pi_\Omega((\Pi x:D.E)[\sigma_e]) belong to CC. For every term hh, product membership is given by (8). h∈RC(Ξ x:D.E,e)⇔h∈Top((Ξ x:D.E)[Οƒe])#andβˆ€n∈RC(D,e)βˆ€f∈Env⁡Ξ©(D::Ξ“),Ext⁡(e,f,n)β‡’hn∈RC(E,f).\begin{aligned} h\in R_C(\Pi x:D.E,e)\quad\Longleftrightarrow\quad& h\in\mathrm{Top}_{((\Pi x:D.E)[\sigma_e])^\#}\ \text{and}\\ &\forall n\in R_C(D,e)\;\forall f\in\operatorname{Env}_\Omega(D::\Gamma),\\ &\qquad\operatorname{Ext}(e,f,n)\ \Longrightarrow\ h\,n\in R_C(E,f). \end{aligned}(8)✦

Suppose in addition that CC is a strongly connected component of the primary profile graph and no feasible product profile triple has all three entries in CC. The one-child component interpretation is (9). ℐΩ,C=(Env⁡Ξ©,e↦σe,Ext⁡,RC)∈CI⁡(Ξ©,C).\mathcal I_{\Omega,C}= \bigl(\operatorname{Env}_\Omega,\ e\mapsto\sigma_e,\operatorname{Ext},R_C\bigr) \in\operatorname{CI}(\Omega,C).(9)✦ For the product and environment above, suppose Ξ“βŠ’N:D\Gamma\vdash N:D, h∈RC(Ξ x:D.E,e)h\in R_C(\Pi x:D.E,e), and N[Οƒe]∈RC(D,e)N[\sigma_e]\in R_C(D,e). Specialization gives (10). h(N[Οƒe])∈RC(E[N/x],e).h\,(N[\sigma_e])\in R_C(E[N/x],e).(10)✦

In the paper, the result reads: if no profile triple has all three vertices in CC, then the bit-parametrized candidates implement the candidate interface.

What Is Checked

The claims concern full Ξ²\beta reduction in a weakly normalizing pure type system, saturated context towers, and typed substitutions equipped with variable polarities; the component interpretation and specialization also require a primary component with no feasible product profile triple wholly inside it.