OctoInformBeta

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

Lemma 37: Even and odd paths retain the original data argument in the resulting formula

Fixed data wrappers admit typed cancellation.

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 fixed data wrapper describes a succession of positive and negative changes of representation. An observation combines the represented term with a second input; negative steps exchange the roles of the datum and a formula family. The cancellation question concerns the formula obtained when the represented term was built from a given input.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations. Terms are variables, sort constants, applications, annotated abstractions λx:A.M\lambda x:A.M, and dependent products Πx:A.B\Pi x:A.B.✦ Labelled terms put one of dddd, dpdp, and pppp on each application, abstraction, and product.✦ These labels specify argument and result modes: data to data, data to proof, and proof to proof, respectively. Erasure |M||M| deletes the labels.✦

A mode assignment γ\gamma assigns data or proof mode to each variable. The mode discipline gives a variable its assigned 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 label’s argument mode. An abstraction has its label’s result mode when its annotation has data mode and its body has the result mode, with the bound variable in the argument mode. A product has data mode when both parts have data mode, with its bound variable in the label’s argument mode. A data-only term has label dddd at every application, abstraction, and product.✦

Contexts are newest-first lists. Writing Γ⊢M:A\Gamma\vdash M:A for the pure type system typing judgement, a valid context is obtained from the empty context by adjoining a type AA for which Γ⊢A:s\Gamma\vdash A:s for some sort ss. The judgement Γ⊢M:A\Gamma\vdash M:A requires the corresponding labelled product in abstraction and application. Its conversion rule permits a change to a convertible expected type having a sort. Full β\beta reduction acts in annotations and binder bodies as well as applications; labelled head contraction requires matching application and abstraction labels. Convertibility is the equivalence relation generated by this reduction. A normal term has no reduction step✦, and a weakly normalizing term reduces in finitely many steps to a normal term.✦

Named binders denote terms with de Bruijn indices, with index zero nearest the binder. Renaming M[ρ]M[\rho] acts on free indices; under a binder its lift fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1. Simultaneous substitution replaces variables by terms, lifting under binders to avoid capture. The notation B[a/x]B[a/x] denotes bound-variable instantiation: index zero is replaced by aa and older free indices are lowered. These operations preserve labels on labelled terms.

Profiles and Logical Formulas

Write T#T^\# for the chosen full β\beta normal form when TT is weakly normalizing.✦ The normal-form sort profile, axiom successors, and product outputs are the sets specified 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, I⊆SI\subseteq S, equal to πΓ(T)\pi_\Gamma(T) for a normal term TT in a valid context. A feasible product profile triple (I,J,K)(I,J,K) has all three profiles feasible and K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦ A labelled type TT is sorted at II when Γ⊢T:s\Gamma\vdash T:s for every s∈Is\in I; additional sorts are allowed.✦

Fix a collection CC of profiles. The primary signed graph has positive edges from a feasible profile to each proper feasible subset, negative edges I→KI\longrightarrow K for feasible triples (I,J,K)(I,J,K), and positive edges J→KJ\longrightarrow K for those triples.✦ Positive reachability uses only positive edges and permits the empty path.✦ An observation layer II for CC is a profile positively reachable from some nonempty Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ A direct observation layer II for CC is an observation layer admitting a triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ A logical terminal profile JJ for CC is a profile admitting a triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

A fixed feasible witness family W=(TI,vI)W=(T_I,v_I) chooses, at each feasible profile II, a data-only type TIT_I with normal erasure, sorted at II, and a term Γ⊢vI:TI\Gamma\vdash v_I:T_I. Both TIT_I and vIv_I have data mode under γ\gamma. A mode-preserving context embedding e:(Γ,γ)→(Δ,δ)e:(\Gamma,\gamma)\longrightarrow(\Delta,\delta) is a variable renaming into a valid context that preserves the types of context variables and their modes.✦ In a newest-first labelled context, context lookup assigns each variable its declared type with free indices shifted past its own declaration and every newer declaration.✦ Write MeM^e for transport along ee; witness transport sends (TI,vI)(T_I,v_I) to (TIe,vIe)(T_I^e,v_I^e).

Proof-mode inhabitation Pr⁡(A)\operatorname{Pr}(A) of a type AA is the existence of a proof-mode term pp with Γ⊢p:A\Gamma\vdash p:A.✦ A typed open proof transformer Tr⁡(A,B)\operatorname{Tr}(A,B) is a proof-mode term in the context with a temporary proof input of type AA, as specified in (2); the upward arrow is the successor renaming of free indices. Typed logical equivalence A≃Γ,γBA\simeq_{\Gamma,\gamma}B between types AA and BB consists of a typed open proof transformer in each direction, as specified in (2). Tr⁡Γ,γ(A,B)⇔∃t(A::Γ⊢t:B↑and t has proof mode under 𝗉𝗋𝗈𝗈𝖿::γ),A≃Γ,γB⇔Tr⁡Γ,γ(A,B)and Tr⁡Γ,γ(B,A).\begin{aligned} \operatorname{Tr}_{\Gamma,\gamma}(A,B) &\iff\exists t\;\bigl(A::\Gamma\vdash t:B^\uparrow \ \text{and }t\text{ has proof mode under }\mathsf{proof}::\gamma\bigr),\\ A\simeq_{\Gamma,\gamma}B &\iff\operatorname{Tr}_{\Gamma,\gamma}(A,B) \ \text{and }\operatorname{Tr}_{\Gamma,\gamma}(B,A). \end{aligned}(2) The transformers in (2) are uniform in the temporary proof input.

A proof wrapper is a finite expression generated by an identity and positive or negative extensions, each adjoining a fixed labelled annotation.✦ A formed path for a wrapper starts at a profile II with even parity. An inclusion step replaces the current target JJ by a subset without changing the expression or parity. A positive extension along (A,J,K)(A,J,K) appends TAT_A and preserves parity; a negative extension along (J,B,K)(J,B,K) appends TBT_B and reverses parity, requiring J,K∈CJ,K\in C. Renaming a wrapper renames its annotations.✦ A wrapper contains a negative step when at least one extension is negative.✦

An ambient logical calculus LL is a collection of choices that includes witnesses WW and typed open proof transformers between the witness types at every ordered pair of terminal profiles. It chooses profiles d,𝔟,k∈Cd,\mathfrak b,k\in C with triple (d,𝔟,k)(d,\mathfrak b,k), together with even proof wrapper paths from 𝔟\mathfrak b to dd and from kk to 𝔟\mathfrak b. For every direct observation layer II, it also chooses a quantifier route: a triple (I,J,K)(I,J,K) and even proof wrapper paths from 𝔟\mathfrak b to JJ and from KK to 𝔟\mathfrak b. Transport LeL^e renames the witnesses and wrapper annotations, including those of its quantifier routes, and retains the profiles.✦

A witness continuation for a labelled term QQ relative to W,CW,C is the following condition: after any mode-preserving context embedding ee, a transformer from QeQ^e to TJeT_J^e, for any terminal profile JJ, entails proof-mode inhabitation of TJeT_J^e.✦ Stable witness extraction for QQ means that, after every such embedding ee, a witness continuation for QeQ^e relative to We,CW^e,C entails proof-mode inhabitation of QeQ^e.✦ An interpretable formula FF for LL is a data-mode term sorted at 𝔟\mathfrak b that admits stable witness extraction.✦

A stable formula family QQ over TT is a term with one distinguished data variable x:Tx:T such that, after every embedding ee and for every data-mode term Δ⊢a:Te\Delta\vdash a:T^e, the instance Qe[a/x]Q^e[a/x] is an interpretable formula for LeL^e.✦ Here renaming the family fixes its distinguished variable. A parity-dependent data argument 𝒟b(T,a)\mathcal D_b(T,a) is defined by (3), where 00 is even and 11 is odd. 𝒟0(T,a)⇔Γ⊢a:Tand a has data mode,𝒟1(T,a)⇔a is a stable formula family over T.\begin{aligned} \mathcal D_0(T,a)&\iff\Gamma\vdash a:T \ \text{and }a\text{ has data mode},\\ \mathcal D_1(T,a)&\iff a\text{ is a stable formula family over }T. \end{aligned}(3)✦

Fixed Data Paths

A positive data path is a finite expression generated by the identity and extensions with a fixed pair of labelled terms.✦ Its formation from II starts with the identity at II, permits restriction of the target to any subset, and extends a target JJ along a triple (A,J,K)(A,J,K) using the pair (TA,vA)(T_A,v_A).✦

A data path tail UU is a tuple consisting of a sort ss, a positive data path, and encoding and decoding proof wrappers.✦ A tail formed at BB requires {s}∈C\{s\}\in C and nonempty Ax⁡(s)\operatorname{Ax}(s); its positive path runs from Ax⁡(s)\operatorname{Ax}(s) to BB. The encoding path runs from 𝔟\mathfrak b to {s}\{s\} and the decoding path from {s}\{s\} to 𝔟\mathfrak b, both with even parity. The decoding wrapper must contain a negative step.

A retained data path RR from II to JJ is a finite expression with a parity bb, formed by the following rules. The identity runs from II to II with even parity, and a restriction replaces its current target by any subset. A positive extension along a triple (A,J,K)(A,J,K) adjoins the fixed pair (TA,vA)(T_A,v_A) and preserves parity. A negative extension along (J,B,K)(J,B,K) adjoins a tail formed at BB and reverses parity.

The data path builder 𝖡R(T,a)\mathsf B_R(T,a) and data path observation 𝖮R(T,w,q)\mathsf O_R(T,w,q) are the recursive labelled term operations in (4). Write R(T)R(T) for the preceding path’s type annotation, 𝖲U\mathsf S_U for sending a formula through a tail UU, and 𝖧U\mathsf H_U for reading through that tail. The notation RD,v+R^+_{D,v} denotes a positive extension and RU−R^-_U a negative extension; every application and abstraction in (4) has label dddd, and bound names are chosen to avoid capture. 𝖡id(T,a)=a,𝖮id(T,w,q)=q[w/x],𝖡RD,v+(T,a)=λz:D.𝖡R(T,a),𝖮RD,v+(T,w,q)=𝖮R(T,wv,q),𝖡RU−(T,a)=λw:R(T).𝖲U(𝖮R(T,w,a)),𝖮RU−(T,w,q)=𝖧U(w𝖡R(T,q)).\begin{aligned} \mathsf B_{\mathrm{id}}(T,a)&=a,\\ \mathsf O_{\mathrm{id}}(T,w,q)&=q[w/x],\\ \mathsf B_{R^+_{D,v}}(T,a)&=\lambda z:D.\mathsf B_R(T,a),\\ \mathsf O_{R^+_{D,v}}(T,w,q)&=\mathsf O_R(T,w\,v,q),\\ \mathsf B_{R^-_U}(T,a)&= \lambda w:R(T).\mathsf S_U(\mathsf O_R(T,w,a)),\\ \mathsf O_{R^-_U}(T,w,q)&= \mathsf H_U\bigl(w\,\mathsf B_R(T,q)\bigr). \end{aligned}(4) The parity cancellation formula 𝖢b(a,q)\mathsf C_b(a,q) is the instance defined in (5). 𝖢b(a,q)={q[a/x],b=0,a[q/x],b=1.\mathsf C_b(a,q)= \begin{cases} q[a/x],&b=0,\\ a[q/x],&b=1. \end{cases}(5)✦

The Claim

Theorem 1. Let LL be an ambient logical calculus in (Γ,γ)(\Gamma,\gamma) and let RR be a formed retained data path from II to JJ, of parity bb. Suppose that TT is sorted at II and has data mode. Let aa satisfy 𝒟b(T,a)\mathcal D_b(T,a) and let qq satisfy 𝒟1−b(T,q)\mathcal D_{1-b}(T,q). Then 𝖮R(T,𝖡R(T,a),q)≃Γ,γ𝖢b(a,q).\mathsf O_R\bigl(T,\mathsf B_R(T,a),q\bigr) \simeq_{\Gamma,\gamma}\mathsf C_b(a,q).(6)✦

What Is Checked

The claim (6) is stated over labelled terms and their mode discipline, with a fixed logical calculus, a formed retained data path, sorting of the input type, and complementary parity-dependent data arguments.