OctoInformBeta

OpenAI preprint, September 2026 Β· Β§9. The guarded diagonal argument

Proposition 56: A parity-matched channel return supplies the source type and the required carrier identities

Formed specialized observations inhabit the logical terminal.

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 specialization of the guarded diagonal construction uses three tagged copies of a data type and an ambient logical calculus. The types assigned to those copies must agree with the data paths used by the 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.✦ Labelled terms attach to each application, abstraction, and product one of the labels dddd, dpdp, and pppp, whose argument and result modes are respectively data/data, data/proof, and proof/proof. Variable names are source notation for indices counted from zero at the nearest binder; contexts are written newest first. Label erasure deletes every label✦, and a data-only term has label dddd at every labelled constructor.✦

Write Ξ“βŠ’M:A\Gamma\vdash M:A for typing in PP, using its axiom, variable, weakening, product, abstraction, application, and conversion rules. In labelled typing, application uses the label of the function’s product type. Full Ξ²\beta reduction contracts (Ξ»x:A.M)N(\lambda x:A.M)\,N to the capture-avoiding substitution M[N/x]M[N/x] and closes under every term component, including annotations and binder bodies✦; labelled head contraction requires matching application and abstraction labels. In either syntax, Ξ²\beta convertibility is the equivalence relation generated by this reduction. A Ξ²\beta normal form is a term that admits no step of full Ξ²\beta reduction, and a weakly normalizing term MM is a term that reaches a Ξ²\beta normal form in finitely many steps, possibly zero; write M#M^\# for its chosen normal form.

A mode environment Ξ³\gamma assigns data or proof mode to each variable. Write γ⊒M:m\gamma\vdash M:m for the mode discipline: variables have their assigned modes, sorts have data mode, and applications and abstractions respect their labels’ argument and result modes. An abstraction’s annotation has data mode; both parts of a product have data mode, and the product has data mode. Binder bodies are considered in the environment extended by the label’s argument mode. Proof-mode inhabitation of a labelled type AA means that some qq satisfies both Ξ“βŠ’q:A\Gamma\vdash q:A and γ⊒q:proof\gamma\vdash q:\mathrm{proof}.✦

Profiles and Logical Interpretation

For pure terms, a valid context is obtained from the empty context by adjoining a type that has some sort in the preceding context.✦ For a pure context Ξ“\Gamma, a term TT having a normal form, a sort s∈Ss\in S, and sets I,JβŠ†SI,J\subseteq S, the normal form sort profile πΓ(T)\pi_\Gamma(T), axiom profile Ax⁡(s)\operatorname{Ax}(s), and product output profile Out⁡(I,J)\operatorname{Out}(I,J) 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βŠ†SI\subseteq S realized as πΔ(T)\pi_\Delta(T) by a Ξ²\beta normal term TT in a valid context Ξ”\Delta.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of three feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦

The primary signed graph has a positive edge Iβ†’JI\to J for a strict inclusion J⊊IJ\subsetneq I of 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 is the relation between profiles defined by the existence of a finite, possibly empty path using only positive edges in the primary signed graph.✦ Fix a collection CC of profiles. An observation layer II for a collection CC of profiles is a profile positively reachable in the primary signed graph 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 for a collection CC of profiles is a profile that admits a feasible triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

Sorting a labelled type AA at II means Ξ“βŠ’A:s\Gamma\vdash A:s for every s∈Is\in I; additional sorts are permitted.✦ A fixed feasible witness family W=(FI,vI)IW=(F_I,v_I)_I assigns types and values to profiles. At every feasible II, the type FIF_I is data-only, its erasure is Ξ²\beta normal, and the conditions in (2) hold. Ξ“βŠ’FI:s(s∈I),Ξ“βŠ’vI:FI,γ⊒FI:data,γ⊒vI:data.\Gamma\vdash F_I:s\quad(s\in I),\qquad \Gamma\vdash v_I:F_I,\qquad \gamma\vdash F_I:\mathrm{data},\qquad \gamma\vdash v_I:\mathrm{data}.(2)✦

A proof wrapper is a finite sequence of positive and negative extensions, each with a fixed labelled annotation, starting from the identity wrapper.✦ Its formation relative to W,CW,C specifies source and target profiles and parity. The identity has even parity; restricting a target to a subset changes neither wrapper nor parity. A positive extension along a feasible triple (A,J,K)(A,J,K) changes target JJ to KK and records FAF_A. A negative extension along (J,B,K)(J,B,K) records FBF_B, requires J,K∈CJ,K\in C, and changes parity. Parity counts negative extensions modulo two.

A typed open proof transformer from AA to BB is a term of type BB in x:A,Ξ“x:A,\Gamma that has proof mode when xx is assigned proof mode; the ambient variables in BB are renamed to avoid capture.✦ An ambient logical calculus LL fixes WW and such transformers between every ordered pair of logical terminal witness types. It chooses a feasible triple (d,b,c)(d,b,c) with d,b,c∈Cd,b,c\in C, an even proof wrapper from bb to dd, and an even proof wrapper from cc to bb. For every direct observation layer II, it chooses a quantifier route: a feasible triple (I,J,K)(I,J,K), an even proof wrapper from bb to JJ, and an even proof wrapper from KK to bb. All these proof wrappers have formation relative to W,CW,C. The logical falsity witness of LL is the type FbF_b.✦

Retained Data Paths

A positive data path Ο…\upsilon is an expression generated from the identity by extensions Ο…+(D,e)\upsilon^+(D,e), each retaining a domain DD and a distinguished argument ee.✦ The wrapped type Ο…[T]\upsilon[T] and projection of a positive data path Ο…\upsilon are defined in (3), where Aβ†’ddBA\to_{dd}B is the nondependent product with data argument and data result. id[T]=T,Ο…+(D,e)[T]=Dβ†’ddΟ…[T],pr⁡id(w)=w,pr⁡Ο…+(D,e)(w)=pr⁡Ο…(wdde).\begin{aligned} \mathrm{id}[T]&=T,& \upsilon^+(D,e)[T]&=D\to_{dd}\upsilon[T],\\ \operatorname{pr}_{\mathrm{id}}(w)&=w,& \operatorname{pr}_{\upsilon^+(D,e)}(w) &=\operatorname{pr}_{\upsilon}(w\,_{dd}e). \end{aligned}(3) Formation of a positive path relative to WW starts at the identity, permits target restriction to a subset, and extends along a feasible triple (A,J,K)(A,J,K) using (D,e)=(FA,vA)(D,e)=(F_A,v_A) to change target JJ to KK.✦

A data path tail U=(u,Ο…U,Qe,Qd)U=(u,\upsilon_U,Q_e,Q_d) consists of a sort, a positive data path, and encoding and decoding proof wrappers.✦ The carrier of a data path tail U=(u,Ο…U,Qe,Qd)U=(u,\upsilon_U,Q_e,Q_d) is Ucar=Ο…U[u]U_{\mathrm{car}}=\upsilon_U[u].✦ Formation of UU at nn requires {u}∈C\{u\}\in C, Ax⁡(u)β‰ βŒ€\operatorname{Ax}(u)\ne\varnothing, and formation of Ο…U\upsilon_U from Ax⁡(u)\operatorname{Ax}(u) to nn. The wrappers Qe,QdQ_e,Q_d must be formed even proof paths from bb to {u}\{u\} and back, respectively, and the decoding wrapper QdQ_d must contain a negative extension.

A retained data path rr is an expression generated from the identity by positive extensions r+(D,e)r^+(D,e) and negative extensions rβˆ’(U)r^-(U).✦ Positive extensions preserve parity and negative extensions reverse it. The wrapped type of a retained data path rr is defined in (4). id[T]=T,r+(D,e)[T]=Dβ†’ddr[T],rβˆ’(U)[T]=r[T]β†’ddUcar.\mathrm{id}[T]=T,\qquad r^+(D,e)[T]=D\to_{dd}r[T],\qquad r^-(U)[T]=r[T]\to_{dd}U_{\mathrm{car}}.(4) Formation of a retained data path rr relative to LL permits identity, target restriction to a subset, and positive extensions using the same witnesses as positive paths. A negative extension along a feasible triple (J,B,K)(J,B,K) changes target JJ to KK and uses a formed tail ending at BB. Write r;qr;q for concatenation in path order, so that (r;q)[T]=q[r[T]](r;q)[T]=q[r[T]] and the parities add modulo two.✦

A double data channel D=(r1,r2)D=(r_1,r_2) consists of two odd retained paths.✦ A double data channel D=(r1,r2)D=(r_1,r_2) is formed from II through JJ to KK when its two paths are formed at those successive endpoints.✦ The double wrapper carrier CDC_D, iterated carriers CDmC_D^m for mβ‰₯0m\geq0, predicate code type HDH_D, and parameter type PDP_D of a double data channel DD are given in (5); the fourfold carrier is CD4(T)C_D^4(T). CD(T)=r2[r1[T]],CD0(T)=T,CDm+1(T)=CD(CDm(T)),HD(T)=r1[CD4(T)],PD(T)=r2[HD(T)].\begin{aligned} C_D(T)&=r_2[r_1[T]],& C_D^0(T)&=T,& C_D^{m+1}(T)&=C_D(C_D^m(T)),\\ H_D(T)&=r_1[C_D^4(T)],& P_D(T)&=r_2[H_D(T)]. \end{aligned}(5)

Probes and Specialized Observations

A uniform probe QQ is a tuple consisting of a seed sort ss, an initial path Ξ±\alpha of parity Ξ΅\varepsilon, odd raw and back paths ρ,Ο„\rho,\tau, an even function path Ο†\varphi, a positive lifting path Ο…\upsilon, and a tail UU.✦ Formation of a uniform probe QQ at (I,J,k,p,n,g)(I,J,k,p,n,g) requires feasible triples (I,J,k)(I,J,k) and (p,n,g)(p,n,g), a nonempty Ax⁡(s)\operatorname{Ax}(s), a formed tail ending at nn, and the path endpoints in (6); the lifting path has formation relative to WW and the other paths relative to LL. pathαρτφυsource{s}kpgAx⁡(s)targetkpkJI\begin{array}{c|ccccc} \text{path}&\alpha&\rho&\tau&\varphi&\upsilon\\ \hline \text{source}&\{s\}&k&p&g&\operatorname{Ax}(s)\\ \text{target}&k&p&k&J&I \end{array}(6)✦

The probe double wrapper is DQ=(Ο„,ρ)D_Q=(\tau,\rho).✦ The probe domain D0D_0, raw type, parameter type, single bundle type, function type, codomain family, and common carrier VQV_Q are defined in (7). Ambient paths and annotations under the binder are renamed without capture. D0=Ο…[s],raw⁡Q(A)=ρ[Ξ±[A]],par⁡Q(A)=PDQ(raw⁡Q(A)),single⁡Q(A)=CDQ(par⁡Q(A)),fun⁡Q(A)=single⁡Q(A)β†’ddUcar,body⁡Q(x)=Ο†[fun⁡Q(pr⁡Ο…(x))],VQ=Ξ ddx:D0.body⁡Q(x).\begin{aligned} D_0&=\upsilon[s],& \operatorname{raw}_Q(A)&=\rho[\alpha[A]],\\ \operatorname{par}_Q(A)&=P_{D_Q}(\operatorname{raw}_Q(A)),& \operatorname{single}_Q(A)&=C_{D_Q}(\operatorname{par}_Q(A)),\\ \operatorname{fun}_Q(A)&=\operatorname{single}_Q(A)\to_{dd}U_{\mathrm{car}},& \operatorname{body}_Q(x)&=\varphi[ \operatorname{fun}_Q(\operatorname{pr}_\upsilon(x))],\\ V_Q&=\Pi^{dd}x:D_0.\operatorname{body}_Q(x). \end{aligned}(7)

An observation channel consists of odd logical, raw, and predicate paths (Ο‡,ρ,ψ)(\chi,\rho,\psi).✦ It is formed at (k,j,p,h)(k,j,p,h) when these paths run respectively from kk to jj, from kk to pp, and from pp to hh✦; its logical channel type at TT is Ο‡[T]\chi[T].✦ A shared relational code E=(Q,Ο‡,ψ)E=(Q,\chi,\psi) is a triple consisting of a uniform probe QQ and logical and predicate paths Ο‡,ψ\chi,\psi, whose observation channel (Ο‡,ρ,ψ)(\chi,\rho,\psi) uses the raw path ρ\rho of QQ. A shared relational code E=(Q,Ο‡,ψ)E=(Q,\chi,\psi) is formed at (I,J,k,p,n,g,j,h)(I,J,k,p,n,g,j,h) when its probe and channel have formation at the indicated profiles.✦ The relational base type of a shared relational code E=(Q,Ο‡,ψ)E=(Q,\chi,\psi) at AA is Ξ±[A]\alpha[A], where Ξ±\alpha is the initial path of QQ.✦

Tagged copy syntax consists of odd source and first paths r0,r1r_0,r_1 and double channels Di,DoD_i,D_o.✦ Its first copy, middle copy, and three-copy carrier are defined in (8). Y1(T)=r1[T],Y2(T)=CDi(Y1(T)),Y3(T)=CDo(Y2(T)).Y_1(T)=r_1[T],\qquad Y_2(T)=C_{D_i}(Y_1(T)),\qquad Y_3(T)=C_{D_o}(Y_2(T)).(8) A three-copy observation code O=(E,Di,Do)O=(E,D_i,D_o) uses r0=Ο‡r_0=\chi and r1=ρr_1=\rho; its observation carrier is Y=Y3(VQ)Y=Y_3(V_Q).✦ A three-copy observation code O=(E,Di,Do)O=(E,D_i,D_o) is formed when EE is formed, DiD_i is formed from pp through kk to pp, and DoD_o is formed from pp through kk to jj.✦

A specialized code B=(O,A0)B=(O,A_0) is a pair consisting of a three-copy observation code OO and a type A0A_0.✦ The underlying relational code of a specialized code B=(O,A0)B=(O,A_0) is EE, its specialized base type is X=Ξ±[A0]X=\alpha[A_0]✦, and its tagged observation type is YY.✦ Write π–₯π—ˆπ—‹π—†L(B;I,J,k,p,n,g,j,h)\mathsf{Form}_L(B;I,J,k,p,n,g,j,h) when OO is formed and the seed sorting, data-mode condition, and carrier identities in (9) hold. Here ro,1,ro,2r_{o,1},r_{o,2} are the first and second paths of DoD_o. Ξ“βŠ’A0:s,γ⊒A0:data,Y=Ο‡[X],ro,2=Ο‡,ro,1[Y2(VQ)]=X.\begin{gathered} \Gamma\vdash A_0:s,\qquad \gamma\vdash A_0:\mathrm{data},\\ Y=\chi[X],\qquad r_{o,2}=\chi,\qquad r_{o,1}[Y_2(V_Q)]=X. \end{gathered}(9)

The Channel Return

A fixed channel configuration KK is a formed shared relational code at (I,J,k,p,n,g,j,h)(I,J,k,p,n,g,j,h) whose logical and predicate profiles j,hj,h are direct observation layers.✦ Its access probe, double code, and relational code are QQ, DQD_Q, and EE. A parity-matched channel return Οƒ\sigma for KK is a retained data path formed from kk to {s}\{s\} with the same parity Ξ΅\varepsilon as Ξ±\alpha.✦ The even return loop, outer odd wrapper, outer double channel, source type, and specialized source code of a parity-matched channel return Οƒ\sigma for a fixed channel configuration KK are defined in (10); its inner double channel is DQD_Q.✦ eΟƒ=Οƒ;Ξ±,rΟƒ=Ο„;eΟƒ,Do,Οƒ=(rΟƒ,Ο‡),AΟƒ=Οƒ[Ο„[ρ[Ο„[ρ[VQ]]]]],BΟƒ=((E,DQ,Do,Οƒ),AΟƒ).\begin{aligned} e_\sigma&=\sigma;\alpha,& r_\sigma&=\tau;e_\sigma,& D_{o,\sigma}&=(r_\sigma,\chi),\\ A_\sigma&=\sigma[\tau[\rho[\tau[\rho[V_Q]]]]],& B_\sigma&=((E,D_Q,D_{o,\sigma}),A_\sigma). \end{aligned}(10)

The Claim

Theorem 1. Let LL be an ambient logical calculus in Ξ“\Gamma with mode environment Ξ³\gamma. Let KK be a fixed channel configuration at (I,J,k,p,n,g,j,h)(I,J,k,p,n,g,j,h) and let Οƒ\sigma be a parity-matched channel return for KK. Then π–₯π—ˆπ—‹π—†L(BΟƒ;I,J,k,p,n,g,j,h).\mathsf{Form}_L(B_\sigma;I,J,k,p,n,g,j,h).(11)✦

Theorem 2. Let LL be an ambient logical calculus in Ξ“\Gamma with mode environment Ξ³\gamma, and let BB be a specialized code formed relative to LL at profiles (I,J,k,p,n,g,j,h)(I,J,k,p,n,g,j,h). There is a term qq with Ξ“βŠ’q:Fb,γ⊒q:proof.\Gamma\vdash q:F_b,\qquad \gamma\vdash q:\mathrm{proof}.(12)✦

In the paper, the result reads: the specialized relational construction yields a proof of βŠ₯=Fb\bot=F_b in the ambient labelled context.

What Is Checked

The source formation statement (11) and the inhabitation statement (12) are stated over labelled typing, the mode discipline, a fixed feasible witness family and ambient logical calculus, and the retained channel paths with their profile and carrier conditions.