OctoInformBeta

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

Lemma 41: A formed double data channel with eight nonzero queries and a separate zero payload tag

Encoding distinguishes tags and preserves observations.

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

An odd retained data path pairs a data term with a test to produce a formula. A double channel uses two odd paths and four successive carrier extensions to transport a predicate with a query tag.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R) with arbitrary axiom and product-rule relations. Terms have 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 give each application and binder a label dddd, dpdp, or pppp, recording data to data, data to proof, or proof to proof.✦ Write 𝖽\mathsf d and 𝗉\mathsf p for these two modes. Contexts are newest-first lists; named bound variables below stand for de Bruijn indices, with zero referring to the nearest binder.

For a labelled context Ξ“\Gamma, the typing judgment Ξ“βŠ’M:A\Gamma\vdash M:A uses the axiom, variable, weakening, product, abstraction, application, and conversion rules, with matching labels in function types and their applications.✦ Full labelled Ξ²\beta reduction contracts a labelled abstraction applied with the same label and permits reduction in every annotation and binder body.✦ Convertibility is its equivalence closure.✦ Erasure deletes the labels and gives the corresponding unlabelled terms.✦ A data-only term has label dddd at every application and binder.✦

A mode environment Ξ³\gamma assigns a mode to each variable. Its extension by mm assigns mm to the newest variable and retains the older assignments.✦ The mode discipline assigns variables their environment modes and sorts data mode. An application uses its label’s argument and result modes. An abstraction has a data-mode annotation and a body in the result mode, checked after extension by the argument mode. A product has data mode when its domain and codomain have data mode under the corresponding binder extension. The nondependent labelled arrow is defined in (1). Aβ†’β„“B=Ξ β„“x:A.B,x does not occur freely in B.A\xrightarrow{\ell}B=\Pi^{\ell}x:A.B, \qquad x\text{ does not occur freely in }B.(1)✦

A normal term admits no full Ξ²\beta step.✦ A weakly normalizing term TT is a term that has a finite Ξ²\beta reduction to a normal term; write T#T^\# for a chosen such normal form. For an unlabelled context Ξ”\Delta, the normal form sort profile and the axiom and output profiles are the sets in (2). πΔ(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_\Delta(T)&=\{s\in S\mid\Delta\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}(2) A valid context is obtained from the empty context by adjoining types that have a sort.✦ A feasible profile II is a nonempty set of sorts of the form I=πΔ(T)I=\pi_\Delta(T) for a normal term TT in a valid context Ξ”\Delta.✦ A feasible product triple (I,J,K)(I,J,K) consists of feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦ For labelled terms, sorting at II, written Ξ“βŠ’T:I\Gamma\vdash T:I, means Ξ“βŠ’T:s\Gamma\vdash T:s for every s∈Is\in I; further sorts are allowed.✦ For unlabelled terms, Ξ”βŠ’M:A\Delta\vdash M:A is the typing judgment of the pure type system PP, with the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦

The primary signed graph has a positive inclusion edge from a feasible profile II to a feasible profile JJ whenever 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 positive path is a finite, possibly empty, path using only positive edges.✦ For a collection CC of profiles, an observation layer II is a profile reachable positively from a nonempty Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ For a collection CC of profiles, a direct observation layer II is an observation layer for CC that admits a feasible triple (I,J,K)(I,J,K) with J,K∈CJ,K\in C.✦ A logical terminal profile JJ is the middle profile of a feasible triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

Logical and Data Paths

A feasible witness family WW chooses a type DID_I and a value eIe_I at every feasible profile II. The type is data-only, has normal erasure, and is sorted at II in Ξ“\Gamma; Ξ“βŠ’eI:DI\Gamma\vdash e_I:D_I, and both terms have data mode under Ξ³\gamma.

A proof wrapper is a finite sequence of positive and negative extensions of the identity wrapper.✦ The identity wrapper acts on a formula AA as AA; if a wrapper QQ acts as Q(A)Q(A), a positive extension with annotation DD acts as Dβ†’dpQ(A)D\xrightarrow{dp}Q(A), and a negative extension with annotation FF acts as Q(A)β†’ppFQ(A)\xrightarrow{pp}F.✦ A formed proof path starts with the identity at its source profile and permits restriction of its target profile to a subset. A positive extension uses a feasible triple (H,J,K)(H,J,K) and annotation DHD_H to pass from JJ to KK. A negative extension uses (J,H,K)(J,H,K) and annotation DHD_H, requires J,K∈CJ,K\in C, and reverses parity. Parity counts negative extensions modulo two. The negative-step test records whether at least one negative extension occurs.✦

A typed open proof transformer from a formula AA to a formula BB is a proof-mode term of type BB in the context extended by a temporary proof input of type AA; the ambient variables in BB are shifted under that input.✦ A logical setup LL chooses WW and uniform typed open proof transformers between the witness types at any two logical terminal profiles. It also chooses a feasible triple (d,b,k)(d,b,k) with d,b,k∈Cd,b,k\in C, together with even proof paths Qin:bβ€³dQ_{\mathrm{in}}:b\leadsto d and Qout:kβ€³bQ_{\mathrm{out}}:k\leadsto b. For every direct observation layer II, a quantifier route chooses a feasible triple (I,J,K)(I,J,K) and even proof paths from bb to JJ and from KK to bb.✦ The logical falsity βŠ₯L\bot_L of the logical setup LL is the witness type DbD_b.✦ The logical code of LL consists of this falsity and its two fixed wrappers; its operations are defined in (3).✦ Logical implication Aβ‡’LBA\Rightarrow_L B wraps the proof-to-proof arrow from Qin(A)Q_{\mathrm{in}}(A) to BB with QoutQ_{\mathrm{out}}.✦ Logical negation Β¬LA\neg_L A is implication from AA to the logical falsity βŠ₯L\bot_L.✦ Logical conjunction A∧LBA\wedge_L B negates the implication from AA to the negation of BB.✦ Negating the conjunction of the negations of AA and BB gives logical disjunction A∨LBA\vee_L B.✦ The polarity-selected proposition sgn⁡L(Ξ΅,A)\operatorname{sgn}_L(\varepsilon,A) is AA when Ξ΅\varepsilon is true and its logical negation when Ξ΅\varepsilon is false.✦ Aβ‡’LB=Qout(Qin(A)β†’ppB),Β¬LA=Aβ‡’LβŠ₯L,A∧LB=Β¬L(Aβ‡’LΒ¬LB),A∨LB=Β¬L(Β¬LA∧LΒ¬LB),sgn⁡L(Ξ΅,A)={A,Ξ΅ is true,Β¬LA,Ξ΅ is false.\begin{aligned} A\Rightarrow_L B &=Q_{\mathrm{out}}\bigl(Q_{\mathrm{in}}(A)\xrightarrow{pp}B\bigr),& \neg_L A&=A\Rightarrow_L\bot_L,\\ 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{sgn}_L(\varepsilon,A) &=\begin{cases}A,&\varepsilon\text{ is true},\\ \neg_L A,&\varepsilon\text{ is false}. \end{cases} \end{aligned}(3)

An all-positive data path retains a domain annotation and its original dummy value at each extension. Its formation starts at the identity, permits target restriction, and uses a feasible triple (H,J,K)(H,J,K) to extend from JJ to KK with DH,eHD_H,e_H.✦ A formed data tail ending at JJ chooses a sort ss with {s}∈C\{s\}\in C and nonempty Ax⁡(s)\operatorname{Ax}(s), an all-positive data path from Ax⁡(s)\operatorname{Ax}(s) to JJ, and even proof paths from bb to {s}\{s\} and back. Its returning proof path must contain a negative step.

A retained data path starts at the identity and admits positive extensions with fixed annotations and dummy values, or negative extensions with fixed data tails.✦ Its parity counts its negative extensions. Formation allows target restriction and positive extensions along feasible triples (H,J,K)(H,J,K) using DH,eHD_H,e_H. A negative extension from JJ to KK uses a feasible triple (J,H,K)(J,H,K) and a formed tail ending at HH. A double channel R=(R1,R2)R=(R_1,R_2) is a pair of odd retained paths.✦ A double channel R=(R1,R2)R=(R_1,R_2) is formed from II through JJ to KK when R1R_1 is formed from II to JJ and R2R_2 is formed from JJ to KK.✦

Write V[T]V[T] for the type wrapped along a retained path VV. The identity gives TT; a positive extension with annotation DD gives Dβ†’ddV[T]D\xrightarrow{dd}V[T], and a negative extension with tail HH gives V[T]β†’ddH*V[T]\xrightarrow{dd}H_*, where H*H_* is the tail’s carrier.✦ Write VD,e+V^+_{D,e} and VHβˆ’V^-_H for these two extensions. The builder BV(T,a)B_V(T,a) returns aa at the identity and forms a constant data abstraction at a positive extension. At a negative extension it abstracts over V[T]V[T], observes its bound input against aa, and sends the resulting formula through the tail. A callback’s distinguished input remains free during this construction.

The observation OV(T,w,a)O_V(T,w,a) is defined by (4), where read⁡H\operatorname{read}_H is the tail’s reading operation and a[w/x]a[w/x] is capture-avoiding instantiation of its distinguished input. Oid(T,w,a)=a[w/x],OVD,e+(T,w,a)=OV(T,wdde,a),OVHβˆ’(T,w,a)=read⁡H(wddBV(T,a)).\begin{aligned} O_{\mathrm{id}}(T,w,a)&=a[w/x],\\ O_{V^+_{D,e}}(T,w,a)&=O_V(T,w\,^{dd}e,a),\\ O_{V^-_H}(T,w,a)&=\operatorname{read}_H \bigl(w\,^{dd}B_V(T,a)\bigr). \end{aligned}(4)✦ For an odd path VV, its observation callback is the open formula ev⁡V(T,w)(x)=OV(T,w,x)\operatorname{ev}_V(T,w)(x)=O_V(T,w,x) in a context extended by x:Tx:T.✦

Renaming acts on every retained annotation and dummy value, on both paths of a double channel, and on the logical code, preserving their path shapes and parities. Substitution replaces variables capture-avoidantly, fixing the newest variable under a binder and shifting the older images.✦ The open composition F∘GF\circ G of open terms FF and GG with a common ambient context is the open term obtained by substituting GG for the distinguished input of FF while preserving that ambient context.✦

Tags and Payloads

For the double channel RR, let CRC_R denote its carrier operation. Its iterated carrier CRn(T)C_R^n(T) and fourfold carrier ℬR(T)\mathcal B_R(T) are defined in (5). CR0(T)=T,CRn+1(T)=CR(CRn(T)),ℬR(T)=CR4(T).C_R^0(T)=T,\qquad C_R^{n+1}(T)=C_R\bigl(C_R^n(T)\bigr),\qquad \mathcal B_R(T)=C_R^4(T).(5) A query index q∈{0,…,8}q\in\{0,\ldots,8\} has the four-bit word Ξ²(q)=(q0,q1,q2,q3)\beta(q)=(q_0,q_1,q_2,q_3), with the least significant bit first.✦ A query tag t∈{0,…,7}t\in\{0,\ldots,7\} has nonzero index ΞΉ(t)=t+1\iota(t)=t+1.✦ The tagged embedding Tag⁡q(T,a)\operatorname{Tag}_q(T,a) iterates the signed embeddings, the maps from a carrier to the next carrier selected by the bits of Ξ²(q)\beta(q), using at each step the carrier tower corresponding to the remaining suffix.✦ Its open form substitutes the distinguished variable for aa.✦ For a nonempty finite sign word, the iterated signed embedding first embeds along the remaining suffix and then uses the first sign to select the signed embedding at the carrier depth equal to the suffix length.

For any finite sign word ww, the tag predicate Ο„w,T\tau_{w,T} is an open formula with logical truth at the empty word. For a nonempty word it conjoins the bit predicate, which tests the sign at the current carrier depth, with the polarity selected by the first sign and the recovered tag predicate of the remaining suffix, both at the carrier depth equal to the suffix length; Ο„q,T\tau_{q,T} uses the four-bit word of qq. The recovery operation lifts an open formula through one application of the carrier operation. The iterated recovery predicate Rec⁡n,T(Q)\operatorname{Rec}_{n,T}(Q) starts at the open formula QQ and applies this operation successively over T,CR(T),…,CRnβˆ’1(T)T,C_R(T),\ldots,C_R^{n-1}(T).✦

Fix an odd retained path UU. For tags t,ut,u, a type TT, a term pp of the wrapped type U[T]U[T], a payload c0c_0 of type TT, and a channel input zz, the encoding predicate Qt,T,pQ_{t,T,p}, tagged encoder EtE_t, mark MuM_u, and decoder DD are the constructions in (6). The decoder’s open predicate composes the first path’s observation callback with the zero-tagged variable embedding.✦ Qt,T,p(x)=(Ο„0,T(x)∧LRec⁡4,T(ev⁡U(T,p))(x))∨Lτι(t),T(x),Et(T,p)=BR1(ℬR(T),Qt,T,p),Mu(T,c0,z)=OR1(ℬR(T),z,Tag⁡ΞΉ(u)(T,c0)),D(T,z)=BU(T,x↦OR1(ℬR(T),z,Tag⁡0(T,x))).\begin{aligned} Q_{t,T,p}(x) &=\bigl(\tau_{0,T}(x)\wedge_L \operatorname{Rec}_{4,T}(\operatorname{ev}_U(T,p))(x)\bigr) \vee_L\tau_{\iota(t),T}(x),\\ E_t(T,p)&=B_{R_1}\bigl(\mathcal B_R(T),Q_{t,T,p}\bigr),\\ M_u(T,c_0,z)&=O_{R_1}\bigl(\mathcal B_R(T),z, \operatorname{Tag}_{\iota(u)}(T,c_0)\bigr),\\ D(T,z)&=B_U\bigl(T,x\mapsto O_{R_1}(\mathcal B_R(T),z,\operatorname{Tag}_0(T,x))\bigr). \end{aligned}(6)

Write Ξ“,γ⊩A\Gamma,\gamma\Vdash A when a proof-mode term rr satisfies Ξ“βŠ’r:A\Gamma\vdash r:A.✦ Typed logical equivalence A≃Γ,Ξ³BA\simeq_{\Gamma,\gamma}B is the existence of uniform typed open proof transformers from AA to BB and from BB to AA, in the context Ξ“\Gamma with mode environment Ξ³\gamma.✦

The Claim

Theorem 1. Fix the logical setup LL, a formed double channel RR with input profile II, and a formed odd retained path UU starting at II. Let TT have data mode and be sorted at II in Ξ“\Gamma, and let pp have data mode with Ξ“βŠ’p:U[T]\Gamma\vdash p:U[T]. For a data-mode term c0c_0 with Ξ“βŠ’c0:T\Gamma\vdash c_0:T and tags t,u∈{0,…,7}t,u\in\{0,\ldots,7\}, the mark has the polarity in (7). Ξ“,γ⊩sgn⁡L(t=u,Mu(T,c0,Et(T,p))).\Gamma,\gamma\Vdash \operatorname{sgn}_L\bigl(t=u,\,M_u(T,c_0,E_t(T,p))\bigr).(7)✦ If Ξ“βŠ’T:s\Gamma\vdash T:s for a sort ss, then every data-mode term cc with Ξ“βŠ’c:T\Gamma\vdash c:T satisfies (8). OU(T,D(T,Et(T,p)),c)≃Γ,Ξ³OU(T,p,c).O_U\bigl(T,D(T,E_t(T,p)),c\bigr) \simeq_{\Gamma,\gamma}O_U(T,p,c).(8)✦

What Is Checked

The statements range over labelled typing and its mode discipline, a logical setup with fixed feasible witnesses, and formed retained paths, with equivalence measured by typed open proof transformers.