OctoInformBeta

OpenAI preprint, September 2026 Β· Β§7. Typed data channels

Lemma 40: Two odd data paths admit either bit, with recovery by uniform typed formula equivalence

Canonical embeddings retain their signed payloads.

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 data argument can pass through two contravariant data paths while formulas continue to observe it. The two choices of sign belong to the embedding of that argument; the observations are formulas interpreted in an ambient logical calculus.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications, annotated abstractions Ξ»x:A.M\lambda x:A.M and dependent products Ξ x:A.B\Pi x:A.B.✦ Contexts are newest-first. Named binders below stand for de Bruijn syntax, with index zero at the nearest binder. A valid context starts empty and extends by AA whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ Typing Ξ“βŠ’M:A\Gamma\vdash M:A uses the axiom, variable, weakening, product, abstraction, application and conversion rules determined by PP.

Full Ξ²\beta reduction contracts (Ξ»x:A.M)a(\lambda x:A.M)\,a to M[a/x]M[a/x] and reduces in every annotation and binder body.✦ Beta convertibility is the equivalence relation generated by full Ξ²\beta reduction.✦ A term is normal if it admits no full Ξ²\beta reduction step; a term is weakly normalizing if it reaches a normal term in finitely many full Ξ²\beta reduction steps. Write M#M^\# for its chosen full normal form when one exists, with a fixed fallback otherwise.✦ For a term TT in a context Ξ“\Gamma, sets I,JI,J of sorts and a sort ss, the normal form sort profile, product output profile and axiom successor set are given in (1). πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›},Ax⁡(s)={t∈S∣(s,t)βˆˆπ’œ}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \operatorname{Out}(I,J)&=\{c\in S\mid \exists a\in I\;\exists b\in J\;(a,b,c)\in\mathcal R\},\\ \operatorname{Ax}(s)&=\{t\in S\mid(s,t)\in\mathcal A\}. \end{aligned}(1) A feasible profile is a nonempty set I=πΓ(T)I=\pi_\Gamma(T) for a normal term TT in a valid context Ξ“\Gamma.✦ 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).✦ The axiom profile of a sort ss is denoted by Ax⁡(s)\operatorname{Ax}(s).

The primary signed graph has positive edges from a feasible profile to a proper feasible subset. A feasible triple (I,J,K)(I,J,K) also gives a negative edge Iβ†’KI\to K and a positive edge Jβ†’KJ\to K. A profile JJ is positively reachable from a profile II if there is a finite path of positive edges from II to JJ, with the empty path allowed.✦ Fix a collection CC of profiles. An observation layer II relative to CC is a feasible profile positively reachable from Ax⁡(s)\operatorname{Ax}(s) for some {s}∈C\{s\}\in C with nonempty Ax⁡(s)\operatorname{Ax}(s).✦ An observation layer II relative to CC is direct if some feasible triple (I,J,K)(I,J,K) has that layer as domain and has J,K∈CJ,K\in C.✦ A terminal profile JJ relative to CC is a feasible profile occurring in a feasible triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

Labelled terms attach 𝖽𝖽\mathsf{dd}, 𝖽𝗉\mathsf{dp} or 𝗉𝗉\mathsf{pp} to every application, abstraction and product.✦ These labels have argument and result modes data/data, data/proof and proof/proof, respectively. The erasure of a labelled term is the unlabelled term obtained by deleting its labels. Labelled typing uses the same typing rules, with matching labels on an abstraction and its dependent product type, and on a function’s product type and its application.✦ Labelled Ξ²\beta contraction requires matching application and abstraction labels; its closure under term components and its convertibility are defined as above. A data-only term has label 𝖽𝖽\mathsf{dd} at every labelled constructor.✦

A mode assignment Ξ³\gamma assigns data or proof to each variable. The mode discipline gives variables their assigned modes and sorts data mode. An application requires its function and argument to have the result and argument modes of its label. An abstraction requires a data annotation and a body of the result mode under the argument-mode extension of Ξ³\gamma. A product requires data domain and codomain under that same extension and has data mode. Write Aβ†’β„“BA\to_\ell B for the nondependent labelled product.✦ Renaming and simultaneous capture-avoiding substitution preserve labels; under a binder their lifts fix the bound variable and shift the renamed variables or substituted terms. Instantiation Q[a/x]Q[a/x] replaces the newest variable by aa and lowers older indices.✦

Sorting at a profile requires every indicated sort, as in (2); other sorts may also type the same term.✦ Sorted⁡Ξ“(A,I)β‡”βˆ€s∈I,Ξ“βŠ’A:s.\operatorname{Sorted}_\Gamma(A,I)\quad\Longleftrightarrow\quad \forall s\in I,\;\Gamma\vdash A:s.(2)✦ A fixed feasible witness family WW chooses a type TIT_I and value vIv_I for every profile. At each feasible II, the type is data-only with normal erasure and satisfies Sorted⁡Ξ“(TI,I)\operatorname{Sorted}_\Gamma(T_I,I); moreover Ξ“βŠ’vI:TI\Gamma\vdash v_I:T_I, and both TIT_I and vIv_I have data mode under Ξ³\gamma.✦

Logical Interpretation

A proof wrapper HH is a finite sequence of positive and negative extensions of the identity, each retaining a fixed labelled term.✦ Its application is defined by (3). id[A]=A,H+D[A]=D→𝖽𝗉H[A],Hβˆ’F[A]=H[A]→𝗉𝗉F.\begin{aligned} \mathrm{id}[A]&=A,\\ H^{+D}[A]&=D\to_{\mathsf{dp}}H[A],\\ H^{-F}[A]&=H[A]\to_{\mathsf{pp}}F. \end{aligned}(3)✦ A formed proof wrapper from II to JJ starts with the identity at II, allows target restriction to a subset, and extends along feasible triples. A positive extension along (D,J,K)(D,J,K) retains TDT_D and preserves parity. A negative extension along (J,F,K)(J,F,K) retains TFT_F, requires J,K∈CJ,K\in C, and reverses parity. The parity of a proof wrapper HH is its number of negative extensions modulo two; HH contains a negative step if at least one of its extensions is negative.

Write Ξ“;γ⊒pA\Gamma;\gamma\vdash_{\mathrm p}A when a proof-mode term pp satisfies Ξ“βŠ’p:A\Gamma\vdash p:A.✦ A typed open proof transformer from AA to BB is a proof-mode term uu in the context extended by a proof variable p:Ap:A, with expected type BB weakened into that context.✦ Formula equivalence A≃Γ,Ξ³BA\simeq_{\Gamma,\gamma}B means a uniform typed open proof transformer in each direction.✦

An ambient logical calculus LL consists of a witness family WW, typed open proof transformers between its witness types at any two terminal profiles, and the following profile, proof-wrapper and quantifier-route choices. It chooses profiles d,o,k∈Cd,o,k\in C forming a feasible triple (d,o,k)(d,o,k), together with even proof wrappers HinH_{\mathrm{in}} from oo to dd and HoutH_{\mathrm{out}} from kk to oo. For every direct observation layer II, it also chooses a quantifier route: a feasible triple (I,J,K)(I,J,K) with an even input proof wrapper from oo to JJ and an even output proof wrapper from KK to oo. The logical base is oo and falsity is βŠ₯=To\bot=T_o. These choices determine the logical operations in (4). Aβ‡’LB=Hout[Hin[A]→𝗉𝗉B],Β¬LA=(Aβ‡’LβŠ₯),⊀L=(βŠ₯β‡’LβŠ₯),A∧LB=Β¬L(Aβ‡’LΒ¬LB),A∨LB=Β¬L(Β¬LA∧LΒ¬LB),if⁡L(G,A,B)=(G∧LA)∨L(Β¬LG∧LB),sgn⁡1(A)=A,sgn⁡0(A)=Β¬LA.\begin{aligned} A\Rightarrow_L B &=H_{\mathrm{out}}[H_{\mathrm{in}}[A]\to_{\mathsf{pp}} B], &\neg_L A&=(A\Rightarrow_L\bot),\\ \top_L&=(\bot\Rightarrow_L\bot), &A\wedge_L B&=\neg_L(A\Rightarrow_L\neg_L B),\\ A\vee_L B&=\neg_L(\neg_L A\wedge_L\neg_L B), &\operatorname{if}_L(G,A,B)&=(G\wedge_L A)\vee_L(\neg_L G\wedge_L B),\\ \operatorname{sgn}_1(A)&=A, &\operatorname{sgn}_0(A)&=\neg_L A. \end{aligned}(4) The operations in (4) are logical implication, logical negation, logical truth, logical conjunction, logical disjunction, the logical conditional and polarity selection. A logical operation code consists of a labelled falsity term and incoming and outgoing proof wrappers. The code associated with LL consists of βŠ₯\bot, HinH_{\mathrm{in}} and HoutH_{\mathrm{out}}.

A mode-preserving context embedding e:(Ξ“,Ξ³)β†’(Ξ”,Ξ΄)e:(\Gamma,\gamma)\to(\Delta,\delta) is a variable renaming into a valid context Ξ”\Delta that preserves variable types and modes.✦ Context lookup shifts a declaration’s type across each newer declaration.✦ Write A[e]A[e] for renaming by ee, and e+e^+ for its lift under a binder. A witness continuation for a term AA relative to W,CW,C is the condition that, after every mode-preserving context embedding ee into (Ξ”,Ξ΄)(\Delta,\delta) and for every terminal JJ, the existence of a typed open proof transformer from A[e]A[e] to TJ[e]T_J[e] entails Ξ”;δ⊒pTJ[e]\Delta;\delta\vdash_{\mathrm p}T_J[e].✦ Stable witness extraction for a term AA is the property that, after every mode-preserving context embedding ee into (Ξ”,Ξ΄)(\Delta,\delta), a witness continuation for A[e]A[e] relative to the transported witness family entails Ξ”;δ⊒pA[e]\Delta;\delta\vdash_{\mathrm p}A[e].✦ Renaming a proof wrapper preserves its identity and its sequence of positive and negative steps, and renames the fixed annotation at every step. Renaming a logical operation code renames its falsity term and its incoming and outgoing proof wrappers by the same variable renaming.

An interpretable formula for LL is a data-mode term sorted at oo that admits stable witness extraction.✦ A stable formula family QQ over TT is a term with a distinguished input such that, under every mode-preserving context embedding ee and for every data-mode argument aa with Ξ”βŠ’a:T[e]\Delta\vdash a:T[e], the instance Q[e+][a/x]Q[e^+][a/x] is an interpretable formula for the transported calculus L[e]L[e].✦

Retained Data Paths

A positive data path is a finite sequence of positive extensions retaining an annotation and dummy value at each step.✦ Formation starts at the identity, permits target restriction, and extends from JJ to KK along a feasible triple (A,J,K)(A,J,K) using TA,vAT_A,v_A.✦ A data path tail UU is a positive data path equipped with a sort ss and encoding and decoding proof wrappers.✦ A data path tail UU with chosen sort ss is formed at JJ when {s}∈C\{s\}\in C, Ax⁡(s)\operatorname{Ax}(s) is nonempty, and its positive part is formed from Ax⁡(s)\operatorname{Ax}(s) to JJ. Its encoding wrapper is even from oo to {s}\{s\}; its decoding wrapper is even from {s}\{s\} to oo and contains a negative step.

A retained data path rr is an identity followed by positive extensions retaining a type and dummy value, or negative extensions retaining a data path tail.✦ A formed retained path from II to JJ permits target restriction as before. A positive extension along (A,J,K)(A,J,K) retains TA,vAT_A,v_A. A negative extension along (J,B,K)(J,B,K) requires a formed tail at BB. Positive extensions preserve parity and negative extensions reverse it.

The wrapped type Dr(T)D_r(T) is TT at the identity. A positive extension with annotation DD changes it to D→𝖽𝖽Dr(T)D\to_{\mathsf{dd}}D_r(T); a negative extension with tail UU changes it to Dr(T)→𝖽𝖽CUD_r(T)\to_{\mathsf{dd}}C_U, where CUC_U is the tail carrier. The builder Br(T,a)B_r(T,a) returns aa at the identity and adds a constant data abstraction at a positive extension. At a negative extension it abstracts over Dr(T)D_r(T), observes the bound input against aa along the inner path, and sends the resulting formula through the tail’s encoding operation. Ambient variables are shifted under the binder, while any distinguished input of aa is retained.

The observation Or(T,w,a)O_r(T,w,a) is a[w/x]a[w/x] at the identity. At a positive extension it applies ww to the retained dummy value and continues along the inner path. At a negative extension it applies ww to the inner builder Br(T,a)B_r(T,a) and reads the result through the tail’s decoding operation. For odd rr, the contravariant term associated to tt is the body Or(T,z,t)O_r(T,z,t) in the context extended by z:Dr(T)z:D_r(T), with all ambient terms and path annotations weakened into that context.✦

Double Channels

A double data channel R=(r1,r2)R=(r_1,r_2) consists of two odd retained data paths.✦ It is formed from II through JJ to KK when r1r_1 is formed from II to JJ and r2r_2 from JJ to KK.✦ For a bit b∈{0,1}b\in\{0,1\}, the signed embeddings and observations of RR are defined in (5), where vv denotes a double channel value and QQ a formula callback with a distinguished input. Expressions displayed as x↦Qx\mapsto Q denote bodies with a distinguished input, with ambient terms and logical operations weakened under that input. emb⁡b(T,t)=Br2(Dr1(T),z↦sgn⁡b(Or1(T,z,t))),bit⁡T(v)=Or2(Dr1(T),v,Br1(T,xβ†¦βŠ€L)),eval⁡T(v,Q)=Or2(Dr1(T),v,Br1(T,Q)),recover⁡T(v,Q)=if⁡L(bit⁡T(v),eval⁡T(v,Q),Β¬Leval⁡T(v,Q)).\begin{aligned} \operatorname{emb}_b(T,t) &=B_{r_2}\bigl(D_{r_1}(T), z\mapsto\operatorname{sgn}_b(O_{r_1}(T,z,t))\bigr),\\ \operatorname{bit}_T(v) &=O_{r_2}\bigl(D_{r_1}(T),v,B_{r_1}(T,x\mapsto\top_L)\bigr),\\ \operatorname{eval}_T(v,Q) &=O_{r_2}\bigl(D_{r_1}(T),v,B_{r_1}(T,Q)\bigr),\\ \operatorname{recover}_T(v,Q) &=\operatorname{if}_L\bigl(\operatorname{bit}_T(v), \operatorname{eval}_T(v,Q),\neg_L\operatorname{eval}_T(v,Q)\bigr). \end{aligned}(5) The operations bit⁡T(v)\operatorname{bit}_T(v), eval⁡T(v,Q)\operatorname{eval}_T(v,Q) and recover⁡T(v,Q)\operatorname{recover}_T(v,Q) in (5) are encoded bit observation, double channel evaluation and signed payload recovery, respectively.

The Claim

Theorem 1 (Canonical signed embeddings). Let LL be an ambient logical calculus in (Ξ“,Ξ³)(\Gamma,\gamma) and let R=(r1,r2)R=(r_1,r_2) be a formed double data channel from II through JJ to KK. Suppose Sorted⁡Ξ“(T,I)\operatorname{Sorted}_\Gamma(T,I), Ξ“βŠ’t:T\Gamma\vdash t:T, and both TT and tt have data mode under Ξ³\gamma. For either b∈{0,1}b\in\{0,1\}, Ξ“;γ⊒psgn⁡b(bit⁡T(emb⁡b(T,t))).\Gamma;\gamma\vdash_{\mathrm p} \operatorname{sgn}_b\bigl( \operatorname{bit}_T(\operatorname{emb}_b(T,t))\bigr).(6)✦ For every stable formula family QQ over TT, recover⁡T(emb⁡b(T,t),Q)≃Γ,Ξ³Q[t/x].\operatorname{recover}_T(\operatorname{emb}_b(T,t),Q) \simeq_{\Gamma,\gamma} Q[t/x].(7)✦

What Is Checked

The assertions (6) and (7) are stated over labelled typing and the data/proof mode discipline, a fixed logical calculus and two formed odd data paths; recovery also assumes a stable formula family. Transport along a mode-preserving context embedding retains the witness family’s data-only types with normal erasures, profile sorting and typed data values. Transport of the logical calculus retains its profiles and proof transformers between terminal witness types, renames its fixed proof wrappers, and transports each quantifier route with the same feasible triple. Renaming a retained data path preserves its extension sequence and renames its annotations and tails.✦