OctoInformBeta

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

Modes, terminal converters, formulas, and data wrappers: Labelled formula transformations and fixed paths through feasible sort profiles

Modes and wrappers for a logical calculus.

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 logical calculus for the forbidden configuration uses mode labels on dependent terms and fixed wrappers along paths of sort profiles. Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification, with arbitrary axiom and product-rule relations. Ordinary terms are variables and sorts, applications MNM\,N, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Named binders denote de Bruijn terms, with index zero referring to the nearest binder; contexts are written in newest-first order.

Full β\beta reduction contracts (λx:A.b)a(\lambda x:A.b)\,a to b[a/x]b[a/x], where b[a/x]b[a/x] denotes substitution of aa for the bound variable xx in bb, and is closed under all term constructors, including annotations and binder bodies.✦ Convertibility is its least equivalence closure.✦ A normal term MM is an ordinary term with no β\beta reduct; a weakly normalizing term MM is an ordinary term that reaches a normal term in finitely many steps, possibly none. Write M#M^\# for the chosen full normal form when one exists, with a fixed arbitrary value otherwise.✦

The ordinary typing judgement Γ⊢M:A\Gamma\vdash M:A has the axiom rule []⊢s:t[]\vdash s:t for (s,t)∈𝒜(s,t)\in\mathcal A, and the variable and weakening rules extend Γ\Gamma by AA when Γ⊢A:s\Gamma\vdash A:s for some sort ss, shifting free indices. Product formation requires Γ⊢A:s1\Gamma\vdash A:s_1 and A,Γ⊢B:s2A,\Gamma\vdash B:s_2, with (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R, and gives Γ⊢Πx:A.B:s3\Gamma\vdash\Pi x:A.B:s_3. Abstraction requires a body of type BB in A,ΓA,\Gamma and a sorted product Πx:A.B\Pi x:A.B in Γ\Gamma. If Γ⊢f:Πx:A.B\Gamma\vdash f:\Pi x:A.B and Γ⊢a:A\Gamma\vdash a:A, application gives Γ⊢fa:B[a/x]\Gamma\vdash f\,a:B[a/x]. Conversion changes an expected type to a convertible type that has a sort in Γ\Gamma. A valid context Γ\Gamma is a context obtained from the empty context by successive extensions by a type having a sort in the preceding context.✦

The normal form sort profile πΓ(T)\pi_\Gamma(T) of an ordinary term TT in a context Γ\Gamma, the axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort ss, and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) of sets of sorts I,JI,J are the sets in (1). πΓ(T)={s∈S∣Γ⊢T#:s},Ax⁡(s)={t∈S∣(s,t)∈𝒜},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{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}(1) A feasible profile II is a nonempty set of sorts equal to πΔ(T)\pi_\Delta(T) for some valid context Δ\Delta and normal term TT.✦ Write ℱ(I,J,K)\mathcal F(I,J,K) when all three profiles are feasible and K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

The primary signed graph has positive inclusion edges I→JI\to J between feasible profiles with J⊊IJ\subsetneq I. Each feasible triple ℱ(I,J,K)\mathcal F(I,J,K) gives a negative edge I→KI\to K and a positive edge J→KJ\to K. Positive reachability ⤳+\leadsto_+ is the relation between feasible profiles given by finite paths of positive edges, including empty paths.✦ For a family CC of profiles, the observation layers 𝒪C\mathcal O_C, direct observation layers 𝒟C\mathcal D_C, and logical terminal profiles 𝒯C\mathcal T_C are the sets of profiles specified in (2). 𝒪C={I∣∃s∈S:{s}∈C,Ax⁡(s)≠⌀,Ax⁡(s)⤳+I},𝒟C={I∈𝒪C∣∃J,K∈C:ℱ(I,J,K)},𝒯C={J∣∃I,K∈C:ℱ(I,J,K)}.\begin{aligned} \mathcal O_C&=\{I\mid\exists s\in S:\ \{s\}\in C, \ \operatorname{Ax}(s)\ne\varnothing, \ \operatorname{Ax}(s)\leadsto_+ I\},\\ \mathcal D_C&=\{I\in\mathcal O_C\mid \exists J,K\in C:\ \mathcal F(I,J,K)\},\\ \mathcal T_C&=\{J\mid\exists I,K\in C:\ \mathcal F(I,J,K)\}. \end{aligned}(2)

The Definition

Definition 1. The modes are the elements of the set ℳ\mathcal M in (3). ℳ={𝖽,𝗉},𝖽=data mode,𝗉=proof mode.\mathcal M=\{\mathsf d,\mathsf p\}, \qquad \mathsf d=\text{data mode},\quad \mathsf p=\text{proof mode}.(3)✦ The labels 𝖽𝖽,𝖽𝗉,𝗉𝗉\mathsf{dd},\mathsf{dp},\mathsf{pp} have argument and result modes (𝖽,𝖽)(\mathsf d,\mathsf d), (𝖽,𝗉)(\mathsf d,\mathsf p), and (𝗉,𝗉)(\mathsf p,\mathsf p), respectively; for a label ℓ\ell, write its argument and result modes as dom⁡(ℓ)\operatorname{dom}(\ell) and res⁡(ℓ)\operatorname{res}(\ell). Labelled terms form the least collection ESE_S given by (4), where n∈ℕn\in\mathbb N, s∈Ss\in S, and ℓ\ell is a label. M::=n∣s∣M⋅ℓN∣λℓx:A.M∣Πℓx:A.B.M ::= n\mid s\mid M\mathbin{\cdot_\ell}N \mid\lambda_\ell x:A.M\mid\Pi_\ell x:A.B.(4)✦ The erasure |M||M| of a labelled term M∈ESM\in E_S is the ordinary term obtained by removing all labels from MM. A data-only term M∈ESM\in E_S is a labelled term in which every application, abstraction, and product has label 𝖽𝖽\mathsf{dd}.✦

For a labelled term M∈ESM\in E_S, a renaming ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N, and a simultaneous substitution σ:ℕ→ES\sigma:\mathbb N\to E_S, the terms M[ρ]M[\rho] and M[σ]M[\sigma] are obtained by replacing a variable nn by ρ(n)\rho(n) and σ(n)\sigma(n), respectively, preserving sorts and labels and acting recursively on subterms. Under a binder they use the lifts in (5); M↑M^\uparrow denotes successor renaming. The single substitution σa\sigma_a and bound variable instantiation are also specified there. These operations on ordinary terms have the same clauses with labels omitted. ρ+(0)=0,ρ+(n+1)=ρ(n)+1,σ+(0)=0,σ+(n+1)=σ(n)↑,σa(0)=a,σa(n+1)=n,b[a/x]=b[σa].\begin{gathered} \rho^+(0)=0,\qquad \rho^+(n+1)=\rho(n)+1,\\ \sigma^+(0)=0,\qquad \sigma^+(n+1)=\sigma(n)^\uparrow,\\ \sigma_a(0)=a,\qquad \sigma_a(n+1)=n,\qquad b[a/x]=b[\sigma_a]. \end{gathered}(5) Labelled β\beta reduction is the full congruence closure of (6)✦; labelled convertibility is its least equivalence closure.✦ (λℓx:A.b)⋅ℓa→βb[a/x].(\lambda_\ell x:A.b)\mathbin{\cdot_\ell}a\ \longrightarrow_\beta\ b[a/x].(6) Labelled typing uses the ordinary typing rules, with labels retained; in abstraction and application the label agrees with the product type’s label, and conversion uses labelled convertibility.✦

A mode assignment γ:ℕ→ℳ\gamma:\mathbb N\to\mathcal M assigns modes to free variables. For a mode assignment γ\gamma and a mode m∈ℳm\in\mathcal M, the extension m::γm::\gamma is the mode assignment that sends zero to mm and n+1n+1 to γ(n)\gamma(n).✦ The mode judgement γ⊢mM:m\gamma\vdash_m M:m gives variable nn mode γ(n)\gamma(n) and sorts mode 𝖽\mathsf d. An application labelled ℓ\ell requires its function in mode res⁡(ℓ)\operatorname{res}(\ell) and argument in mode dom⁡(ℓ)\operatorname{dom}(\ell), and has mode res⁡(ℓ)\operatorname{res}(\ell). An abstraction requires its annotation in data mode and its body in result mode under the argument-mode extension, and has result mode. A product requires its domain and body in data mode, with the body under the argument-mode extension, and itself has data mode.

A formula A∈ESA\in E_S is inhabited by a genuine proof when (7) holds. Proves⁡Γ,γ(A)⇔∃p∈ES:Γ⊢p:A∧γ⊢mp:𝗉.\operatorname{Proves}_{\Gamma,\gamma}(A) \quad\Longleftrightarrow\quad \exists p\in E_S:\ \Gamma\vdash p:A \ \land\ \gamma\vdash_m p:\mathsf p.(7)✦ A typed open proof transformer t∈ESt\in E_S from AA to BB in a labelled context Γ\Gamma with mode assignment γ\gamma is a term in the fresh proof variable of type AA satisfying (8). A⇝Γ,γB⇔∃t∈ES:A,Γ⊢t:B↑∧𝗉::γ⊢mt:𝗉.A\rightsquigarrow_{\Gamma,\gamma}B \quad\Longleftrightarrow\quad \exists t\in E_S:\ A,\Gamma\vdash t:B^\uparrow \ \land\ \mathsf p::\gamma\vdash_m t:\mathsf p.(8) Formula equivalence A≃Γ,γBA\simeq_{\Gamma,\gamma}B is the relation between labelled formulas A,B∈ESA,B\in E_S in a labelled context Γ\Gamma with mode assignment γ\gamma that requires uniform typed open proof transformers in both directions, as in (9). A≃Γ,γB⇔A⇝Γ,γB∧B⇝Γ,γA.A\simeq_{\Gamma,\gamma}B \quad\Longleftrightarrow\quad A\rightsquigarrow_{\Gamma,\gamma}B \ \land\ B\rightsquigarrow_{\Gamma,\gamma}A.(9)✦

Sorting a labelled term AA at a profile II means Γ⊢A:s\Gamma\vdash A:s for every s∈Is\in I.✦ A fixed feasible witness family W=(TI,vI)I⊆SW=(T_I,v_I)_{I\subseteq S} in a labelled context Γ\Gamma with mode assignment γ\gamma is a family of pairs of labelled terms, one pair for every profile, satisfying (10) for each feasible profile II. 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),\\ \Gamma\vdash v_I:T_I,\qquad \gamma\vdash_m T_I:\mathsf d,\qquad \gamma\vdash_m v_I:\mathsf d. \end{gathered}(10)✦

A proof wrapper QQ is a finite expression built by identity and signed extensions; a positive data wrapper UU is a finite expression built by identity and paired extensions. Their grammars are (11), with A,a∈ESA,a\in E_S. Q::=𝟏∣pos⁡(Q,A)∣neg⁡(Q,A),U::=𝟏∣step⁡(U,A,a).\begin{aligned} Q&::=\mathbf1\mid\operatorname{pos}(Q,A)\mid\operatorname{neg}(Q,A),\\ U&::=\mathbf1\mid\operatorname{step}(U,A,a). \end{aligned}(11) A data path tail is a tuple τ=(s,U,Qenc,Qdec)\tau=(s,U,Q_{\mathrm{enc}},Q_{\mathrm{dec}}) with s∈Ss\in S, a positive data wrapper UU, and proof wrappers Qenc,QdecQ_{\mathrm{enc}},Q_{\mathrm{dec}}.✦ Retained data wrappers form the least family 𝒲ϵ\mathcal W_\epsilon, indexed by parity ϵ∈{0,1}\epsilon\in\{0,1\}, with the constructors in (12); here A,a∈ESA,a\in E_S and τ\tau is a data path tail. 𝟏∈𝒲0D∈𝒲ϵpos⁡(D,A,a)∈𝒲ϵD∈𝒲ϵneg⁡(D,τ)∈𝒲1−ϵ.\frac{}{\mathbf1\in\mathcal W_0} \qquad \frac{D\in\mathcal W_\epsilon} {\operatorname{pos}(D,A,a)\in\mathcal W_\epsilon} \qquad \frac{D\in\mathcal W_\epsilon} {\operatorname{neg}(D,\tau)\in\mathcal W_{1-\epsilon}}.(12)✦

For a witness family WW, formation of a proof wrapper from II to JJ with parity ϵ\epsilon is written $Q:I\xRightarrow[W,C]{\epsilon}J$ and is the least relation closed under (13). Parity counts negative extensions modulo two. $$\begin{gathered} \frac{}{\mathbf1:I\xRightarrow[W,C]{0}I},\qquad \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad K\subseteq J} {Q:I\xRightarrow[W,C]{\epsilon}K},\\[3pt] \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad\mathcal F(H,J,K)} {\operatorname{pos}(Q,T_H):I\xRightarrow[W,C]{\epsilon}K},\\[3pt] \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad\mathcal F(J,H,K)\quad J,K\in C} {\operatorname{neg}(Q,T_H):I\xRightarrow[W,C]{1-\epsilon}K}. \end{gathered}$$(13)✦ A quantifier route rr through a profile II at base profile bb is a tuple of profiles J,KJ,K and proof wrappers Qin,QoutQ_{\mathrm{in}},Q_{\mathrm{out}} satisfying (14). Write 𝒬W,C(b,I)\mathcal Q_{W,C}(b,I) for the collection of these routes. $$\mathcal F(I,J,K),\qquad Q_{\mathrm{in}}:b\xRightarrow[W,C]{0}J,\qquad Q_{\mathrm{out}}:K\xRightarrow[W,C]{0}b.$$(14)✦

An ambient logical setup for P,Γ,γ,CP,\Gamma,\gamma,C consists of a witness family WW, terminal converters given by typed open proof transformers from TJT_J to TJ′T_{J'} for all J,J′∈𝒯CJ,J'\in\mathcal T_C, profiles b,d,kb,d,k, proof wrappers Qin,QoutQ_{\mathrm{in}},Q_{\mathrm{out}}, and a quantifier route rIr_I for each direct observation layer II, subject to (15). $$\begin{gathered} T_J\rightsquigarrow_{\Gamma,\gamma}T_{J'} \quad(J,J'\in\mathcal T_C),\\ b,d,k\in C,\qquad\mathcal F(d,b,k),\\ Q_{\mathrm{in}}:b\xRightarrow[W,C]{0}d,\qquad Q_{\mathrm{out}}:k\xRightarrow[W,C]{0}b,\\ r_I\in\mathcal Q_{W,C}(b,I)\quad(I\in\mathcal D_C). \end{gathered}$$(15)✦

What Is Checked

The ambient logical setup of (15) is stated over an arbitrary pure type specification PP and a labelled context Γ\Gamma with mode assignment γ\gamma, relative to a family CC of sort profiles.