OctoInformBeta

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

Lemma 50: Elimination is uniform under mode-preserving context embeddings

Class and edge rules from tagged witnesses.

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 relational diagonal construction has source, left, and right tagged copies x0,xβ„“,xrx^0,x^\ell,x^r of each probe element. Class membership and incidence between tagged observations are formulas of its ambient logical calculus.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), a valid context Ξ“\Gamma, and a mode assignment Ξ³\gamma. The axiom and product-rule relations are arbitrary. Terms have annotated abstractions and dependent products, with application and binder labels specifying data and proof modes. The mode judgment γ⊒M:𝖽\gamma\vdash M:\mathsf d assigns data mode to MM, and γ⊒M:𝗉\gamma\vdash M:\mathsf p assigns proof mode; annotations and both parts of a product have data mode. Data typing and proof-mode inhabitation are the assertions in (1). π’ŸΞ“,Ξ³(M:A)⇔(Ξ“βŠ’M:A)∧(γ⊒M:𝖽),𝒫Γ,Ξ³(F)β‡”βˆƒp((Ξ“βŠ’p:F)∧(γ⊒p:𝗉)).\begin{aligned} \mathcal D_{\Gamma,\gamma}(M:A) &\Longleftrightarrow (\Gamma\vdash M:A)\land(\gamma\vdash M:\mathsf d),\\ \mathcal P_{\Gamma,\gamma}(F) &\Longleftrightarrow \exists p\,\bigl((\Gamma\vdash p:F)\land (\gamma\vdash p:\mathsf p)\bigr). \end{aligned}(1)

A feasible profile II of the pure type specification PP is a nonempty set of all sorts typing a normal type in a valid context; normality uses full Ξ²\beta reduction, including annotations and binder bodies.✦ A feasible product triple (I,J,K)(I,J,K) has three feasible profiles and K=Out⁡(I,J)K=\operatorname{Out}(I,J), where Out⁡(I,J)\operatorname{Out}(I,J) consists of all cc with (a,b,c)βˆˆβ„›(a,b,c)\in\mathcal R for some a∈Ia\in I, b∈Jb\in J. The normal form sort profile πΓ(T)\pi_\Gamma(T) is the set of all sorts ss for which Ξ“βŠ’T#:s\Gamma\vdash T^\#:s, where T#T^\# is the chosen full Ξ²\beta normal form when TT is weakly normalizing.✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) is the set of sorts tt with (s,t)βˆˆπ’œ(s,t)\in\mathcal A.✦ The primary signed graph has feasible sort profiles as vertices, positive inclusion edges from II to each feasible proper subset JJ, and, for every feasible product triple (I,J,K)(I,J,K), a negative edge from II to KK and a positive edge from JJ to KK.✦ Positive reachability in a signed graph is reachability along a finite, possibly empty path consisting entirely of positive edges.✦ An ambient logical calculus LL has a fixed collection CC of feasible profiles, domain, base, and product profiles d,b,k∈Cd,b,k\in C forming a feasible product triple (d,b,k)(d,b,k), an even incoming proof path from bb to dd, and an even outgoing proof path from kk to bb. The existential quantifier of the logical calculus LL is βˆƒx:T.F=Β¬βˆ€x:T.Β¬F\exists x:T.\,F=\neg\forall x:T.\,\neg F✦; formula equivalence F↔GF\leftrightarrow G in LL is the conjunction of the implications in both directions. These equivalences mean uniform typed proof-term transformers. A typed open transformer pp from FF to GG in the logical calculus LL is a proof-mode term of type GG in the context extended by a proof-mode variable of type FF.✦ The calculus fixes a witness type TIT_I and inhabitant vIv_I at every feasible profile II, with Ξ“βŠ’TI:s\Gamma\vdash T_I:s for every s∈Is\in I and Ξ“βŠ’vI:TI\Gamma\vdash v_I:T_I, and both have data mode under Ξ³\gamma. Each TIT_I is data-only and its label erasure is in full Ξ²\beta normal form; there are typed open transformers between the witness types at any two terminal profiles. For the fixed collection CC of profiles of LL, a terminal profile JJ is a feasible profile belonging to a feasible product triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦ An observation layer is a profile positively reachable in the primary signed graph from a nonempty axiom profile Ax⁡(s)\operatorname{Ax}(s) with {s}∈C\{s\}\in C.✦ A direct observation layer II of LL is an observation layer for which a feasible product triple (I,J,K)(I,J,K) has J,K∈CJ,K\in C.✦ A quantifier route for a domain profile II and logical base bb chooses a feasible product triple (I,J,K)(I,J,K), an even incoming proof path from bb to JJ, and an even outgoing proof path from KK to bb.✦ The falsity type of LL is its witness type at bb, and LL supplies a quantifier route for every direct observation layer, including the quantifiers βˆ€Y\forall_Y and βˆ€P\forall_P used here.

A mode-preserving context embedding e:(Ξ“,Ξ³)β†’(Ξ”,Ξ΄)e:(\Gamma,\gamma)\longrightarrow(\Delta,\delta) is a variable renaming into a valid context which assigns each renamed source variable its renamed type and preserves its mode.✦ A witness continuation for a formula FF of LL is the condition that, under every mode-preserving context embedding and for every terminal witness type, a typed open transformer from the renamed FF to that witness type entails proof-mode inhabitation of the witness type.✦ Stable witness extraction for a formula FF of LL is the condition that a witness continuation yields proof-mode inhabitation of FF under every mode-preserving context embedding.✦ An interpretable formula FF of LL is a data-mode term sorted at every sort of the logical base profile bb and admitting stable witness extraction.✦ Write FeF_e for renaming along ee; subscripts ee on types and operations transport all their fixed parameters as well.

Observations and Structural Queries

A specialized relational coding BB fixes a chosen type AA and a three-copy observation system OO.✦ The underlying relational coding has a common probe carrier HH and a shared observation channel with logical, raw, and predicate paths Dlog,Draw,DpredD_{\mathrm{log}},D_{\mathrm{raw}},D_{\mathrm{pred}}, each of odd parity. A retained data path DD is a finite succession of positive and negative type wrappers from the identity; its parity counts negative extensions modulo two.✦ The raw path is shared with the probe. The inner and outer double channels each consist of two successive odd retained data paths; let 𝒲in,𝒲out\mathcal W_{\mathrm{in}},\mathcal W_{\mathrm{out}} denote their carrier operations and Dout,1,Dout,2D_{\mathrm{out},1},D_{\mathrm{out},2} the two outer paths. Writing D(T)D(T) for a path’s action on a type, the specialized base type, probe element type, observation type, and two predicate types are defined in (2); DinitD_{\mathrm{init}} is the probe’s initial path. TB=Dinit(A),X=Dlog(H),M=𝒲in(Draw(H)),Y=𝒲out(M),𝒱=Dpred(Draw(TB)),ℐ=Dpred(Draw(H)).\begin{gathered} T_B=D_{\mathrm{init}}(A),\qquad X=D_{\mathrm{log}}(H),\\ M=\mathcal W_{\mathrm{in}}(D_{\mathrm{raw}}(H)),\qquad Y=\mathcal W_{\mathrm{out}}(M),\\ \mathcal V=D_{\mathrm{pred}}(D_{\mathrm{raw}}(T_B)),\qquad \mathcal I=D_{\mathrm{pred}}(D_{\mathrm{raw}}(H)). \end{gathered}(2)

A positive data path is a finite succession of positive extensions from the identity, each retaining a domain annotation and a fixed dummy argument.✦ A data path tail consists of a sort, a positive data path from that sort, and fixed encoding and decoding proof paths.✦ Its carrier is the positive wrapper of the sort; encoding first follows the encoding proof path and then the positive injection, while decoding first takes the positive projection and then follows the decoding proof path. The data path builder along a retained path returns its argument at the identity and adds a constant data abstraction at a positive extension. At a negative extension it abstracts over the inner wrapped type, observes the bound input against the supplied argument, and encodes the resulting formula through the tail. Data path observation along the identity substitutes the wrapped input into the supplied formula body. At a positive extension it applies the input to the retained dummy argument before continuing along the inner path; at a negative extension it applies the input to the argument constructed by the inner data path builder and decodes the result through the tail.

For a probe element x:Xx:X and a tag t∈{0,β„“,r}t\in\{0,\ell,r\}, the tagged copy xtx^t is the observation obtained by reencoding xx from the logical path to the raw path and embedding it in the inner and outer channels with respective bits t=β„“t=\ell and t=rt=r.✦ For y:Yy:Y, let bin(y)b_{\mathrm{in}}(y) and bout(y)b_{\mathrm{out}}(y) be the recovered inner and outer marker formulas. For i:ℐi:\mathcal I, the observation obs⁡(i,y)\operatorname{obs}(i,y) recovers the payload through these channels against the uniform predicate probe for ii.✦ Tagged observational equivalence yβ‰ˆzy\approx z between observations y,z:Yy,z:Y is the formula in (3). yβ‰ˆz=(bin(y)↔bin(z))∧((bout(y)↔bout(z))βˆ§βˆ€Pi:ℐ.(obs⁡(i,y)↔obs⁡(i,z))).\begin{aligned} y\approx z={}& \bigl(b_{\mathrm{in}}(y)\leftrightarrow b_{\mathrm{in}}(z)\bigr)\land{}\\ &\bigl(\bigl(b_{\mathrm{out}}(y)\leftrightarrow b_{\mathrm{out}}(z)\bigr)\land \forall_P i:\mathcal I.\, (\operatorname{obs}(i,y)\leftrightarrow \operatorname{obs}(i,z))\bigr). \end{aligned}(3)✦

The signed payload embedding in a double channel builds along its second path from the observation of the payload along its first path, using that observation when the bit is true and its logical negation when the bit is false.✦ Double channel evaluation observes an input along the second path against the data path builder along the first path applied to the supplied formula body.✦ The encoded bit observation in a double channel is double channel evaluation against the constant truth body.✦ The outer marker is this bit observation on the outer channel at the middle copy type.✦ Signed payload recovery is the logical conditional whose guard is the encoded bit observation, whose true branch is double channel evaluation against the supplied body, and whose false branch is its logical negation.✦ The inner marker recovers the inner bit observation through the outer channel.✦ The logical conditional with guard GG and branches FF and HH is the disjunction of GG conjoined with FF and the negation of GG conjoined with HH.✦

Channel evaluation ev⁡(v,y)\operatorname{ev}(v,y) observes a predicate vv along the predicate path against the raw reencoding of yy. At base HH, write ev⁡H(i,x)\operatorname{ev}_H(i,x) for the same operation. The probe order observation iβ‰Όxi\preceq x observes xx along the logical path against the uniform predicate probe for ii.✦ Probe element equivalence on XX is the relation in which two probe elements have equivalent order observations for every i:ℐi:\mathcal I✦, while predicate equivalence on ℐ\mathcal I is the relation in which two predicates have equivalent ev⁡H\operatorname{ev}_H evaluations at every x:Xx:X.✦ The extensionality condition Ext⁡(i)\operatorname{Ext}(i) for a predicate i:ℐi:\mathcal I is the requirement that ev⁡H(i,βˆ’)\operatorname{ev}_H(i,-) respect probe element equivalence.✦ The validity condition Valid⁡(x)\operatorname{Valid}(x) for a probe element x:Xx:X is the requirement that βˆ’β‰Όx-\preceq x respect predicate equivalence.✦

For a formula body F(w)F(w), write [w↦F(w)][w\mapsto F(w)] for the channel predicate with that body at the indicated base type. The left copy predicate rv=[x↦ev⁡(v,xβ„“)]r_v=[x\mapsto\operatorname{ev}(v,x^\ell)] has base HH.✦ For t∈{0,β„“,r}t\in\{0,\ell,r\}, the observation invariance, class representation, edge representation, and relational closure properties of v:𝒱v:\mathcal V are defined in (4). 𝖦(v)=βˆ€Yy:Y.βˆ€Yz:Y.(yβ‰ˆzβ†’(ev⁡(v,y)↔ev⁡(v,z))),𝖒t(v)=βˆƒx:X.βˆ€Yw:Y.(ev⁡(v,w)↔wβ‰ˆxt),𝖀t(v)=βˆƒx:X.βˆ€Yw:Y.(ev⁡(v,w)↔((wβ‰ˆx0)∨(wβ‰ˆxt))),𝖱(v)=Ext⁡(rv)β†’βˆ€Yx:X.(Valid⁡(x)β†’(ev⁡(v,xr)β†’rvβ‰Όx)).\begin{aligned} \mathsf G(v)&=\forall_Y y:Y.\,\forall_Y z:Y.\, \bigl(y\approx z\to (\operatorname{ev}(v,y)\leftrightarrow\operatorname{ev}(v,z))\bigr),\\ \mathsf C_t(v)&=\exists x:X.\,\forall_Y w:Y.\, \bigl(\operatorname{ev}(v,w)\leftrightarrow w\approx x^t\bigr),\\ \mathsf E_t(v)&=\exists x:X.\,\forall_Y w:Y.\, \bigl(\operatorname{ev}(v,w)\leftrightarrow ((w\approx x^0)\lor(w\approx x^t))\bigr),\\ \mathsf R(v)&=\operatorname{Ext}(r_v)\to \forall_Y x:X.\,\bigl(\operatorname{Valid}(x)\to (\operatorname{ev}(v,x^r)\to r_v\preceq x)\bigr). \end{aligned}(4)

The structural parameter m0m_0 is the probe double-channel realization with a constant truth marker and seven branches, in order 𝖦,𝖒0,𝖒ℓ,𝖒r,𝖀ℓ,𝖀r,𝖱\mathsf G,\mathsf C_0,\mathsf C_\ell,\mathsf C_r, \mathsf E_\ell,\mathsf E_r,\mathsf R from (4). Let Qj(v)Q_j(v) be the structural query of the parameter m0m_0 at index j∈{0,…,6}j\in\{0,\ldots,6\}, instantiated with vv.✦ The channel roundtrip ρ(y)\rho(y) sends yy to the raw channel and back to the logical channel.✦ Roundtrip invariance Resp⁡(v)\operatorname{Resp}(v) and the actual specialized admissibility guard Adm⁡(v)\operatorname{Adm}(v) are defined in (5). Resp⁡(v)=βˆ€Yy:Y.(ev⁡(v,y)↔ev⁡(v,ρ(y))),Adm⁡(v)=Resp⁡(v)∧Q0(v).\begin{aligned} \operatorname{Resp}(v)&= \forall_Y y:Y.\, (\operatorname{ev}(v,y)\leftrightarrow \operatorname{ev}(v,\rho(y))),\\ \operatorname{Adm}(v)&= \operatorname{Resp}(v)\land Q_0(v). \end{aligned}(5)

The specialized observational relation ∼\sim on YY is the relation that tests exactly the predicates admitted by the guard in (5): y∼z=βˆ€Pv:𝒱.(Adm⁡(v)β†’(ev⁡(v,y)↔ev⁡(v,z))).y\sim z= \forall_P v:\mathcal V.\, \bigl(\operatorname{Adm}(v)\to (\operatorname{ev}(v,y)\leftrightarrow\operatorname{ev}(v,z))\bigr).(6)✦

The equivalence class predicate Ο‡y\chi_y and class union predicate Ο‡y,z\chi_{y,z} are channel predicates at base TBT_B formed from (6), with the bodies in (7). The coded class predicate Is⁡t\operatorname{Is}_t selects the class query tag t+1t+1, with 0,β„“,r0,\ell,r numbered 0,1,20,1,2; the coded edge predicate TtT_t uses edge query tag Ο΅(β„“)=4\epsilon(\ell)=4 or Ο΅(r)=5\epsilon(r)=5. Ο‡y=[w↦w∼y],Ο‡y,z=[w↦(w∼y)∨(w∼z)],Is⁡t(y)=Qt+1(Ο‡y),Tt(y,z)=Is⁡0(y)∧(Is⁡t(z)∧QΟ΅(t)(Ο‡y,z)),t∈{β„“,r}.\begin{aligned} \chi_y&=[w\mapsto w\sim y],\qquad \chi_{y,z}=[w\mapsto (w\sim y)\lor(w\sim z)],\\ \operatorname{Is}_t(y)&=Q_{t+1}(\chi_y),\\ T_t(y,z)&=\operatorname{Is}_0(y)\land \bigl(\operatorname{Is}_t(z)\land Q_{\epsilon(t)}(\chi_{y,z})\bigr), \qquad t\in\{\ell,r\}. \end{aligned}(7)

The Claim

Theorem 1. Assume that BB is formed relative to LL: its probe, shared observation channel, and inner and outer double channels have their prescribed path formations, its chosen type AA has data-mode typing at the sort fixed by its probe, and its carrier identities are Y=Dlog(TB)Y=D_{\mathrm{log}}(T_B), Dout,2=DlogD_{\mathrm{out},2}=D_{\mathrm{log}}, and Dout,1(M)=TBD_{\mathrm{out},1}(M)=T_B.✦ Every observation argument yy or zz has data typing at YY in (Ξ“,Ξ³)(\Gamma,\gamma). In the elimination rules, DD is an interpretable formula.

For t∈{0,β„“,r}t\in\{0,\ell,r\}, class introduction and elimination have the forms (8) and (9). In the elimination rule the continuation ranges over every mode-preserving context embedding ee and every data term x:Xex:X_e in its target; xt,ex^{t,e} denotes the tagged copy formed there. π’ŸΞ“,Ξ³(x:X)𝒫Γ,Ξ³(y∼xt)𝒫Γ,Ξ³(Is⁡t(y)).\frac{\mathcal D_{\Gamma,\gamma}(x:X)\qquad \mathcal P_{\Gamma,\gamma}(y\sim x^t)} {\mathcal P_{\Gamma,\gamma}(\operatorname{Is}_t(y))}.(8)✦ 𝒫Γ,Ξ³(Is⁡t(y))βˆ€(Ξ”,Ξ΄)βˆ€e:(Ξ“,Ξ³)β†’(Ξ”,Ξ΄)βˆ€x with π’ŸΞ”,Ξ΄(x:Xe),𝒫Δ,Ξ΄(ye∼ext,e)⇒𝒫Δ,Ξ΄(De)𝒫Γ,Ξ³(D).\frac{ \begin{gathered} \mathcal P_{\Gamma,\gamma}(\operatorname{Is}_t(y))\\ \forall (\Delta,\delta)\;\forall e:(\Gamma,\gamma)\to(\Delta,\delta)\; \forall x\text{ with }\mathcal D_{\Delta,\delta}(x:X_e),\\ \mathcal P_{\Delta,\delta}(y_e\sim_e x^{t,e}) \Longrightarrow\mathcal P_{\Delta,\delta}(D_e) \end{gathered}} {\mathcal P_{\Gamma,\gamma}(D)}.(9)✦

For t∈{β„“,r}t\in\{\ell,r\}, edge introduction and elimination have the forms (10) and (11), with the same data typing and continuation requirements. π’ŸΞ“,Ξ³(x:X)𝒫Γ,Ξ³(y∼x0)𝒫Γ,Ξ³(z∼xt)𝒫Γ,Ξ³(Tt(y,z)).\frac{\mathcal D_{\Gamma,\gamma}(x:X)\qquad \mathcal P_{\Gamma,\gamma}(y\sim x^0)\qquad \mathcal P_{\Gamma,\gamma}(z\sim x^t)} {\mathcal P_{\Gamma,\gamma}(T_t(y,z))}.(10)✦ 𝒫Γ,Ξ³(Tt(y,z))βˆ€(Ξ”,Ξ΄)βˆ€e:(Ξ“,Ξ³)β†’(Ξ”,Ξ΄)βˆ€x with π’ŸΞ”,Ξ΄(x:Xe),𝒫Δ,Ξ΄((ye∼ex0,e)∧(ze∼ext,e))⇒𝒫Δ,Ξ΄(De)𝒫Γ,Ξ³(D).\frac{ \begin{gathered} \mathcal P_{\Gamma,\gamma}(T_t(y,z))\\ \forall (\Delta,\delta)\;\forall e:(\Gamma,\gamma)\to(\Delta,\delta)\; \forall x\text{ with }\mathcal D_{\Delta,\delta}(x:X_e),\\ \mathcal P_{\Delta,\delta} \bigl((y_e\sim_e x^{0,e})\land(z_e\sim_e x^{t,e})\bigr) \Longrightarrow\mathcal P_{\Delta,\delta}(D_e) \end{gathered}} {\mathcal P_{\Gamma,\gamma}(D)}.(11)✦

In the paper, the result reads: Is⁡t(y)β†”βˆƒx.(y∼xt)\operatorname{Is}_t(y)\leftrightarrow\exists x.\,(y\sim x^t) for t=0,β„“,rt=0,\ell,r, and Tt(y,z)β†”βˆƒx.((y∼x0)∧(z∼xt))T_t(y,z)\leftrightarrow\exists x.\,((y\sim x^0)\land(z\sim x^t)) for t=β„“,rt=\ell,r.

What Is Checked

The rules are stated over the formed specialized relational coding and its logical calculus, using the labelled typing and mode discipline of (1), the guarded class and edge constructions of (7), and stable witness extraction for their elimination targets under mode-preserving context embeddings.