OctoInformBeta

OpenAI preprint, September 2026 · §8. Relational coding of the diagonal argument

Lemma 44: Equivalence and congruence for guarded predicate comparisons in formed observation channels

Observation laws relate inputs to channel rounding.

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 observational relation compares data through predicate evaluations in a logical calculus. A formula selects the predicates to be tested. Channel rounding sends a logical value through a raw channel and then back to its logical channel.

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.✦ Writing dd for data mode and pp for proof mode, labelled terms attach the argument and result modes dddd, dpdp, or pppp to each application, abstraction and product.✦ Bound names below denote terms whose variables use de Bruijn indices; contexts list the newest declaration first. Label erasure |M||M| deletes the labels.✦

The typing judgment Γ⊢M:A\Gamma\vdash M:A uses the axiom and product rules of PP, variable introduction and weakening, abstraction and application, and conversion.✦ For labelled terms, application and abstraction use the label of their product type. Full β\beta reduction contracts (λx:A.M)N(\lambda x:A.M)\,N by capture-avoiding substitution and reduces every annotation and binder body; labelled contraction requires matching labels. Convertibility is the equivalence relation generated by these steps. A valid context Γ\Gamma is a context obtained from the empty context by adjoining a type having some sort in the preceding context.✦

A mode assignment γ\gamma gives each variable its mode. Sorts have data mode. An application has the result mode of its label when its function has that result mode and its argument has the argument mode of the label. An abstraction has a data-mode annotation and a body of its result mode under extension by its argument mode. A dependent product has data mode when its domain has data mode in the original mode assignment and its codomain has data mode under extension by the argument mode of its label. A data-only term MM is a term with label dddd at every constructor.✦

Profiles and the Logical Calculus

A weakly normalizing term TT is a term that reaches a term with no full β\beta step in finitely many steps.✦ For a weakly normalizing term TT, write T#T^{\#} for its chosen normal form. The normal form sort profile, axiom successors and product outputs are the sets 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 is a nonempty set I=πΔ(A)I=\pi_\Delta(A) for a normal term AA in a valid context Δ\Delta.✦ 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).✦ A labelled type AA in context Γ\Gamma is sorted at a profile II when Γ⊢A:s\Gamma\vdash A:s for every s∈Is\in I.✦

Fix a collection CC of profiles. In the primary signed graph, proper restriction between feasible profiles is positive. A feasible triple (I,J,K)(I,J,K) gives a negative edge from II to KK and a positive edge from JJ to KK. An observation layer II is a feasible profile reachable by a finite, possibly empty, positive path 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 product profile triple with codomain JJ and with its domain and output in CC.✦

A fixed feasible witness family WW chooses a type TIT_I and value vIv_I at every feasible profile II. The type is data-only, |TI||T_I| is normal, and TIT_I is sorted at II; both TIT_I and vIv_I have data mode, and Γ⊢vI:TI\Gamma\vdash v_I:T_I.✦ A typed open proof transformer A⇝BA\rightsquigarrow B is a proof-mode term tt with x:A,Γ⊢t:Bx:A,\Gamma\vdash t:B, where BB is weakened into the extended context and xx has proof mode.✦ Proof-mode inhabitation and typed logical equivalence have the meanings in (2): Γ;γ⊩A⇔some proof-mode p satisfies Γ⊢p:A,A≃Γ,γB⇔(A⇝B)and(B⇝A).\begin{aligned} \Gamma;\gamma\Vdash A &\quad\Longleftrightarrow\quad \text{some proof-mode }p\text{ satisfies }\Gamma\vdash p:A,\\ A\simeq_{\Gamma,\gamma}B &\quad\Longleftrightarrow\quad (A\rightsquigarrow B)\ \text{and}\ (B\rightsquigarrow A). \end{aligned}(2)

A mode-preserving context embedding ee from a context Γ\Gamma into a valid context Γe\Gamma_e is a variable renaming that preserves each variable’s renamed type and mode.✦ Renaming and simultaneous substitution avoid capture by fixing a newly bound variable and shifting the images of older ones; instantiation substitutes for the newest variable and lowers the older indices. A witness continuation cc for AA is an operation that, after every mode-preserving context embedding ee and at each logical terminal profile JJ, takes a transformer A[e]⇝TJ[e]A[e]\rightsquigarrow T_J[e] to proof-mode inhabitation of TJ[e]T_J[e].✦ Stable witness extraction for AA means that, after every embedding ee into a context Γe\Gamma_e with mode assignment γe\gamma_e, a witness continuation for A[e]A[e] yields Γe;γe⊩A[e]\Gamma_e;\gamma_e\Vdash A[e].✦

An ambient logical calculus LL has the witness family WW and transformers between its witness types at any two terminal profiles. Its domain dd, base bb and output kk belong to CC and form a feasible triple (d,b,k)(d,b,k). A formed proof path VV is a path that starts with the identity at a set of sorts and is built from target restrictions to arbitrary subsets and positive and negative extensions along feasible product profile triples; VV is even when its number of negative extensions is even. Fix even proof paths from bb to dd and from kk to bb. A quantifier route KK at a direct observation layer II is a feasible triple with domain II, together with even proof paths from bb to its codomain and from its output to bb; choose one at every direct observation layer.✦ An interpretable formula AA is a data-mode term sorted at bb and admitting stable witness extraction.✦ A stable formula family QQ over a type DD is a one-variable open term whose instance at every data-mode argument Γe⊢a:D[e]\Gamma_e\vdash a:D[e], after every embedding ee, is an interpretable formula for the transported calculus.✦ All witness types, values and paths are renamed along the same embedding.

Retained Paths and Guarded Observation

A proof wrapper V[−]V[-] is generated from the identity by positive and negative extensions.✦ For a domain witness type DD in a positive extension and a codomain witness type FF in a negative extension, application is given by (3), where A→lBA\to_l B is the nondependent labelled product with label ll: id[A]=A,(V+D)[A]=D→dpV[A],(V−F)[A]=V[A]→ppF.\mathrm{id}[A]=A,\qquad (V+D)[A]=D\to_{dp}V[A],\qquad (V-F)[A]=V[A]\to_{pp}F.(3)✦ A negative extension requires the preceding target and new output to lie in CC.

A positive data path VV is a path that retains a domain type and its chosen dummy value at each positive extension.✦ Its formed paths start with the identity at II, allow target restriction from JJ to any subset, and extend from JJ to KK along a feasible triple (A,J,K)(A,J,K) using TA,vAT_A,v_A.✦ A data tail UU over SS consists of a sort ss, a positive data path, and encoding and decoding proof wrappers.✦ It is formed at a target JJ when {s}∈C\{s\}\in C, Ax⁡(s)\operatorname{Ax}(s) is nonempty, its positive path is formed from Ax⁡(s)\operatorname{Ax}(s) to JJ, and its encoding and decoding paths are formed from bb to {s}\{s\} and back with even parity, with a negative step in the decoding path.✦ A retained data path VV is a path generated by the identity, positive extensions retaining domain types and their chosen dummy values, and negative extensions retaining a data tail.✦ Its formed paths start with the identity at II and allow target restriction. A positive extension follows a feasible triple (A,J,K)(A,J,K) from JJ to KK, retaining TA,vAT_A,v_A; a negative extension follows a feasible triple (J,B,K)(J,B,K) using a formed tail ending at BB. Parity counts negative extensions modulo two.

For a retained data path VV and a type TT, write V[T]V[T] for the wrapped type. For a term ww of type V[T]V[T] and a one-variable observation callback qq, write 𝖡V(T;q)\mathsf B_V(T;q) for its builder and 𝖮V(T,w;q)\mathsf O_V(T,w;q) for observation. The identity returns TT, returns qq, and substitutes ww into the distinguished input of qq, respectively. A positive step forms a data arrow into the preceding wrapped type; its builder is a constant data abstraction, and observation applies ww to the retained dummy value before continuing. A negative step forms a data arrow from the preceding wrapped type to its tail carrier. Its builder abstracts over the preceding wrapped type and sends the inner observation through the tail; observation applies ww to the inner builder and reads through the tail. For odd paths V,V′V,V', reencoding uses the observation term with one free variable in (4): enc⁡V,V′(T,w)=𝖡V′(T;x↦𝖮V(T,w;x)).\operatorname{enc}_{V,V'}(T,w) =\mathsf B_{V'}\bigl(T;\ x\mapsto\mathsf O_V(T,w;x)\bigr).(4)✦

The logical operations of LL use falsity ⊥=Tb\bot=T_b and its fixed incoming and outgoing proof wrappers VinV_{\mathrm{in}} and VoutV_{\mathrm{out}}. Their definitions are (5): A⇒LB=Vout[Vin[A]→ppB],¬LA=A⇒L⊥,A∧LB=¬L(A⇒L¬LB),A⇔LB=(A⇒LB)∧L(B⇒LA).\begin{aligned} A\Rightarrow_L B &=V_{\mathrm{out}}[V_{\mathrm{in}}[A]\to_{pp}B],& \neg_L A&=A\Rightarrow_L\bot,\\ A\wedge_L B&=\neg_L(A\Rightarrow_L\neg_L B),& A\Leftrightarrow_L B &=(A\Rightarrow_L B)\wedge_L(B\Rightarrow_L A). \end{aligned}(5) A quantifier route KK has incoming and outgoing wrappers defining the universal and guarded universal formulas in (6): ∀Kx:D.Q(x)=Kout[Πdpx:D.Kin[Q(x)]],∀Kx:D∣G(x).Q(x)=∀Kx:D.(G(x)⇒LQ(x)).\begin{aligned} \forall^K x:D.\,Q(x) &=K_{\mathrm{out}}[\Pi_{dp}x:D.\,K_{\mathrm{in}}[Q(x)]],\\ \forall^K x:D\mid G(x).\,Q(x) &=\forall^K x:D.\,(G(x)\Rightarrow_L Q(x)). \end{aligned}(6) Wrappers under binders are renamed into the extended context, retaining their annotations and step signs. The guard implication callback is the logical implication from the open guard GG to the open body QQ, with the logical operations renamed under their common binder.✦

An observation channel RR consists of odd retained paths Rlog,Rraw,RpredR_{\mathrm{log}},R_{\mathrm{raw}},R_{\mathrm{pred}}.✦ Formed channels have paths from II to JJ, from II to K0K_0, and from K0K_0 to HH, respectively, relative to LL.✦ Their types and operations are (7): YT=Rlog[T],XT=Rraw[T],𝒫T=Rpred[XT],raw⁡T(y)=enc⁡Rlog,Rraw(T,y),log⁡T(c)=enc⁡Rraw,Rlog(T,c),round⁡T(y)=log⁡T(raw⁡T(y)),ev⁡T(p,y)=𝖮Rpred(XT,p;raw⁡T(y)).\begin{aligned} Y_T&=R_{\mathrm{log}}[T],& X_T&=R_{\mathrm{raw}}[T],& \mathcal P_T&=R_{\mathrm{pred}}[X_T],\\ \operatorname{raw}_T(y) &=\operatorname{enc}_{R_{\mathrm{log}},R_{\mathrm{raw}}}(T,y),&&&\\ \operatorname{log}_T(c) &=\operatorname{enc}_{R_{\mathrm{raw}},R_{\mathrm{log}}}(T,c),&&&\\ \operatorname{round}_T(y)&=\operatorname{log}_T(\operatorname{raw}_T(y)),&&&\\ \operatorname{ev}_T(p,y) &=\mathsf O_{R_{\mathrm{pred}}}(X_T,p;\operatorname{raw}_T(y)).&&& \end{aligned}(7) Here YTY_T is the logical channel type. Wrapping TT along the raw path RrawR_{\mathrm{raw}} gives the raw channel type XTX_T.✦ The type 𝒫T\mathcal P_T is the channel predicate type. The map raw⁡T\operatorname{raw}_T is raw channel encoding. The map log⁡T\operatorname{log}_T is logical channel encoding. The predicate evaluation callback at yy is the open term that evaluates the newly bound predicate at yy over TT, with the channel, type and element renamed under the predicate binder.✦

For a stable formula family GG over 𝒫T\mathcal P_T, a quantifier route KPK_P at HH and data-mode terms y,z:YTy,z:Y_T, the observation relation ℰG(y,z)\mathcal E_G(y,z) is the guarded comparison in (8). The pointwise observational comparison at yy and zz is the encoded logical equivalence between their predicate evaluation callbacks, with logical operations renamed under the predicate binder.✦ ℰG(y,z)=∀KPp:𝒫T∣G(p).(ev⁡T(p,y)⇔Lev⁡T(p,z)).\mathcal E_G(y,z)= \forall^{K_P}p:\mathcal P_T\mid G(p).\, \bigl(\operatorname{ev}_T(p,y)\Leftrightarrow_L \operatorname{ev}_T(p,z)\bigr).(8)✦ For a quantifier route KYK_Y at JJ, a stable formula family QQ over 𝒫T\mathcal P_T and a channel predicate p:𝒫Tp:\mathcal P_T, the roundtrip invariance formula Resp⁡T(p)\operatorname{Resp}_T(p) and the admissible predicate formula Good⁡Q(p)\operatorname{Good}_Q(p) are defined by (9): Resp⁡T(p)=∀KYy:YT.(ev⁡T(p,y)⇔Lev⁡T(p,round⁡T(y))),Good⁡Q(p)=Resp⁡T(p)∧LQ(p).\begin{aligned} \operatorname{Resp}_T(p) &=\forall^{K_Y}y:Y_T.\, \bigl(\operatorname{ev}_T(p,y)\Leftrightarrow_L \operatorname{ev}_T(p,\operatorname{round}_T(y))\bigr),\\ \operatorname{Good}_Q(p)&=\operatorname{Resp}_T(p)\wedge_L Q(p). \end{aligned}(9) The roundtrip invariance callback of pp is the encoded logical equivalence between its evaluation at the newly bound element and its evaluation after that element’s channel roundtrip, with the parameters renamed under the element binder.✦

The Claim

Theorem 1. Let LL be an ambient logical calculus and let RR have formed observation channels from II through J,K0,HJ,K_0,H. Let TT have data mode and be sorted at II. Choose a quantifier route KPK_P at HH and a stable formula family GG over 𝒫T\mathcal P_T.

For every data-mode term Γ⊢y:YT\Gamma\vdash y:Y_T, reflexivity is (10): Γ;γ⊩ℰG(y,y).\Gamma;\gamma\Vdash\mathcal E_G(y,y).(10)✦ Let y,zy,z have data mode and type YTY_T in Γ\Gamma, and suppose Γ;γ⊩ℰG(y,z)\Gamma;\gamma\Vdash\mathcal E_G(y,z). Symmetry is (11): Γ;γ⊩ℰG(z,y).\Gamma;\gamma\Vdash\mathcal E_G(z,y).(11)✦ Let y,z,wy,z,w have data mode and type YTY_T in Γ\Gamma. Suppose both ℰG(y,z)\mathcal E_G(y,z) and ℰG(z,w)\mathcal E_G(z,w) are inhabited in proof mode. Transitivity is (12): Γ;γ⊩ℰG(y,w).\Gamma;\gamma\Vdash\mathcal E_G(y,w).(12)✦ Choose also a quantifier route KYK_Y at JJ and a stable formula family QQ over 𝒫T\mathcal P_T. For every data-mode term Γ⊢y:YT\Gamma\vdash y:Y_T, roundtrip relatedness is (13): Γ;γ⊩ℰGood⁡Q(y,round⁡T(y)).\Gamma;\gamma\Vdash \mathcal E_{\operatorname{Good}_Q}(y,\operatorname{round}_T(y)).(13)✦ Let a,a′,c,c′a,a',c,c' have data mode and type YTY_T in Γ\Gamma, and suppose ℰG(a,a′)\mathcal E_G(a,a') and ℰG(c,c′)\mathcal E_G(c,c') are inhabited in proof mode. The congruence law is the typed logical equivalence in (14): ℰG(a,c)≃Γ,γℰG(a′,c′).\mathcal E_G(a,c)\simeq_{\Gamma,\gamma}\mathcal E_G(a',c').(14)✦

What Is Checked

The claims are stated over labelled typing and the mode discipline, with formed retained channels, an ambient logical calculus and stable formula families; their inhabitation and equivalence conclusions use proof-mode terms and uniform typed open proof transformers. Renaming along a mode-preserving context embedding preserves the witness family’s sorting, typing, normality and modes, and transports the logical calculus and its quantifier routes while preserving their profiles and feasible product profile triples.