OctoInformBeta

OpenAI preprint, September 2026 Β· Β§6. A typed calculus for the forbidden configuration

Lemma 35: Simultaneous transformations between fixed profile witnesses retain the required shape of proof declarations

Terminal networks preserve converter contexts.

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 proof input at one fixed terminal type may be used to obtain a proof at another. The question is which such transformations can share a valid context whose proof variables have converter types.

A pure type system specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of a set of sorts and arbitrary axiom and product-rule relations.✦ 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.✦ Labelled terms attach one of (𝖽,𝖽)(\mathsf d,\mathsf d), (𝖽,𝗉)(\mathsf d,\mathsf p) and (𝗉,𝗉)(\mathsf p,\mathsf p) to each application, abstraction and product; the two entries are the argument and result modes, with 𝖽\mathsf d denoting data and 𝗉\mathsf p proof. The erasure |M||M| of a labelled term MM is the unlabelled term obtained by deleting its labels.✦ A data-only term is a labelled term with label (𝖽,𝖽)(\mathsf d,\mathsf d) at every labelled constructor.✦

Binder names are source notation; variables have de Bruijn indices and contexts are newest-first lists. Write M[ρ]M[\rho] for capture-avoiding renaming by ρ:β„•β†’β„•\rho:\mathbb N\to\mathbb N, and M[Οƒ]M[\sigma] for simultaneous substitution by an assignment of terms to indices. Under a binder the lifted renaming fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1; the lifted substitution fixes the new variable and shifts each older image. The instantiation b[a]b[a] of a term bb by a term aa is the term obtained by the single-variable substitution sending zero to aa and n+1n+1 to the variable of index nn. These operations preserve labels in labelled syntax. The successor renaming is written M↑M^\uparrow.

Full β\beta reduction contracts (λx:A.b)a(\lambda x:A.b)\,a to b[a]b[a] and is closed under all term components, including annotations and binder bodies.✦ Labelled contraction requires the application and abstraction to have the same label. In either syntax, β\beta convertibility is the equivalence relation generated by this reduction. A normal term is a term with no β\beta-reduct✦; a weakly normalizing term is a term that reaches a normal term in finitely many steps, possibly zero.✦ Write M#M^\# for the chosen full normal form when one exists, with a fixed fallback otherwise.✦

The typing judgment Ξ“βŠ’M:A\Gamma\vdash M:A uses the axiom, variable, weakening, product, abstraction, application and conversion rules of PP. Products use a triple in β„›\mathcal R and sorts for their domain and codomain; abstraction requires the product itself to have a sort. Conversion permits a Ξ²\beta-convertible expected type that has a sort in Ξ“\Gamma. The labelled rules preserve the product label in abstraction and application. A valid context, in either syntax, is a finite context built from the empty context by adjoining a type AA with Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.

Profiles and Terminals

The normal form sort profile πΓ(T)\pi_\Gamma(T) of an unlabelled term TT in a context Ξ“\Gamma is the set in (1).✦ A feasible sort profile II is a nonempty set of sorts equal to πΓ(T)\pi_\Gamma(T) for some valid context Ξ“\Gamma and normal term TT.✦ πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}.(1)✦

The product output profile Out⁡(I,J)\operatorname{Out}(I,J) of sort sets I,JβŠ†SI,J\subseteq S is the set of sorts given in (2). 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).✦ Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J,(a,b,c)βˆˆβ„›}.\operatorname{Out}(I,J) =\{c\in S\mid \exists a\in I\;\exists b\in J,\ (a,b,c)\in\mathcal R\}.(2)✦

The signed primary profile graph has a positive edge Iβ†’JI\to J whenever I,JI,J are feasible and J⊊IJ\subsetneq I. Each feasible product triple (I,J,K)(I,J,K) gives a negative edge Iβ†’KI\to K and a positive edge Jβ†’KJ\to K. A signed directed walk is a finite walk whose sign counts the parity of its negative edges; the empty walk is positive.✦ Directed reachability permits either sign.✦ A strongly connected component CC of the primary profile graph is a set of profiles containing some rr and consisting exactly of the profiles reachable from rr that also reach rr.✦

A logical terminal profile JJ of CC is a profile admitting a feasible product triple with domain and output in CC. Write 𝒯C\mathcal T_C for the set of these profiles, as in (3). 𝒯C={JβŠ†Sβˆ£βˆƒI,K∈C,(I,J,K) is a feasible product profile triple}.\mathcal T_C =\{J\subseteq S\mid \exists I,K\in C,\ (I,J,K) \text{ is a feasible product profile triple}\}.(3)✦

Witnesses and Converter Contexts

A mode environment Ξ³\gamma is a function assigning 𝖽\mathsf d or 𝗉\mathsf p to each variable index. The extension m::Ξ³m::\gamma of a mode environment Ξ³\gamma by a mode mm is the mode environment assigning mm to zero and Ξ³(n)\gamma(n) to n+1n+1.✦ The mode judgment γ⊒mM:m\gamma\vdash_{\mathrm m}M:m assigns a variable its environment mode and a sort data mode. An application has its label’s result mode when its function has that mode and its argument has the argument mode. An abstraction has the result mode when its annotation is data and its body has that result mode under extension by the argument mode. A product has data mode when its domain and codomain have data mode, with the latter checked under that extension.

A fixed feasible witness family W=(TI,vI)W=(T_I,v_I) in (Ξ“,Ξ³)(\Gamma,\gamma) is an assignment of a type and a value to every sort set, satisfying (4) at each feasible profile II.✦ Sorting at II means having every sort in II, and permits additional sorting judgments.✦ TI is data-only,|TI| is normal,Ξ“βŠ’TI:s(s∈I),Ξ“βŠ’vI:TI,γ⊒mTI:𝖽,γ⊒mvI:𝖽.\begin{gathered} T_I\text{ is data-only},\qquad |T_I|\text{ is normal},\qquad \Gamma\vdash T_I:s\quad(s\in I),\qquad \Gamma\vdash v_I:T_I,\\ \gamma\vdash_{\mathrm m}T_I:\mathsf d,\qquad \gamma\vdash_{\mathrm m}v_I:\mathsf d. \end{gathered}(4)

A positive telescope is a labelled term obtained from a data-only term by prefixing zero or more (𝖽,𝗉)(\mathsf d,\mathsf p) products, with arbitrary domains.✦ A normal positive target is a positive telescope whose erasure is normal.✦

Write Ξ“(n)=A\Gamma(n)=A for context lookup, shifting a declaration’s type past its own variable and all newer declarations.✦ A converter proof context (Ξ“,Ξ³)(\Gamma,\gamma) is a context with a mode environment satisfying (5).✦ PC⁡(Ξ“,Ξ³)quadβ‡”βˆ€n,A,(Ξ“(n)=A∧γ(n)=𝗉)β‡’βˆƒR,F,A=Π𝗉,𝗉u:R.F∧R is a normal positive target.\operatorname{PC}(\Gamma,\gamma)quad\Longleftrightarrow\quad \forall n,A,\quad \bigl(\Gamma(n)=A\ \land\ \gamma(n)=\mathsf p\bigr) \ \Longrightarrow\ \exists R,F,\quad A=\Pi^{\mathsf p,\mathsf p}u:R.F \ \land\ R\text{ is a normal positive target}.(5)✦

A mode-preserving context embedding e∈Emb⁡P(Ξ“,Ξ³;Ξ”,Ξ΄)e\in\operatorname{Emb}_P(\Gamma,\gamma;\Delta,\delta) is a renaming e:β„•β†’β„•e:\mathbb N\to\mathbb N into a valid context Ξ”\Delta satisfying (6).✦ Ξ”βŠ’xe(n):A[e]whenever Ξ“(n)=A,Ξ΄(e(n))=Ξ³(n)(nβˆˆβ„•).\begin{gathered} \Delta\vdash x_{e(n)}:A[e]\quad\text{whenever }\Gamma(n)=A,\\ \delta(e(n))=\gamma(n)\quad(n\in\mathbb N). \end{gathered}(6)

A typed open proof transformer tt from AA to BB in (Ξ“,Ξ³)(\Gamma,\gamma) is a term with a temporary proof input of type AA satisfying (7); write Tr⁡Ξ“,Ξ³(A,B)\operatorname{Tr}_{\Gamma,\gamma}(A,B) for its existence. Tr⁡Ξ“,Ξ³(A,B)quadβ‡”βˆƒt,A::Ξ“βŠ’t:Bβ†‘βˆ§(𝗉::Ξ³)⊒mt:𝗉.\operatorname{Tr}_{\Gamma,\gamma}(A,B)quad\Longleftrightarrow\quad \exists t,\quad A::\Gamma\vdash t:B^\uparrow \ \land\ (\mathsf p::\gamma)\vdash_{\mathrm m}t:\mathsf p.(7)✦

For a set QQ of ordered profile pairs, a terminal transfer network (Ξ”,Ξ΄,e)(\Delta,\delta,e) for WW is a triple in the set 𝒩W(Q)\mathcal N_W(Q) defined by (8). 𝒩W(Q)={(Ξ”,Ξ΄,e)∣e∈Emb⁡P(Ξ“,Ξ³;Ξ”,Ξ΄),PC⁡(Ξ”,Ξ΄),Tr⁡Ξ”,Ξ΄(TJ[e],TJβ€²[e]) for every (J,Jβ€²)∈Q}.\begin{split} \mathcal N_W(Q)=\{(\Delta,\delta,e)\mid{}& e\in\operatorname{Emb}_P(\Gamma,\gamma;\Delta,\delta),\quad \operatorname{PC}(\Delta,\delta),\\ &\operatorname{Tr}_{\Delta,\delta}(T_J[e],T_{J'}[e]) \text{ for every }(J,J')\in Q\}. \end{split}(8)

The Claim

Theorem 1. Let CC be a strongly connected component of the primary profile graph. Let Ξ“\Gamma be valid, let PC⁡(Ξ“,Ξ³)\operatorname{PC}(\Gamma,\gamma) hold, and let WW be a fixed feasible witness family in (Ξ“,Ξ³)(\Gamma,\gamma).

If the sort set SS is finite, then 𝒩W(𝒯C×𝒯C)β‰ βŒ€.\mathcal N_W(\mathcal T_C\times\mathcal T_C)\ne\varnothing.(9)✦ For any finite set QβŠ†π’―C×𝒯CQ\subseteq\mathcal T_C\times\mathcal T_C, 𝒩W(Q)β‰ βŒ€.\mathcal N_W(Q)\ne\varnothing.(10)✦ Let (I1,J1,K1)(I_1,J_1,K_1) and (I2,J2,K2)(I_2,J_2,K_2) be feasible product profile triples, with K1∈CK_1\in C and I2∈CI_2\in C. Then 𝒩W({(J1,J2)})β‰ βŒ€.\mathcal N_W(\{(J_1,J_2)\})\ne\varnothing.(11)✦

In the paper, the result reads: there is a finite valid extension Ξ”=Δ𝖽,Δ𝗉\Delta=\Delta_{\mathsf d},\Delta_{\mathsf p} with a proof term Ο„F,Fβ€²(p):Fβ€²\tau_{F,F'}(p):F' in Ξ”,p:F\Delta,p:F for every pair of terminals F,Fβ€²F,F', and every declaration of Δ𝗉\Delta_{\mathsf p} has the form c:Π𝗉,𝗉u:T.FJc:\Pi^{\mathsf p,\mathsf p}u:T.F_J, where FJF_J is a terminal and TT is a normal, constant telescope of (𝖽,𝗉)(\mathsf d,\mathsf p) products ending at a terminal, its suffixes are sorted, and its type contains no free proof variables.

What Is Checked

The statements (9), (10) and (11) concern labelled typing and mode judgments over a fixed feasible witness family, a primary strongly connected component and a valid converter proof context, with finiteness of the sort set assumed in (9).