OctoInformBeta

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

Lemma 42: Bottom payloads and tagged queries in a double data channel

Tests of dummy and point 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

The observations of a double data channel are data terms, while their tests are formulas inhabited in proof mode. A dummy test asks about an observation; a marker test asks about its predicate payload. Point queries also take a supplied data predicate.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) with arbitrary axiom and product-rule relations. Terms are built from variables and sorts by application, annotated abstraction λx:A.M\lambda x:A.M, and dependent product Πx:A.B\Pi x:A.B.✦ Labelled terms attach one of the argument and result labels 𝖽𝖽\mathsf{dd}, 𝖽𝗉\mathsf{dp} and 𝗉𝗉\mathsf{pp} to these constructors, for data to data, data to proof, and proof to proof respectively. Erasure deletes the labels.✦ Named variables are used below; the underlying indices are de Bruijn indices, with zero denoting the newest variable, and contexts are newest-first.

In a context Γ\Gamma, typing is written Γ⊢M:A\Gamma\vdash M:A for the subject MM and expected type AA. It uses the axiom and product-rule relations, variable introduction and weakening, annotated abstraction, application, and conversion. Full β\beta reduction contracts a labelled application of an abstraction with the same label and allows reduction in every annotation and binder body.✦ Convertibility is the least equivalence relation containing this reduction.✦ Substitution is capture-avoiding; under a binder, renaming fixes the newest variable and shifts the renamed older variables. Instantiation substitutes for the newest variable and lowers the older indices.✦ The open composition f∘gf\circ g of open terms ff and gg in a common ambient context is the open term obtained by substituting gg for the distinguished input of ff, preserving that context.✦ Renaming acts uniformly on the fixed annotations of all paths and logical codes.

A normal term has no β\beta reduct.✦ For a weakly normalizing unlabelled term TT, write T#T^\# for its chosen reachable normal form.✦ For a sort ss and sets I,JI,J of sorts, the normal form sort profile of TT, the axiom successors of ss, and the product output profile of I,JI,J are πΓ(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 is a nonempty set I=πΔ(A)I=\pi_\Delta(A) for some normal term AA in a valid context Δ\Delta.✦ A valid context starts empty and extends by a type having a sort in the preceding context.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J) in (1).✦ For labelled terms, sorting at II means Sorted⁡I(T)⇔Γ⊢T:sfor every s∈I.\operatorname{Sorted}_I(T) \quad\Longleftrightarrow\quad \Gamma\vdash T:s\quad\text{for every }s\in I.(2)✦

Let γ\gamma assign data or proof mode to each variable. Write 𝖽γ(M)\mathsf d_\gamma(M) when MM has data mode under γ\gamma, and 𝗉γ(M)\mathsf p_\gamma(M) when it has proof mode. Variables take their assigned modes and sorts have data mode. Applications use the argument and result modes of their label. Abstraction annotations have data mode, and bodies have the result mode under extension by the argument mode. Product domains and codomains have data mode under the corresponding binder extension. A data-only term has label 𝖽𝖽\mathsf{dd} at every constructor.✦

Proof-mode inhabitation Pr⁡Γ,γ(A)\operatorname{Pr}_{\Gamma,\gamma}(A) means that some pp satisfies Γ⊢p:A\Gamma\vdash p:A and 𝗉γ(p)\mathsf p_\gamma(p).✦ A typed open proof transformer from AA to BB is a proof-mode term of expected type BB in the context extended by a temporary proof input of type AA.✦ Typed logical equivalence A≃Γ,γBA\simeq_{\Gamma,\gamma}B means that uniform such transformers exist in both directions.✦

Logical Paths and Data Payloads

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

A fixed feasible witness family WW chooses a type TIT_I and value vIv_I at each profile. At every feasible II, the type is data-only, its erasure is normal, and it is sorted at II; moreover Γ⊢vI:TI\Gamma\vdash v_I:T_I, and both chosen terms have data mode under γ\gamma.

A proof wrapper is a finite path with fixed annotations. Its identity leaves a formula unchanged. The nondependent labelled arrow is a dependent product whose codomain omits the new variable; a positive extension with annotation DD replaces a wrapped formula FF by D→𝖽𝗉FD\to_{\mathsf{dp}}F, and a negative extension with annotation EE replaces it by F→𝗉𝗉EF\to_{\mathsf{pp}}E. Formation starts at the identity, permits restriction of the target profile, and extends along feasible product triples. A positive step along (A,J,K)(A,J,K) retains TAT_A and preserves parity. A negative step along (J,B,K)(J,B,K) retains TBT_B, requires J,K∈CJ,K\in C, and reverses parity. Parity counts negative steps modulo two; containing a negative step is a separate condition.

A logical setup LL consists of a feasible witness family WW and typed open proof converters between the witness types at any two logical terminal profiles. It has a feasible triple (d,b,k)(d,b,k) with d,b,k∈Cd,b,k\in C, an even input proof path from bb to dd, and an even output proof path from kk to bb. For each direct observation layer II, its 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 is the witness type ⊥L=Tb\bot_L=T_b; together with the input wrapper in⁡L\operatorname{in}_L and output wrapper out⁡L\operatorname{out}_L it determines the logical operation code. Its operations are A⇒LB=out⁡L[in⁡L[A]→𝗉𝗉B],¬LA=A⇒L⊥L,⊤L=⊥L⇒L⊥L,A∧LB=¬L(A⇒L¬LB),A∨LB=¬L(¬LA∧L¬LB).\begin{aligned} A\Rightarrow_L B &=\operatorname{out}_L[ \operatorname{in}_L[A]\to_{\mathsf{pp}}B],& \neg_L A&=A\Rightarrow_L\bot_L,\\ \top_L&=\bot_L\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). \end{aligned}(3)

A positive data path starts at the identity and has only positive extensions, each retaining a witness annotation and its original dummy value.✦ A formed positive path starts at a specified profile, permits target restriction, and extends along feasible triples (A,J,K)(A,J,K) using TA,vAT_A,v_A.✦

A data path tail ending at JJ consists of a sort ss with {s}∈C\{s\}\in C and nonempty Ax⁡(s)\operatorname{Ax}(s), a formed positive data path from Ax⁡(s)\operatorname{Ax}(s) to JJ, an even encoding proof path from bb to {s}\{s\}, and an even decoding proof path back to bb. The decoding path contains a negative step. A retained data path is a path generated by identity, positive extensions with a fixed annotation and dummy value, and negative extensions with a fixed data path tail.✦ Identity has even parity, and positive extensions preserve parity. Its formation permits target restriction; positive extensions use (A,J,K)(A,J,K) and the witnesses at AA, whereas negative extensions use (J,B,K)(J,B,K) and a formed tail ending at BB.

For a retained path VV, write V[T]V[T] for its wrapped data type, ℬV(T;a)\mathcal B_V(T;a) for its builder, and 𝒪V(T;w,a)\mathcal O_V(T;w,a) for observation. Identity gives TT, aa, and substitution of ww into the distinguished input of aa, respectively. A positive extension with annotation DD and dummy ee gives the arrow D→𝖽𝖽V[T]D\to_{\mathsf{dd}}V[T]; its builder is a constant annotated data abstraction, and its observation applies ww to ee before continuing along VV. A negative extension gives the data arrow from V[T]V[T] to its tail’s carrier. Its builder abstracts a wrapped input, observes it along VV against aa, and sends the resulting formula through the tail. Its observation applies ww to the recursively built argument and reads the result through that tail. Negative extensions reverse parity.

For an odd path VV, a wrapped input ww, and a data point cc of type TT, the evaluation and contravariant observation callbacks are the one-input open terms eV,T,w[x]=𝒪V(T;w,x),kV,T,c[x]=𝒪V(T;x,c).e_{V,T,w}[x]=\mathcal O_V(T;w,x), \qquad k_{V,T,c}[x]=\mathcal O_V(T;x,c).(4) The ambient variables are shifted beneath the fresh input in (4).

A double channel R=(R1,R2)R=(R_1,R_2) consists of two odd retained data paths.✦ Formation from II through JJ to KK means that R1R_1 is formed from II to JJ and R2R_2 from JJ to KK.✦ The carrier operation 𝒞R\mathcal C_R of the double channel RR wraps a data type first along R1R_1 and then along R2R_2. Its iterated and fourfold carriers, and its predicate payload type, are 𝒞R0(T)=T,𝒞Rn+1(T)=𝒞R(𝒞Rn(T)),HT=𝒞R4(T),BT=R1[HT].\mathcal C_R^0(T)=T,\qquad \mathcal C_R^{n+1}(T)=\mathcal C_R(\mathcal C_R^n(T)),\qquad H_T=\mathcal C_R^4(T),\qquad B_T=R_1[H_T].(5)

Queries at the fourfold carrier of (5) have indices q∈{0,…,8}q\in\{0,\ldots,8\}, whose bit strings list the binary digits in positions zero through three in that order.✦ A marker tag t∈{0,…,7}t\in\{0,\ldots,7\} has nonzero query index t+1t+1.✦ The tagged embedding ιq(T,c)\iota_q(T,c) is a data term obtained from cc by successively applying the one-stage embedding of the double channel for bit zero or bit one, as prescribed by that four-bit string. The empty signed embedding leaves its input unchanged; each preceding bit adds the corresponding one-stage signed embedding at the carrier depth of the remaining string. The tagged variable embedding is ιq(T,x)\iota_q(T,x) as an open term in xx.✦

Write Qq,T[x]Q_{q,T}[x] for the tag predicate of the query bit string. The empty tag predicate is ⊤L\top_L. Each preceding bit conjoins the predicate that distinguishes that bit, or its logical negation for a false bit, with the predicate recovered from the remaining tag after one stage at the appropriate carrier depth. The iterated recovery predicate Rec⁡Tn(F)\operatorname{Rec}_T^n(F) starts at FF and adds one recovery stage at each successor depth.✦

Fix the odd retained data path UU used for supplied predicates. For a predicate payload bpbp of type BTB_T, the decoding callback dT,bpd_{T,bp}, payload decoder, and decoding map are dT,bp[x]=𝒪R1(HT;bp,ι0(T,x)),Dec⁡U(T,bp)=ℬU(T;dT,bp),δU,T[x]=Dec⁡U(T,x).\begin{aligned} d_{T,bp}[x]&=\mathcal O_{R_1}(H_T;bp,\iota_0(T,x)),\\ \operatorname{Dec}_U(T,bp)&=\mathcal B_U(T;d_{T,bp}),\\ \delta_{U,T}[x]&=\operatorname{Dec}_U(T,x). \end{aligned}(6) For a supplied data predicate pp of type U[T]U[T], the encoding predicate Et,T,pE_{t,T,p} and tagged payload encoder are Et,T,p=(Q0,T∧LRec⁡T4(eU,T,p))∨LQt+1,T,Enc⁡t(T,p)=ℬR1(HT;Et,T,p).\begin{aligned} E_{t,T,p} &=(Q_{0,T}\wedge_L\operatorname{Rec}_T^4(e_{U,T,p})) \vee_L Q_{t+1,T},\\ \operatorname{Enc}_t(T,p)&=\mathcal B_{R_1}(H_T;E_{t,T,p}). \end{aligned}(7)

The bottom predicate payload and dummy observation are constant-formula builds along the two paths: ⊥Tbp=ℬR1(HT;⊥L),Dummy⁡T=ℬR2(BT;⊤L).\bot_T^{\mathrm{bp}}=\mathcal B_{R_1}(H_T;\bot_L), \qquad \operatorname{Dummy}_T=\mathcal B_{R_2}(B_T;\top_L).(8) For an observation oo and a reference data point c0c_0 of type TT, the dummy predicate, marker test, and tagged query are the observations IsDummy⁡T(o)=𝒪R2(BT;o,⊥Tbp),Mark⁡t(T,c0;bp)=𝒪R1(HT;bp,ιt+1(T,c0)),Query⁡t(T;o,p)=𝒪R2(BT;o,Enc⁡t(T,p)).\begin{aligned} \operatorname{IsDummy}_T(o) &=\mathcal O_{R_2}(B_T;o,\bot_T^{\mathrm{bp}}),\\ \operatorname{Mark}_t(T,c_0;bp) &=\mathcal O_{R_1}(H_T;bp,\iota_{t+1}(T,c_0)),\\ \operatorname{Query}_t(T;o,p) &=\mathcal O_{R_2}(B_T;o,\operatorname{Enc}_t(T,p)). \end{aligned}(9) The marking predicate body is the open term Mt,T,c0[x]=Mark⁡t(T,c0;x)M_{t,T,c_0}[x]=\operatorname{Mark}_t(T,c_0;x) from (9).✦

An encoded data point uses marker tag seven and the decoding map (6). Its predicate body ΦT,c0,c\Phi_{T,c_0,c} and point observation are ΦT,c0,c=M7,T,c0∧L(kU,T,c∘δU,T),Point⁡U(T,c0,c)=ℬR2(BT;ΦT,c0,c).\begin{aligned} \Phi_{T,c_0,c}&=M_{7,T,c_0}\wedge_L(k_{U,T,c}\circ\delta_{U,T}),\\ \operatorname{Point}_U(T,c_0,c) &=\mathcal B_{R_2}(B_T;\Phi_{T,c_0,c}). \end{aligned}(10)

The Claim

Theorem 1. Let LL be the logical setup and RR the formed double channel used above. Let TT be sorted at II as in (2), with 𝖽γ(T)\mathsf d_\gamma(T). The dummy law is (11): PrΓ,γ(IsDummy⁡T(Dummy⁡T)).\operatorname{Pr}_{\Gamma,\gamma} \bigl(\operatorname{IsDummy}_T(\operatorname{Dummy}_T)\bigr).(11)✦

Let c0c_0 satisfy Γ⊢c0:T\Gamma\vdash c_0:T and 𝖽γ(c0)\mathsf d_\gamma(c_0). For every marker tag t∈{0,…,7}t\in\{0,\ldots,7\}, the bottom payload law is (12): PrΓ,γ(¬LMark⁡t(T,c0;⊥Tbp)).\operatorname{Pr}_{\Gamma,\gamma} \bigl(\neg_L\operatorname{Mark}_t(T,c_0;\bot_T^{\mathrm{bp}})\bigr).(12)✦

Let cc also satisfy Γ⊢c:T\Gamma\vdash c:T and 𝖽γ(c)\mathsf d_\gamma(c). Choose sorts s,rs,r with Γ⊢T:s\Gamma\vdash T:s and Γ⊢BT:r\Gamma\vdash B_T:r. For the point defined in (10), the non-dummy law is (13): PrΓ,γ(¬LIsDummy⁡T(Point⁡U(T,c0,c))).\operatorname{Pr}_{\Gamma,\gamma} \bigl(\neg_L\operatorname{IsDummy}_T (\operatorname{Point}_U(T,c_0,c))\bigr).(13)✦

Under these same assumptions, let pp satisfy Γ⊢p:U[T]\Gamma\vdash p:U[T] and 𝖽γ(p)\mathsf d_\gamma(p). The point query law is (14): Query⁡7(T;Point⁡U(T,c0,c),p)≃Γ,γ𝒪U(T;p,c).\operatorname{Query}_7(T;\operatorname{Point}_U(T,c_0,c),p) \simeq_{\Gamma,\gamma}\mathcal O_U(T;p,c).(14)✦

What Is Checked

The statements are over labelled typing and the data and proof mode discipline, the logical setup and formed double channel, and the displayed constructions of payloads and observations, with the explicit sorting witnesses for TT and BTB_T and the typing assumptions on the supplied data terms.