OctoInformBeta

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

Lemma 36: From proof-mode premises in an ambient logical calculus, with quantified formulas allowed as atoms

Boolean consequences yield labelled proof terms.

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

Boolean valuations then concern the propositional connections, while inhabitation concerns labelled terms in the proof mode of a pure type system.

A pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) consists of sorts SS and arbitrary axiom and product-rule relations.✦ Its terms are variables, sorts, applications, annotated abstractions Ξ»x:A.M\lambda x:A.M and dependent products Ξ x:A.B\Pi x:A.B.✦ Labelled terms have the same constructors, with a label on each application, abstraction and product.✦ The labels 𝖽𝖽\mathsf{dd}, 𝖽𝗉\mathsf{dp} and 𝗉𝗉\mathsf{pp} specify respectively data to data, data to proof and proof to proof.✦ Write d(l)d(l) and r(l)r(l) for the argument and result modes of a label ll. The erasure |M||M| of a labelled term MM is the unlabelled term obtained by deleting all labels from MM. A data-only term is a labelled term whose constructor labels are all 𝖽𝖽\mathsf{dd}.✦

Contexts Ξ“\Gamma are finite lists in newest-first order. A valid context is the empty context or an extension A::Ξ“A::\Gamma of a valid context with Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss. In either term language, typing Ξ“βŠ’M:A\Gamma\vdash M:A is generated by the axiom, variable and weakening rules, dependent product formation along β„›\mathcal R, annotated abstraction, application and conversion. Product formation uses Ξ“βŠ’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; abstraction also requires the resulting product to have a sort. Application substitutes the argument into the codomain. Conversion replaces an expected type by a convertible type that has a sort. In labelled application the function’s product label matches the application label.

Named binders are used in the displayed terms. Variable indices follow the de Bruijn convention, with index zero the newest variable. Renaming MρM^\rho replaces free indices according to ρ\rho, lifting ρ\rho beneath binders to fix the bound variable. Simultaneous substitution M[Οƒ]M[\sigma] replaces free indices by terms and lifts their images beneath binders to avoid capture. The single-variable substitution determined by aa sends zero to aa and n+1n+1 to variable nn; its action on a body is bound-variable instantiation b[a]b[a]. These operations preserve labels in the labelled language. Write ↑M\uparrow M for successor renaming.

Full β\beta reduction contracts (λx:A.b)a(\lambda x:A.b)\,a to b[a]b[a] and permits reduction in every component, including annotations and binder bodies.✦ Labelled head contraction requires matching application and abstraction labels. In either language, β\beta convertibility is the equivalence relation generated by reduction. A normal term has no reduction step.✦ A weakly normalizing term MM reaches a normal term in finitely many steps; M#M^\# denotes its chosen normal form.

A mode assignment Ξ³\gamma assigns each variable data mode 𝖽\mathsf d or proof mode 𝗉\mathsf p. Its extension m::Ξ³m::\gamma assigns mm to zero and Ξ³(n)\gamma(n) to n+1n+1.✦ The mode discipline γ⊒mM:m\gamma\vdash_{\mathrm m}M:m gives a variable its assigned mode and a sort data mode. An application with label ll requires function mode r(l)r(l) and argument mode d(l)d(l), and has mode r(l)r(l). An abstraction requires a data-mode annotation and a body of mode r(l)r(l) under d(l)::Ξ³d(l)::\gamma, and has mode r(l)r(l). A product requires a data-mode domain and a data-mode codomain under d(l)::Ξ³d(l)::\gamma, and has data mode.

Proof-mode inhabitation Pr⁡Ξ“,Ξ³(A)\operatorname{Pr}_{\Gamma,\gamma}(A) is the existence of a labelled inhabitant satisfying the proof-mode discipline, as in (1). PrΞ“,Ξ³(A)β‡”βˆƒp(Ξ“βŠ’p:A∧γ⊒mp:𝗉).\operatorname{Pr}_{\Gamma,\gamma}(A) \quad\Longleftrightarrow\quad \exists p\;\bigl(\Gamma\vdash p:A\ \land\ \gamma\vdash_{\mathrm m}p:\mathsf p\bigr).(1)✦ An open proof transformer Aβ€³Ξ“,Ξ³BA\leadsto_{\Gamma,\gamma}B is a proof-mode term with one temporary proof input of type AA, with the condition in (2). Aβ€³Ξ“,Ξ³Bβ‡”βˆƒt(A::Ξ“βŠ’t:↑B∧(𝗉::Ξ³)⊒mt:𝗉).A\leadsto_{\Gamma,\gamma}B \quad\Longleftrightarrow\quad \exists t\;\bigl(A::\Gamma\vdash t:\uparrow B\ \land\ (\mathsf p::\gamma)\vdash_{\mathrm m}t:\mathsf p\bigr).(2)✦

Profiles and Observation Layers

The normal form sort profile πΓ(T)\pi_\Gamma(T) of a weakly normalizing unlabelled term TT is the set of all sorts typing T#T^\# in Ξ“\Gamma, as in (3).✦ A feasible profile is a nonempty sort set equal to πΓ(T)\pi_\Gamma(T) for some normal term TT in a valid context Ξ“\Gamma.✦ πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s}.\pi_\Gamma(T)=\{s\in S\mid\Gamma\vdash T^\#:s\}.(3)✦ For a sort ss and sort sets II and JJ, the axiom profile Ax⁡(s)\operatorname{Ax}(s) and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) are the sort sets in (4). 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).✦ Ax⁡(s)={t∣(s,t)βˆˆπ’œ},Out⁡(I,J)={cβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›}.\operatorname{Ax}(s)=\{t\mid(s,t)\in\mathcal A\},\qquad \operatorname{Out}(I,J)= \{c\mid\exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\}.(4)

The primary signed graph is the graph on sort sets with positive edges Iβ†’JI\to J for strict inclusions J⊊IJ\subsetneq I of feasible profiles, and, for each feasible triple (I,J,K)(I,J,K), a negative edge Iβ†’KI\to K and a positive edge Jβ†’KJ\to K.✦ Positive reachability allows a finite, possibly empty path using only positive edges.✦ For a collection CC of sort sets, an observation layer is a profile positively reachable from a nonempty Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ A direct observation layer II for CC is an observation layer for which a feasible triple (I,J,K)(I,J,K) has J,K∈CJ,K\in C.✦ A logical terminal profile JJ for CC is a profile for which a feasible triple (I,J,K)(I,J,K) has I,K∈CI,K\in C; write 𝒯C\mathcal T_C for their collection.✦

Witnesses and Wrapper Routes

A fixed feasible witness family W=(TI,vI)IW=(T_I,v_I)_I assigns a labelled type and value to each sort set. At every feasible profile II, the type TIT_I is data-only, its erasure is normal, and Ξ“βŠ’TI:s\Gamma\vdash T_I:s for every s∈Is\in I. The value satisfies Ξ“βŠ’vI:TI\Gamma\vdash v_I:T_I, and both TIT_I and vIv_I have data mode under Ξ³\gamma. More generally, a labelled type AA is sorted at II when Ξ“βŠ’A:s\Gamma\vdash A:s for every s∈Is\in I; this permits additional sorting judgments.✦

A proof wrapper is a finite expression built from an identity wrapper by positive or negative extensions, each adjoining a fixed labelled term.✦ A wrapper path relative to WW and CC assigns such an expression a source profile, a target profile and a parity, given by the number of negative extensions modulo two. The identity path starts and ends at its source with even parity. Inclusion replaces a target JJ by any subset KβŠ†JK\subseteq J without changing the expression or parity. A positive extension at target JJ uses a feasible triple (A,J,K)(A,J,K), adjoins TAT_A and preserves parity. A negative extension uses a feasible triple (J,B,K)(J,B,K) with J,K∈CJ,K\in C, adjoins TBT_B and reverses parity. The wrapper expression and its annotations remain fixed under input substitution and enlargement of sorting profiles.

A quantifier wrapper route for a base profile bb and domain profile II consists of a feasible triple (I,J,K)(I,J,K) and even wrapper paths from bb to JJ and from KK to bb.✦ An ambient logical calculus LL consists of a fixed witness family WW, open proof transformers TJβ€³Ξ“,Ξ³TJβ€²T_J\leadsto_{\Gamma,\gamma}T_{J'} for every pair of terminal profiles, and a feasible triple (d,b,k)(d,b,k) with d,b,k∈Cd,b,k\in C. It has even wrapper paths from bb to dd and from kk to bb, and a quantifier wrapper route with base bb for every direct observation layer.

Interpretable Formulas

A mode-preserving context embedding e:(Ξ“,Ξ³)β†ͺ(Ξ”,Ξ΄)e:(\Gamma,\gamma)\hookrightarrow(\Delta,\delta) is a variable renaming into a valid labelled context Ξ”\Delta that preserves the type and mode of each variable.✦ Context lookup assigns the newest variable the successor shift of the head declaration, and shifts the retrieved type once more for each step to an older declaration.✦ If lookup assigns AA to index nn in Ξ“\Gamma, the embedding requires Ξ”βŠ’e(n):Ae\Delta\vdash e(n):A^e and Ξ΄(e(n))=Ξ³(n)\delta(e(n))=\gamma(n). Witness family renaming gives We=(TIe,vIe)IW^e=(T_I^e,v_I^e)_I in the target context.✦

The witness continuation condition Cont⁡W,C(Q)\operatorname{Cont}_{W,C}(Q) for a labelled term QQ is the requirement that, in every embedded context, a transformer from QQ to a terminal witness type have a proof-mode inhabited target, as in (5).✦ Cont⁡W,C(Q)β‡”βˆ€(Ξ”,Ξ΄)βˆ€e:(Ξ“,Ξ³)β†ͺ(Ξ”,Ξ΄)βˆ€Jβˆˆπ’―C,Qeβ€³Ξ”,Ξ΄TJeβ‡’PrΞ”,Ξ΄(TJe).\begin{split} \operatorname{Cont}_{W,C}(Q)\quad\Longleftrightarrow\quad &\forall(\Delta,\delta)\; \forall e:(\Gamma,\gamma)\hookrightarrow(\Delta,\delta)\; \forall J\in\mathcal T_C,\\ & Q^e\leadsto_{\Delta,\delta}T_J^e \ \Longrightarrow\ \operatorname{Pr}_{\Delta,\delta}(T_J^e). \end{split}(5)✦ The stable witness extraction condition SE⁡W,C(Q)\operatorname{SE}_{W,C}(Q) for a labelled term QQ is the requirement in (6) of extraction from its witness continuation after every mode-preserving context embedding.✦ SE⁡W,C(Q)β‡”βˆ€(Ξ”,Ξ΄)βˆ€e:(Ξ“,Ξ³)β†ͺ(Ξ”,Ξ΄),Cont⁡We,C(Qe)β‡’PrΞ”,Ξ΄(Qe).\begin{split} \operatorname{SE}_{W,C}(Q)\quad\Longleftrightarrow\quad &\forall(\Delta,\delta)\; \forall e:(\Gamma,\gamma)\hookrightarrow(\Delta,\delta),\\ &\operatorname{Cont}_{W^e,C}(Q^e) \ \Longrightarrow\ \operatorname{Pr}_{\Delta,\delta}(Q^e). \end{split}(6)✦ An interpretable formula AA for LL is a labelled term sorted at the base profile bb, having data mode and stable witness extraction.✦ Write β„±L(A)\mathcal F_L(A) for this condition, as in (7). β„±L(A)⇔(βˆ€s∈b,Ξ“βŠ’A:s)∧γ⊒mA:π–½βˆ§SE⁡W,C(A).\mathcal F_L(A)\quad\Longleftrightarrow\quad \bigl(\forall s\in b,\ \Gamma\vdash A:s\bigr) \ \land\ \gamma\vdash_{\mathrm m}A:\mathsf d \ \land\ \operatorname{SE}_{W,C}(A).(7)✦

Propositional Syntax and Interpretation

A propositional formula over atoms Ξ±\alpha is a finite expression generated by atoms, falsity βŠ₯\bot and implication Uβ‡’VU\Rightarrow V.✦ Negation is Β¬U=(Uβ‡’βŠ₯)\neg U=(U\Rightarrow\bot).✦ A Boolean valuation v:Ξ±β†’{0,1}v:\alpha\to\{0,1\} is a map from atoms to truth values, extended to formulas by (8). For a finite list h=(R1,…,Rn)h=(R_1,\ldots,R_n), iterated implication is chain⁡(h,Q)=R1β‡’β‹―β‡’Rnβ‡’Q\operatorname{chain}(h,Q)=R_1\Rightarrow\cdots\Rightarrow R_n\Rightarrow Q, associated to the right, with chain⁡((),Q)=Q\operatorname{chain}((),Q)=Q.✦ ev⁡v(i)=v(i),ev⁡v(βŠ₯)=0,ev⁡v(Uβ‡’V)=Β¬ev⁡v(U)∨ev⁡v(V).\operatorname{ev}_v(i)=v(i),\qquad \operatorname{ev}_v(\bot)=0,\qquad \operatorname{ev}_v(U\Rightarrow V)= \neg\operatorname{ev}_v(U)\lor\operatorname{ev}_v(V).(8)✦

Classical derivability H⊒clUH\vdash_{\mathrm{cl}}U from a set HH of propositional assumptions is the least relation closed under assumption, implication introduction and elimination, and double negation elimination.✦ Introduction derives Uβ‡’VU\Rightarrow V from a derivation of VV under Hβˆͺ{U}H\cup\{U\}; double negation elimination derives UU from ¬¬U\neg\neg U.

Write βŠ₯L\bot_L and Aβ‡’LBA\Rightarrow_L B for the ambient calculus’s falsity and implication types. The propositional interpretation ⟦U⟧a\llbracket U\rrbracket_a associated to an atom assignment a:Ξ±β†’Expr(S)a:\alpha\to\mathrm{Expr}(S), where Expr(S)\mathrm{Expr}(S) denotes the labelled terms over SS, is the labelled term defined by (9). ⟦i⟧a=a(i),⟦βŠ₯⟧a=βŠ₯L,⟦Uβ‡’V⟧a=⟦U⟧aβ‡’L⟦V⟧a.\llbracket i\rrbracket_a=a(i),\qquad \llbracket\bot\rrbracket_a=\bot_L,\qquad \llbracket U\Rightarrow V\rrbracket_a= \llbracket U\rrbracket_a\Rightarrow_L\llbracket V\rrbracket_a.(9)✦

The Claim

Theorem 1 (Tautologies are derivable). Suppose equality of atoms is decidable. Let UU be a propositional formula true under every Boolean valuation. For every set HH of propositional assumptions, (10) holds. H⊒clU.H\vdash_{\mathrm{cl}}U.(10)✦

Theorem 2 (Propositional consequence). Let LL be an ambient logical calculus, and let aa assign an interpretable formula for LL to every atom. Let h=(R1,…,Rn)h=(R_1,\ldots,R_n) be a finite list of propositional formulas, and let QQ be a propositional formula. Suppose chain⁡(h,Q)\operatorname{chain}(h,Q) is true under every Boolean valuation and each ⟦Rj⟧a\llbracket R_j\rrbracket_a has a proof-mode inhabitant in (Ξ“,Ξ³)(\Gamma,\gamma). There is a labelled term pp satisfying (11). Ξ“βŠ’p:⟦Q⟧a,γ⊒mp:𝗉.\Gamma\vdash p:\llbracket Q\rrbracket_a, \qquad \gamma\vdash_{\mathrm m}p:\mathsf p.(11)✦

What Is Checked

The statements range over finite propositional formulas with Boolean valuations and over labelled typing and mode judgments in an ambient logical calculus with fixed feasible witnesses and stable witness extraction for its atom interpretations.

Renaming a fixed feasible witness family along a mode-preserving context embedding preserves its data-only types, normality of their erasures, sorting, typing and data modes.