OctoInformBeta

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

Lemma 39: Encoded predicates evaluate at the rounded logical input up to uniform typed proof transformations

Rounding preserves observations in formed channels.

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 type can be represented along different retained data paths. The comparison concerns formulas obtained by observing a represented value and by testing an encoded predicate against it.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), with arbitrary axiom relation π’œβŠ†SΓ—S\mathcal A\subseteq S\times S and product-rule relation β„›βŠ†SΓ—SΓ—S\mathcal R\subseteq S\times S\times S.✦ Pure 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 attach an argument and result label to each application, abstraction, and product.✦ Erasure deletes these labels.✦ Named variables below denote de Bruijn variables, with index zero the newest variable; contexts are newest-first.

In either syntax, a valid context is obtained from the empty context by adjoining a type AA with Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss. Typing Ξ“βŠ’M:A\Gamma\vdash M:A is the relation generated by the axiom and variable rules, weakening, product formation along β„›\mathcal R, abstraction and application, and conversion to a sorted expected type. In the labelled syntax, abstraction and application use the label of their dependent product.

Full β\beta reduction contracts (λx:A.M)a(\lambda x:A.M)\,a to M[a/x]M[a/x] and acts in every component, including annotations and binder bodies; labelled head contraction requires the application and abstraction to have the same label. Convertibility is the equivalence relation generated by this reduction. A term is normal when it admits no reduction step, and weakly normalizing when finitely many steps reach a normal term. Write M#M^\# for its chosen full normal form when one exists, with a fixed default otherwise.✦

Capture-avoiding renaming acts on free variables and fixes each newly bound variable. Simultaneous substitution replaces free variables by assigned terms, lifting the assignment under binders. Instantiation Q[a/x]Q[a/x] substitutes aa for the distinguished newest variable and lowers the older indices; its single-variable substitution sends zero to aa and n+1n+1 to variable nn. For open terms Q(x)Q(x) and g(x)g(x), their composition Q∘gQ\circ g is Q[g(x)/x]Q[g(x)/x], with ambient variables retained.✦

The modes are data, written 𝖽\mathsf d, and proof, written 𝗉\mathsf p.✦ The labels dddd, dpdp, and pppp have argument and result modes (𝖽,𝖽)(\mathsf d,\mathsf d), (𝖽,𝗉)(\mathsf d,\mathsf p), and (𝗉,𝗉)(\mathsf p,\mathsf p), respectively. A mode assignment Ξ³\gamma assigns a mode to every variable. The mode discipline γ⊒mM:m\gamma\vdash_{\mathrm m}M:m assigns variables their prescribed modes and sorts data mode. An application faf\,a with label ll has the result mode of ll under Ξ³\gamma when ff has that mode and aa has the argument mode of ll under Ξ³\gamma. An abstraction Ξ»x:A.M\lambda x:A.M with label ll has the result mode of ll under Ξ³\gamma when AA has data mode under Ξ³\gamma and MM has the result mode of ll under Ξ³\gamma extended by assigning xx the argument mode of ll. A product has data-mode domain and codomain, with the codomain checked under that extension, and has data mode. A data-only term is one whose constructor labels are all dddd.✦

Sorting at a profile IβŠ†SI\subseteq S is the condition in (1); it permits additional sorting judgments. Sort⁡Ξ“(T,I)β‡”Ξ“βŠ’T:sfor every s∈I.\operatorname{Sort}_{\Gamma}(T,I) \quad\Longleftrightarrow\quad \Gamma\vdash T:s\quad\text{for every }s\in I.(1)✦ The normal form sort profile, axiom profile, and product output profile 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_{\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}(2) A feasible sort profile II is a nonempty set equal to πΔ(N)\pi_{\Delta}(N) for some valid pure context Ξ”\Delta and normal pure term NN.✦ 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).✦

Fix a collection CC of sort profiles. The primary signed graph has positive edges Iβ†’JI\to J for strict inclusions J⊊IJ\subsetneq I between feasible profiles. Each feasible product profile triple (I,J,K)(I,J,K) supplies a negative edge Iβ†’KI\to K and a positive edge Jβ†’KJ\to K. Positive reachability means a finite, possibly empty path using only positive edges.✦ An observation layer II is a 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 for which (I,J,K)(I,J,K) is a feasible product profile triple with J,K∈CJ,K\in C.✦ A logical terminal profile JJ is a profile occurring in a feasible product profile 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) assigns a type and a value to every profile. At every feasible II, the type TIT_I is data-only, its erasure is normal, and Sort⁡Ξ“(TI,I)\operatorname{Sort}_{\Gamma}(T_I,I) holds; also Ξ“βŠ’vI:TI\Gamma\vdash v_I:T_I, and both TIT_I and vIv_I have data mode under Ξ³\gamma.

Logical Formulas

A mode-preserving context embedding e:(Ξ“,Ξ³)β†’(Ξ”,Ξ΄)e:(\Gamma,\gamma)\to(\Delta,\delta) is a variable renaming into a valid context Ξ”\Delta that preserves each variable’s type and mode.✦ Context lookup assigns the variable at index nn its declared type with every free index raised by n+1n+1, accounting for its own declaration and the nn newer declarations.✦

Proof mode inhabitation of a formula AA means that some pp satisfies Ξ“βŠ’p:A\Gamma\vdash p:A and γ⊒mp:𝗉\gamma\vdash_{\mathrm m}p:\mathsf p.✦ A typed open proof transformer from AA to BB is a term tt with p:A,Ξ“βŠ’t:Bp:A,\Gamma\vdash t:B in proof mode, where the temporary variable pp has proof mode and BB is weakened into the extended context.✦ Write Tr⁡Ξ“,Ξ³(A,B)\operatorname{Tr}_{\Gamma,\gamma}(A,B) for the existence of such a transformer. Typed logical equivalence is the relation in (3). A≃Γ,Ξ³B⇔Tr⁡Ξ“,Ξ³(A,B)∧Tr⁡Ξ“,Ξ³(B,A).A\simeq_{\Gamma,\gamma}B \quad\Longleftrightarrow\quad \operatorname{Tr}_{\Gamma,\gamma}(A,B) \ \land\ \operatorname{Tr}_{\Gamma,\gamma}(B,A).(3)✦

A proof wrapper Ο‰\omega is a finite sequence of positive and negative extensions, starting with the identity, each extension retaining one term.✦ Relative to WW and CC, its path starts at a profile II. Its current target JJ may be restricted to any subset without changing the wrapper. A triple (A,J,K)(A,J,K) permits a positive extension to KK retaining TAT_A; a triple (J,B,K)(J,B,K) permits a negative extension retaining TBT_B when J,K∈CJ,K\in C. The parity is the number of negative extensions modulo two. A wrapper contains a negative step precisely when at least one extension is negative.✦

A quantifier wrapper route ρ\rho for a base bb and domain II consists of a feasible triple (I,J,K)(I,J,K) and even proof wrapper paths from bb to JJ and from KK to bb.✦ An ambient logical calculus LL consists of a witness family WW with typed open proof transformers between TJT_J and TJβ€²T_{J'} for every pair of logical terminal profiles. It also chooses a feasible triple (d,b,k)(d,b,k) with d,b,k∈Cd,b,k\in C, even proof wrapper paths from bb to dd and from kk to bb, and a quantifier wrapper route for every direct observation layer.

A witness continuation for a term FF is the following condition: after every mode-preserving context embedding and for every logical terminal profile JJ, the existence of a typed open proof transformer from the renamed FF to the renamed TJT_J entails proof mode inhabitation of that renamed TJT_J.✦ Stable witness extraction for FF means that after every such embedding, a witness continuation for the renamed FF entails proof mode inhabitation of the renamed FF itself.✦

An interpretable formula FF for LL is a term sorted at bb, of data mode, that admits stable witness extraction.✦ A stable formula family Q(x)Q(x) over a type TT is an open term such that, after every mode-preserving context embedding ee, each data-mode argument aa with Ξ”βŠ’a:e(T)\Delta\vdash a:e(T) gives an interpretable instance e(Q)[a/x]e(Q)[a/x] for the transported calculus.✦ The renaming e(Q)e(Q) fixes its distinguished variable and renames the ambient variables. Transport along ee renames the witness types and values, transports the typed open proof transformers between terminal witness types, and renames the proof wrappers and quantifier routes. It preserves the base, domain, and product profiles, their feasible product profile triple, and their membership in CC.

Data Paths and Channels

A positive data path rr is a finite sequence of positive steps, each retaining a chosen type and dummy value.✦ Relative to WW, it starts with the identity at II, permits restriction of the current target JJ to any subset, and extends to KK along a triple (A,J,K)(A,J,K) using (TA,vA)(T_A,v_A).✦

A data path tail UU consists of a sort sUs_U, a positive data path, and encoding and decoding proof wrappers. It is formed relative to LL with endpoint BB when {sU}∈C\{s_U\}\in C, Ax⁡(sU)\operatorname{Ax}(s_U) is nonempty, its positive path is formed from that axiom profile to BB, and its encoding and decoding proof paths are formed with even parity from bb to {sU}\{s_U\} and back, respectively. The decoding path must contain a negative step.

A retained data path rr is a path that starts with the identity and is extended by positive steps retaining a type and dummy value, or negative steps retaining a data path tail.✦ Its parity counts negative steps modulo two. A formed retained data path rr relative to LL is a retained data path that starts at II, permits restriction of its current target JJ to a subset, and admits a positive extension to KK along (A,J,K)(A,J,K) with retained terms (TA,vA)(T_A,v_A). A negative extension to KK uses a feasible product profile triple (J,B,K)(J,B,K) and a formed data path tail relative to LL ending at BB.

The wrapped type r[T]r[T] is TT at the identity. A positive step with annotation DD replaces the preceding wrapped type by the data function type from DD to that type; a negative step replaces it by the data function type from that type to the tail’s carrier. The builder Br(T,a)B_r(T,a) returns aa at the identity and forms a constant data abstraction at a positive step. At a negative step, it abstracts over the preceding wrapped type, observes that bound input against aa, and sends the resulting formula through the tail’s encoding. Capture-avoiding shifts preserve the distinguished input when aa is a callback.

The observation Or(T,w,a)O_r(T,w,a) instantiates aa by ww at the identity. At a positive step it applies ww to the retained dummy value and observes the result along the preceding path. At a negative step it applies ww to the argument built along the preceding path from aa, then reads the result through the tail’s decoding. Renaming a data path renames its retained terms and tails and preserves its steps.✦

For an odd path rr, the observation callback cr(T,w)c_r(T,w) is the open term in (4). Reencoding from an odd path rr to an odd path rβ€²r' is the builder expression in the same display. cr(T,w)(x)=Or(T,w,x),Er,rβ€²(T,w)=Brβ€²(T,cr(T,w)).c_r(T,w)(x)=O_r(T,w,x),\qquad E_{r,r'}(T,w)=B_{r'}\bigl(T,c_r(T,w)\bigr).(4) The open reencoding er,rβ€²(T;x)e_{r,r'}(T;x) is Er,rβ€²(T,x)E_{r,r'}(T,x) with xx distinguished and all ambient variables weakened.✦

An observation channel R=(rβ„“,rr,rp)R=(r_{\ell},r_{\mathrm r},r_{\mathrm p}) consists of odd logical, raw, and predicate data paths.✦ It is formed from II through profiles J,K,HJ,K,H when those paths are formed from II to JJ, from II to KK, and from KK to HH, respectively.✦ Its logical and raw types, conversions, and roundtrip are defined in (5). Tβ„“=rβ„“[T],Tr=rr[T],toRaw⁡(T,y)=Erβ„“,rr(T,y),toLog⁡(T,c)=Err,rβ„“(T,c),round⁡(T,y)=toLog⁡(T,toRaw⁡(T,y)).\begin{aligned} T_{\ell}&=r_{\ell}[T],& T_{\mathrm r}&=r_{\mathrm r}[T],\\ \operatorname{toRaw}(T,y)&=E_{r_{\ell},r_{\mathrm r}}(T,y),& \operatorname{toLog}(T,c)&=E_{r_{\mathrm r},r_{\ell}}(T,c),\\ \operatorname{round}(T,y) &=\operatorname{toLog}\bigl(T,\operatorname{toRaw}(T,y)\bigr). \end{aligned}(5) The encoded predicate and channel evaluation are the expressions in (6), using open composition for the callback supplied to the predicate builder. pred⁡(T,Q)=Brp(Tr,Q∘err,rβ„“(T;x)),eval⁡(T,p,y)=Orp(Tr,p,toRaw⁡(T,y)).\begin{aligned} \operatorname{pred}(T,Q) &=B_{r_{\mathrm p}}\bigl(T_{\mathrm r}, Q\circ e_{r_{\mathrm r},r_{\ell}}(T;x)\bigr),\\ \operatorname{eval}(T,p,y) &=O_{r_{\mathrm p}}\bigl(T_{\mathrm r},p, \operatorname{toRaw}(T,y)\bigr). \end{aligned}(6)

The Claim

Theorem 1. Let LL be an ambient logical calculus in (Ξ“,Ξ³)(\Gamma,\gamma), and let RR be a formed observation channel from II through J,K,HJ,K,H. Suppose Sort⁡Ξ“(T,I)\operatorname{Sort}_{\Gamma}(T,I) holds, TT has data mode, and Ξ“βŠ’y:Tβ„“\Gamma\vdash y:T_{\ell} with yy of data mode. For every data-mode term aa with Ξ“βŠ’a:T\Gamma\vdash a:T, the observation law (7) holds: Orβ„“(T,round⁡(T,y),a)≃Γ,Ξ³Orβ„“(T,y,a).O_{r_{\ell}}\bigl(T,\operatorname{round}(T,y),a\bigr) \simeq_{\Gamma,\gamma} O_{r_{\ell}}(T,y,a).(7)✦ Suppose additionally that Ξ“βŠ’Tr:s\Gamma\vdash T_{\mathrm r}:s for some sort ss, and that Q(x)Q(x) is a stable formula family over Tβ„“T_{\ell}. Then the evaluation law (8) holds: eval⁡(T,pred⁡(T,Q),y)≃Γ,Ξ³Q[round⁡(T,y)/x].\operatorname{eval}\bigl(T,\operatorname{pred}(T,Q),y\bigr) \simeq_{\Gamma,\gamma} Q[\operatorname{round}(T,y)/x].(8)✦

What Is Checked

The statements concern formed observation channels relative to an ambient logical calculus, profile-sorted data-mode types and typed data-mode inputs; predicate evaluation additionally requires a sort for the raw channel type and a stable formula family over the logical channel type.

Renaming along a mode-preserving context embedding preserves witness normality, sorting, typing, and data modes.