OctoInformBeta

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

Lemma 51: Incidence recovery assumes Resp⁡(v)\operatorname{Resp}(v), invariance of probe vv under observational equivalence; second-channel comparison has no response premise

Response pairing distinguishes left and right tags.

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

Pairing combines a predicate and an observation in the relational coding of a pure type system. The observations range over three tagged copies of a logical probe type. Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations, a context Ξ“\Gamma, and a mode assignment Ξ³\gamma taking values in data and proof.

Terms have applications, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B, with labels for data to data, data to proof, or proof to proof. Typing is written Ξ“βŠ’M:A\Gamma\vdash M:A; the mode discipline separately assigns modes to variables and respects the argument and result modes of each label. Annotations and product types have data mode. Named variables below use source notation for de Bruijn terms in newest-first contexts. Full Ξ²\beta reduction includes annotations and binder bodies, and conversion is its equivalence closure. A valid context is a context obtained from the empty context by adjoining a type AA whenever Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦ A Ξ²\beta normal form is a term admitting no one-step Ξ²\beta reduction.✦ A term is weakly normalizing when a finite sequence of Ξ²\beta reductions reaches a Ξ²\beta normal form.✦ Write M#M^\# for the chosen full Ξ²\beta normal form of MM when one exists, and for a fixed arbitrary term otherwise.✦

The normal form sort profile πΓ(T)\pi_\Gamma(T) is the set of all sorts ss for which Ξ“βŠ’T#:s\Gamma\vdash T^\#:s.✦ A feasible sort profile is a nonempty set II of sorts for which some valid context Ξ”\Delta and some Ξ²\beta normal form AA satisfy πΔ(A)=I\pi_\Delta(A)=I .✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) is the set of sorts tt with (s,t)βˆˆπ’œ(s,t)\in\mathcal A .✦ For sets I,JI,J of sorts, the product output profile Out⁡(I,J)\operatorname{Out}(I,J) consists of the sorts cc for which (a,b,c)βˆˆβ„›(a,b,c)\in\mathcal R for some a∈Ia\in I and b∈Jb\in J .✦ A feasible product profile triple (I,J,K)(I,J,K) consists of three feasible sort profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J) , with II the domain profile, JJ the codomain profile and KK the product profile.✦

The primary signed graph on sort profiles has positive inclusion edges Iβ†’JI\to J between feasible profiles when J⊊IJ\subsetneq I. Each feasible product profile triple (I,J,K)(I,J,K) gives a negative domain edge Iβ†’KI\to K and a positive codomain edge Jβ†’KJ\to K . Positive reachability is reachability by a finite, possibly empty path consisting entirely of positive edges.✦

A labelled term is data-only when every application, abstraction and dependent product in it has the data-to-data label.✦ Label erasure removes all argument and result labels from a labelled term, preserving its variables, sorts and term constructors.✦

Fix a logical calculus LL and quantifier routes KY,KPK_Y,K_P. Its implication and universal quantification use fixed incoming and outgoing proof wrappers, with a proof-to-proof arrow for implication and a data-to-proof dependent product for quantification. Write β‡’,∧,∨,↔\Rightarrow,\wedge,\vee,\leftrightarrow for its logical connectives, and βˆ€,βˆƒ\forall,\exists for its quantifiers. A proof-mode inhabitant of a formula AA is a term hh with Ξ“βŠ’h:A\Gamma\vdash h:A in proof mode.✦ A typed open transformer A⇝BA\rightsquigarrow B is a proof-mode term tt with p:A,Ξ“βŠ’t:Bp:A,\Gamma\vdash t:B, where the fresh input pp has proof mode.✦ Typed formula equivalence Aβ‰ˆΞ“,Ξ³BA\approx_{\Gamma,\gamma}B between formulas AA and BB is the relation defined in (1). Aβ‰ˆΞ“,Ξ³B⇔(A⇝B)and(B⇝A).A\approx_{\Gamma,\gamma}B \quad\Longleftrightarrow\quad (A\rightsquigarrow B)\ \text{and}\ (B\rightsquigarrow A).(1)✦ For a collection CC of sort profiles, the observation layers are the profiles 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 is an observation layer II for which some J,K∈CJ,K\in C form a feasible product profile triple (I,J,K)(I,J,K) .✦ A logical terminal profile is a profile JJ for which some I,K∈CI,K\in C form a feasible product profile triple (I,J,K)(I,J,K) .✦ A labelled type AA is sorted at a profile II in Ξ“\Gamma when Ξ“βŠ’A:s\Gamma\vdash A:s for every s∈Is\in I ; it may also have sorts outside II .✦ A fixed feasible witness family is a choice of a type TIT_I and a value uIu_I at every sort set II. At every feasible profile II , the type is data-only, its erasure is a full Ξ²\beta normal form, it is sorted at II in Ξ“\Gamma , and Ξ“βŠ’uI:TI\Gamma\vdash u_I:T_I , with both TIT_I and uIu_I in data mode.✦ A formed proof wrapper path is a proof wrapper path constructed from an even identity path at its source profile by the permitted target restrictions and extensions.✦ A feasible product profile triple (A,J,K)(A,J,K) extends a path ending at JJ positively to KK using the fixed witness type at AA , whereas (J,B,K)(J,B,K) extends it negatively using the fixed witness type at BB when J,K∈CJ,K\in C , reversing parity. The falsity formula βŠ₯\bot of LL is the type selected at its logical base profile by its fixed feasible witness family.✦

Tagged Observations and Structural Queries

A specialized relational coding BB consists of a three-copy observation system and a chosen type TT.✦ Its underlying relational system has a uniform probe type VV, an initial data path ΞΉ\iota, and a shared channel with logical, raw, and predicate paths β„“,ρ,Ο‡\ell,\rho,\chi, all three of odd parity. A retained data path is a finite succession of positive and negative wrapper steps; its parity counts negative steps modulo two.✦ Write a path applied to a type for its wrapper type. The specialized base type DD, logical probe element type XX, and channel predicate type at a type UU are given in (2). The tagged observation type YY is the carrier obtained from ρ(V)\rho(V) by the inner and outer double channels, each consisting of two odd paths.✦ Assume the probe and channel formation conditions, and the specialized shape conditions: TT has the probe’s seed sort in Ξ“\Gamma and has data mode, Y=β„“(D)Y=\ell(D), the outer second path is β„“\ell, and the outer first path applied to the middle copy carrier is DD.✦ D=ΞΉ(T),X=β„“(V),Pred⁡(U)=Ο‡(ρ(U)).D=\iota(T),\qquad X=\ell(V),\qquad \operatorname{Pred}(U)=\chi(\rho(U)).(2) A positive data path is a finite succession of steps retaining a domain type and a dummy argument at each step; its wrapper type is an iterated data-to-data arrow. Its injection forms constant annotated abstractions over those domains, and its projection applies to the retained dummy arguments. A formed positive data path is a positive data path constructed from the identity at its source profile by the permitted target restrictions and extensions.✦ A feasible product profile triple (A,J,K)(A,J,K) extends a path ending at JJ positively to KK , retaining the fixed witness type and value at AA . A data path tail consists of a sort, a positive data path and fixed encoding and decoding proof paths; its carrier is the positive wrapper of that sort. Encoding applies the encoding proof wrapper and then the positive injection, while decoding takes the positive projection and then applies the decoding proof wrapper. A data path tail ending at JJ is formed when its sort ss satisfies {s}∈C\{s\}\in C , its axiom profile is nonempty, and its positive path runs from Ax⁡(s)\operatorname{Ax}(s) to JJ . Its encoding and decoding proof paths run respectively from the logical base to {s}\{s\} and back with even parity, and the decoding path contains a negative step. A formed retained data path is a retained data path constructed from the identity at its source profile by the permitted target restrictions and extensions.✦ A feasible product profile triple (A,J,K)(A,J,K) extends a path ending at JJ positively to KK using the fixed witness type and value at AA , whereas (J,B,K)(J,B,K) together with a formed data path tail ending at BB permits a negative extension to KK , reversing parity. A formed double data channel from II through JJ to KK consists of a formed first odd path from II to JJ and a formed second odd path from JJ to KK .✦

For a type UU , a channel predicate p:Pred⁡(U)p:\operatorname{Pred}(U) , and a logical element y:β„“(U)y:\ell(U) , channel evaluation p@Uyp@_U y observes pp along the predicate path at ρ(U)\rho(U) , against the raw reencoding of yy .✦ Reencoding observes along the source path and builds along the target path.✦ The channel roundtrip round⁡U(y)\operatorname{round}_U(y) reencodes a logical element into the raw channel and back.✦ For a predicate body QQ on logical elements at a type UU, the encoded predicate pred⁡U(Q)\operatorname{pred}_U(Q) is the predicate path builder applied to the body QQ after raw-to-logical reencoding.✦ Subscripts on evaluation are omitted at DD. Data path observation of a wrapped term against a test substitutes that term into the test at the identity path. At a positive step it applies the term to the retained dummy argument and continues along the remaining path; at a negative step it applies the term to the test built along the remaining path and decodes the result through the data path tail.

The three tagged embeddings of x:Xx:X into YY are written x0,xβ„“,xrx^0,x^\ell,x^r, for copy indices 0,1,20,1,2. They reencode the logical wrapper into the raw wrapper, then embed through the inner and outer channels; the inner embedding bit is true exactly at index 11, and the outer embedding bit exactly at index 22. Let bin,boutb_{\mathrm{in}},b_{\mathrm{out}} be the corresponding marker observations, with the inner marker recovered through the outer channel. For i:Pred⁡(V)i:\operatorname{Pred}(V) , let ziz_i be its uniform predicate probe. The observation Obs⁡(i,y)\operatorname{Obs}(i,y) recovers the payload of yy through both channels and tests it against ziz_i .✦ Tagged observational equivalence y≍zy\asymp z between observations y,z:Yy,z:Y is the formula in (3). y≍z:=(bin(y)↔bin(z))∧((bout(y)↔bout(z))βˆ§βˆ€i:Pred⁡(V),(Obs⁡(i,y)↔Obs⁡(i,z))).\begin{aligned} y\asymp z := {}& (b_{\mathrm{in}}(y)\leftrightarrow b_{\mathrm{in}}(z))\ \wedge\ &\bigl((b_{\mathrm{out}}(y)\leftrightarrow b_{\mathrm{out}}(z))\ \wedge\ &\qquad\forall i:\operatorname{Pred}(V),\, (\operatorname{Obs}(i,y)\leftrightarrow\operatorname{Obs}(i,z))\bigr). \end{aligned}(3)✦ Double channel evaluation against a predicate body builds that body along the first odd path and observes the supplied element against the result along the second odd path.✦ The encoded bit observation in a double channel is double channel evaluation against the constant truth predicate.✦ Signed payload recovery in a double channel is the logical conditional that returns its double channel evaluation when its encoded bit observation holds, and the negation of that evaluation otherwise.✦ Signed payload embedding of an element builds along the second odd path the observation predicate of that element along the first path, retaining that predicate for a true bit and negating it for a false bit.✦

The probe order observation iβ‰Όxi\preceq x observes xx along the logical path at VV against ziz_i.✦ For predicates i,j:Pred⁡(V)i,j:\operatorname{Pred}(V), predicate equivalence i≐ji\doteq j is the formula comparing their channel evaluations at every x:Xx:X.✦ Probe element equivalence x≃xβ€²x\simeq x' for elements x,xβ€²:Xx,x':X , predicate extensionality Ext⁡(i)\operatorname{Ext}(i) for i:Pred⁡(V)i:\operatorname{Pred}(V) , and order validity Valid⁡(x)\operatorname{Valid}(x) for x:Xx:X are the formulas in (4); each quantifier over predicates uses KPK_P , and each quantifier over elements uses KYK_Y . i≐j:=βˆ€x:X,(i@Vx↔j@Vx),x≃xβ€²:=βˆ€i:Pred⁡(V),(iβ‰Όx↔iβ‰Όxβ€²),Ext⁡(i):=βˆ€x,xβ€²:X,(x≃xβ€²)β‡’(i@Vx↔i@Vxβ€²),Valid⁡(x):=βˆ€i,j:Pred⁡(V),(i≐j)β‡’(iβ‰Όx↔jβ‰Όx).\begin{aligned} i\doteq j &:= \forall x:X,\ (i@_Vx\leftrightarrow j@_Vx),\\ x\simeq x' &:= \forall i:\operatorname{Pred}(V),\ (i\preceq x\leftrightarrow i\preceq x'),\\ \operatorname{Ext}(i)&:=\forall x,x':X,\ (x\simeq x')\Rightarrow(i@_Vx\leftrightarrow i@_Vx'),\\ \operatorname{Valid}(x)&:=\forall i,j:\operatorname{Pred}(V),\ (i\doteq j)\Rightarrow(i\preceq x\leftrightarrow j\preceq x). \end{aligned}(4) The section pair query at a type AA , parameter mm , probe vv and element aa is query 66 of mm against the relational pair of the section predicate of vv and aa .✦ The relational element lift of aa at AA and mm is the logical-path encoding whose predicate on a probe vv is the section pair query at A,m,v,aA,m,v,a .✦ The predicate pullback of ii along this lift is the encoded predicate on logical elements aa whose membership formula is channel evaluation of ii at the relational element lift of aa .✦ Predicate pullback recovery tests a single-bundle argument by recovery access in the probe double channel, using the predicate path and the predicate pullback of ii as a function of the data parameter.✦

For a predicate pp over YY and a copy index tt , observation invariance G(p)G(p) , class representation Ct(p)C_t(p) , edge representation Et(p)E_t(p) , and relational closure H(p)H(p) are the formulas in (5). Here x1=xβ„“x^1=x^\ell and x2=xrx^2=x^r, and the left copy predicate is rp=pred⁡V(x↦p@xβ„“)r_p=\operatorname{pred}_V(x\mapsto p@x^\ell).✦ G(p):=βˆ€y,z:Y,(y≍z)β‡’(p@y↔p@z),Ct(p):=βˆƒx:X,βˆ€y:Y,(p@y↔y≍xt),Et(p):=βˆƒx:X,βˆ€y:Y,(p@y↔((y≍x0)∨(y≍xt))),H(p):=Ext⁡(rp)β‡’βˆ€x:X,Valid⁡(x)β‡’(p@xrβ‡’rpβ‰Όx).\begin{aligned} G(p)&:=\forall y,z:Y,\ (y\asymp z)\Rightarrow(p@y\leftrightarrow p@z),\\ C_t(p)&:=\exists x:X,\ \forall y:Y,\ (p@y\leftrightarrow y\asymp x^t),\\ E_t(p)&:=\exists x:X,\ \forall y:Y,\ \bigl(p@y\leftrightarrow((y\asymp x^0)\vee(y\asymp x^t))\bigr),\\ H(p)&:=\operatorname{Ext}(r_p)\Rightarrow \forall x:X,\ \operatorname{Valid}(x)\Rightarrow (p@x^r\Rightarrow r_p\preceq x). \end{aligned}(5)

The structural parameter m0m_0 is the query realization, using the constant truth marker, with branches G,C0,C1,C2,E1,E2,HG,C_0,C_1,C_2,E_1,E_2,H in that order.✦ Write Qt(p)Q_t(p) for the structural query at tag t∈{0,…,6}t\in\{0,\ldots,6\} of m0m_0 against pp.✦ An admissible predicate p:Pred⁡(D)p:\operatorname{Pred}(D) is a channel predicate satisfying the actual roundtrip and structural guard Good\operatorname{Good} in (6). The specialized observational relation ∼\sim tests precisely this guard.✦ Good⁡(p):=(βˆ€y:Y,p@y↔p@round⁡D(y))∧Q0(p),y∼z:=βˆ€p:Pred⁡(D),Good⁡(p)β‡’(p@y↔p@z).\begin{aligned} \operatorname{Good}(p)&:= \bigl(\forall y:Y,\ p@y\leftrightarrow p@\operatorname{round}_D(y)\bigr)\wedge Q_0(p),\\ y\sim z&:=\forall p:\operatorname{Pred}(D),\ \operatorname{Good}(p)\Rightarrow(p@y\leftrightarrow p@z). \end{aligned}(6) Roundtrip invariance of a channel predicate p:Pred⁡(D)p:\operatorname{Pred}(D) means that its evaluations at yy and round⁡D(y)\operatorname{round}_D(y) are logically equivalent for every y:Yy:Y.✦

Response and Pairing

For observations y,z:Yy,z:Y , the equivalence class predicate [y][y] and class union predicate Uy,zU_{y,z} are encoded predicates defined using ∼\sim in (7). For an observation y:Yy:Y and a copy index tt, the class query class⁡t(y)\operatorname{class}_t(y) is the formula obtained by applying structural query t+1t+1 to [y][y].✦ The left and right tagged edge predicates require their respective class queries and the query on the class union. [y]:=pred⁡D(w↦w∼y),Uy,z:=pred⁡D(w↦(w∼y)∨(w∼z)),class⁡t(y):=Qt+1([y]),Edge⁡β„“(y,z):=class⁡0(y)∧(class⁡1(z)∧Q4(Uy,z)),Edge⁡r(y,z):=class⁡0(y)∧(class⁡2(z)∧Q5(Uy,z)).\begin{aligned} [y]&:=\operatorname{pred}_D(w\mapsto w\sim y),\\ U_{y,z}&:=\operatorname{pred}_D(w\mapsto (w\sim y)\vee(w\sim z)),\\ \operatorname{class}_t(y)&:=Q_{t+1}([y]),\\ \operatorname{Edge}_{\ell}(y,z)&:= \operatorname{class}_0(y)\wedge \bigl(\operatorname{class}_1(z)\wedge Q_4(U_{y,z})\bigr),\\ \operatorname{Edge}_r(y,z)&:= \operatorname{class}_0(y)\wedge \bigl(\operatorname{class}_2(z)\wedge Q_5(U_{y,z})\bigr). \end{aligned}(7)

The specialized pair predicate Pair⁡(p,a)\operatorname{Pair}(p,a) of p:Pred⁡(D)p:\operatorname{Pred}(D) and a:Ya:Y is the encoded predicate with membership formula (8). Its existential quantifier uses KYK_Y. Pair⁡(p,a):=pred⁡D(z↦(βˆƒy:Y,Edge⁡β„“(y,z)∧p@y)∨Edge⁡r(a,z)).\operatorname{Pair}(p,a):= \operatorname{pred}_D\!\left(z\mapsto \bigl(\exists y:Y,\ \operatorname{Edge}_{\ell}(y,z)\wedge p@y\bigr) \vee\operatorname{Edge}_r(a,z)\right).(8)✦

For a uniform probe v:Vv:V, a structural parameter mm, and an observation y:Yy:Y, the diamond observation vβ‹„myv\diamond_m y observes the specialization of vv at TT along the probe’s even function path against the test that applies its input to the relational argument bundle of mm and yy and decodes the result through the data path tail.✦ This specialization is the data-mode application of vv to the positive wrapper injection of TT along the probe’s lifting path.✦ That bundle combines the dummy observation, mm, and the point encoding of the raw reencoding of yy.✦ Specialize this observation to m0m_0.✦ For a uniform probe vv , predicate extraction Part⁡(v)\operatorname{Part}(v) is the channel predicate over YY defined in (9). Part⁡(v):=pred⁡D(y↦vβ‹„m0y).\operatorname{Part}(v):= \operatorname{pred}_D(y\mapsto v\diamond_{m_0}y).(9)✦

The response predicate Resp⁡(v)\operatorname{Resp}(v) is the formula (10); its quantifiers over observations use KYK_Y. Resp⁡(v):=βˆ€y,z:Y,(y∼z)β‡’(vβ‹„m0y↔vβ‹„m0z).\operatorname{Resp}(v):=\forall y,z:Y,\ (y\sim z)\Rightarrow (v\diamond_{m_0}y\leftrightarrow v\diamond_{m_0}z).(10)✦

The Claim

Theorem 1 (Lemma 51). Let vv be a data-mode term with Ξ“βŠ’v:V\Gamma\vdash v:V. For data-mode terms Ξ“βŠ’a:Y\Gamma\vdash a:Y and Ξ“βŠ’x:X\Gamma\vdash x:X, assume a proof-mode inhabitant of Resp⁡(v)\operatorname{Resp}(v). Then (11) holds. Pair⁡(Part⁡(v),a)@xβ„“β‰ˆΞ“,Ξ³vβ‹„m0x0.\operatorname{Pair}(\operatorname{Part}(v),a)@x^\ell \ \approx_{\Gamma,\gamma}\ v\diamond_{m_0}x^0.(11)✦ For data-mode terms Ξ“βŠ’a:X\Gamma\vdash a:X and Ξ“βŠ’x:X\Gamma\vdash x:X, the law (12) holds without a response hypothesis. Pair⁡(Part⁡(v),a0)@xrβ‰ˆΞ“,Ξ³(a≃x).\operatorname{Pair}(\operatorname{Part}(v),a^0)@x^r \ \approx_{\Gamma,\gamma}\ (a\simeq x).(12)✦

In the paper, the result reads: under h:Resp⁡(v)h:\operatorname{Resp}(v), set Px=Pair⁡(Part⁡(v),x0)P_x=\operatorname{Pair}(\operatorname{Part}(v),x^0); for every xβ€²:Xx':X there are proofs of Px@(xβ€²β„“)↔vβ‹„m(xβ€²0)P_x@(x'^{\,\ell})\leftrightarrow v\diamond_m(x'^{\,0}) and Px@(xβ€²r)↔x≃xβ€²P_x@(x'^{\,r})\leftrightarrow x\simeq x'.

What Is Checked

The claims are stated over labelled typing and the data and proof mode discipline in the fixed logical calculus, with quantifier routes and specialized relational coding satisfying the probe, channel, seed-sorting and copy-shape conditions stated above.