OctoInformBeta

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

Proposition 22: The least fixed point in the signed candidate order supplies the full component interface

Primary components without odd closed walks admit 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 candidates assigned to a dependent product must account for its domain and its codomain with opposite variances. The primary graph records these dependencies between sort profiles. The construction concerns a strongly connected component of this graph.

A pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) consists of a set of sorts and arbitrary axiom and product-rule relations.✦ A term of the pure type specification PP is an expression generated by variables, sort constants, application, annotated abstraction λx:A.M\lambda x:A.M, and dependent product Πx:A.B\Pi x:A.B.✦ We write named variables for de Bruijn variables and extend contexts on the left, so that their declarations are in newest-first order. The judgement Γ⊢M:A\Gamma\vdash M:A uses the typing rules of PP, including conversion by β\beta convertibility. A valid context Δ\Delta is a finite sequence of declarations built from the empty context by adjoining a type AA to a previously constructed context Γ\Gamma whenever Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

Full reduction →β\to_\beta is the relation on terms that contracts (λx:A.b)n(\lambda x:A.b)\,n to b[n/x]b[n/x] and permits reduction in every annotation and binder body.✦ Convertibility ≡β\equiv_\beta is the equivalence relation on terms generated by full reduction.✦ A normal term MM is a term with no immediate reduct✦; a weakly normalizing term MM is a term that reaches a normal term✦; a strongly normalizing term MM is a term that admits no infinite reduction sequence.✦ For every term MM, write M#M^\# for its chosen full β\beta normal form when one exists, and for a fixed arbitrary term otherwise.✦ A legal term MM in a context Γ\Gamma is a term that occurs as either the subject or the expected type of a typing judgement in Γ\Gamma.✦ System weak normalization of a pure type specification PP is the property that every legal term in every valid context is weakly normalizing.✦ An expected type AA in a context Γ\Gamma is either a literal sort or a term with Γ⊢A:s\Gamma\vdash A:s for some sort ss.✦

A saturated context tower Ω\Omega is a sequence of valid contexts of length nn at stage nn, each extended by one sorted declaration at the next stage, in which every type available at a finite stage is declared again arbitrarily late.✦ Free names are held fixed along the tower. Tower typing Ω⊢M:A\Omega\vdash M:A means that the judgement for both MM and AA holds in some finite prefix, after translating those free names to context indices.✦ The normal form sort profiles are πΓ(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\}.(1) A feasible profile II is a nonempty set of sorts occurring as πΓ(T)\pi_\Gamma(T) in (1) for a normal term TT in a valid context.✦

The product output profile and feasible product triples are specified by Out⁡(I,J)={c∣∃a∈I∃b∈J(a,b,c)∈ℛ},K=Out⁡(I,J),\operatorname{Out}(I,J) =\{c\mid \exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\}, \qquad K=\operatorname{Out}(I,J),(2) A feasible product triple (I,J,K)(I,J,K) is a triple of feasible profiles satisfying (2).✦ The primary graph has a positive edge I→JI\to J for feasible profiles with J⊊IJ\subsetneq I; each triple in (2) gives a negative edge I→KI\to K and a positive edge J→KJ\to K.✦ A signed directed walk has the parity of its number of negative edges, with the empty walk even.✦ Directed reachability from II to JJ means that a signed directed walk from II to JJ exists, with either parity.✦ A strongly connected component CC of the primary graph is the set of vertices mutually reachable with a chosen root r∈Cr\in C.✦ Choose a root-to-II walk for each I∈CI\in C and let ϵ(I)\epsilon(I) be its parity; put ϵ(I)=0\epsilon(I)=0 outside CC.✦

Candidates and the Signed Step

The top set at a tower type TT consists of its typed strongly normalizing terms: 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)✦ A tested argument stack m→\vec m at a tower type TT is the empty list, or a list n::n→n::\vec n at Πx:D.E\Pi x:D.E with n∈TopDn\in\mathrm{Top}_D from (3) and n→\vec n tested at (E[n/x])#(E[n/x])^\#.✦ Write Mn→M\vec n for left-associated iterated application.✦ The ground set and the bounds on a candidate XX at TT are GT={M∣Ω⊢M:T and Mn→ is strongly normalizing for every tested stack n→},GT⊆X⊆TopT.G_T=\{M\mid\Omega\vdash M:T\text{ and } M\vec n\text{ is strongly normalizing for every tested stack }\vec n\}, \qquad G_T\subseteq X\subseteq\mathrm{Top}_T.(4) A normalization candidate XX at a tower type TT is a set satisfying (4) and head expansion closure at TT.✦ A set XX of terms of tower type TT is closed under head expansion if a redex with trailing arguments belongs to XX whenever its contraction belongs to XX, provided the redex with those arguments has tower type TT, its annotation, body and contracted argument are strongly normalizing, and the trailing argument list is strongly normalizing.✦ Argument list reduction reduces one entry by one full β\beta step✦; a strongly normalizing argument list admits no infinite sequence of such reductions.✦

For a domain DD, a codomain EE, a set of arguments AA and a family 𝒳(n)\mathcal X(n) of sets of terms, the indexed product test is PT⁡D,E(A,𝒳)={h∈TopΠx:D.E∣∀n∈A∀X∈𝒳(n)hn∈X}.\operatorname{PT}_{D,E}(A,\mathcal X) =\{h\in\mathrm{Top}_{\Pi x:D.E}\mid \forall n\in A\;\forall X\in\mathcal X(n)\;hn\in X\}.(5)✦ Signed candidates use inclusion for sign 00 and reverse inclusion for sign 11, with the same underlying candidate sets.✦ A signed candidate vector vv is a family assigning a candidate vTv_T to each term TT, ordered with sign ϵ(πΩ(T))\epsilon(\pi_\Omega(T)).✦ The order ≼\preceq on vectors is pointwise in these signed orders. Component lookup is Vv(T)={vT,πΩ(T)∈C,TopT,πΩ(T)∉C.V_v(T)= \begin{cases} v_T,&\pi_\Omega(T)\in C,\\ \mathrm{Top}_T,&\pi_\Omega(T)\notin C. \end{cases}(6)✦ Using (5) and (6), the signed candidate operator FF assigns the following set, with the signed order at TT: F(v)T={PT⁡D,E(Vv(D),n↦{Vv((E[n/x])#)}),T=Πx:D.E is normal,Ω⊢T:s for some s,πΩ(T)∈C,TopT,otherwise.F(v)_T= \begin{cases} \operatorname{PT}_{D,E}\bigl(V_v(D), n\mapsto\{V_v((E[n/x])^\#)\}\bigr), &\begin{array}{l}T=\Pi x:D.E\text{ is normal},\\ \Omega\vdash T:s\text{ for some }s,\quad\pi_\Omega(T)\in C,\end{array}\\ \mathrm{Top}_T,&\text{otherwise}. \end{cases}(7)✦

Environments and the Component Interface

A typed substitution σ:Γ→Ω\sigma:\Gamma\to\Omega is a map assigning a raw term to each context variable x:Ax:A such that Ω⊢σ(x):A[σ]\Omega\vdash\sigma(x):A[\sigma], with AA viewed in the full context by variable lookup.✦ Simultaneous substitution M[σ]M[\sigma] is capture-avoiding, as is bound variable instantiation E[n/x]E[n/x]. Variable renaming acts on free variables and is lifted under binders.✦ The extension σ[x:=n]\sigma[x:=n] of a substitution σ\sigma is the substitution assigning nn to the newest variable and retaining the old images for the remaining variables; in indices it sends 00 to nn and i+1i+1 to σ(i)\sigma(i).✦

The environments Env⁡(Γ)\operatorname{Env}(\Gamma) used here are all typed substitutions from Γ\Gamma into Ω\Omega.✦ For environments ee and e′e', write σe\sigma_e for the images of ee, and Ext⁡(e,e′,n)\operatorname{Ext}(e,e',n) for σe′=σe[x:=n]\sigma_{e'}=\sigma_e[x:=n]. For a least signed fixed point v*v_* of the operator in (7), the actual interpretation 𝒜\mathcal A and its environmental interpretation RR are 𝒜(T)=Vv*(T),R(A,e)={𝒜((A[σe])#),πΓ(A)∈C,Top(A[σe])#,πΓ(A)∉C.\mathcal A(T)=V_{v_*}(T),\qquad R(A,e)= \begin{cases} \mathcal A((A[\sigma_e])^\#),&\pi_\Gamma(A)\in C,\\ \mathrm{Top}_{(A[\sigma_e])^\#},&\pi_\Gamma(A)\notin C. \end{cases}(8)

A component interface ℑ\mathfrak I for (Ω,C)(\Omega,C) is a tuple consisting of environments representing every typed substitution, an extension relation agreeing with substitution extension, and an interpretation of expected types by candidates at their substituted normal forms. Whenever Γ⊢D:s\Gamma\vdash D:s and Ω⊢n:D[σe]\Omega\vdash n:D[\sigma_e], an extension must exist. The interpretation must respect conversion of expected types and weakening along such an extension. Whenever either πΓ(A)\pi_\Gamma(A) or πΩ(A[σe])\pi_\Omega(A[\sigma_e]) lies outside CC, the interpretation must equal Top(A[σe])#\mathrm{Top}_{(A[\sigma_e])^\#}.

The product laws of a component interface apply when Γ⊢Πx:D.E:s\Gamma\vdash\Pi x:D.E:s and 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. If h∈Top((Πx:D.E)[σe])#h\in\mathrm{Top}_{((\Pi x:D.E)[\sigma_e])^\#} and hn∈R(E,e′)hn\in R(E,e') for every n∈R(D,e)n\in R(D,e) and every extension Ext⁡(e,e′,n)\operatorname{Ext}(e,e',n), product introduction puts hh in the product interpretation. If Γ⊢N:D\Gamma\vdash N:D, h∈R(Πx:D.E,e)h\in R(\Pi x:D.E,e) and N[σe]∈R(D,e)N[\sigma_e]\in R(D,e), specialization requires h(N[σe])∈R(E[N/x],e)h(N[\sigma_e])\in R(E[N/x],e). Write CI⁡(Ω,C)\operatorname{CI}(\Omega,C) for the class of component interfaces with these laws.

The Claim

Theorem 1 (Proposition 22). Let PP satisfy system weak normalization, let Ω\Omega be a saturated context tower for PP, and let CC be a strongly connected component of the primary graph with no odd closed walk based at a vertex of CC. For signed vectors v≼wv\preceq w, F(v)≼F(w).F(v)\preceq F(w).(9)✦ The least signed fixed point is v*=lfp⁡(F).v_*=\operatorname{lfp}(F).(10)✦ The environments and interpretation in (8) give a component interface ℑC=(Env⁡,e↦σe,Ext⁡,R)∈CI⁡(Ω,C).\mathfrak I_C= (\operatorname{Env},\ e\mapsto\sigma_e,\ \operatorname{Ext},\ R) \in\operatorname{CI}(\Omega,C).(11)✦

In the paper, the result reads: if CC, denoted SS there, has no odd closed walk, it admits the candidate interface.

What Is Checked

The assertions (9), (10) and (11) are stated over full β\beta reduction and tower typing for a weakly normalizing specification, with signs chosen on a primary component having no odd closed walk. The top set is a normalization candidate at every TT.✦ For the construction in (8), R(A,e)R(A,e) is a candidate even for an arbitrary term AA✦; the outside equality also holds for arbitrary AA whenever πΩ(A[σe])∉C\pi_\Omega(A[\sigma_e])\notin C.✦