OctoInformBeta

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

Lemma 52: Exact evaluation and extensionality under the response condition Resp\mathrm{Resp}, with validity Valid\mathrm{Valid} for the predecessor law

Guarded laws for the response predicate.

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 guarded diagonal construction compares incidence on tagged observations with an order on logical probe elements. These belong to different carriers: a probe is tested against an observation, whereas a channel predicate is evaluated at a logical element.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), a context Ξ“\Gamma, and an assignment Ξ³\gamma of data and proof modes to its variables. The axiom and product-rule relations are arbitrary. Write Ξ“βŠ’Ξ³M:A[𝖽]\Gamma\vdash_\gamma M:A\,[\mathsf d] for typing together with data mode, and use [𝗉][\mathsf p] for proof mode. A formula AA is inhabited in proof mode, written 𝖯𝗋𝖿Γ,Ξ³(A)\mathsf{Prf}_{\Gamma,\gamma}(A), when some term pp satisfies Ξ“βŠ’Ξ³p:A[𝗉]\Gamma\vdash_\gamma p:A\,[\mathsf p].✦ Formula equivalence A≃Γ,Ξ³BA\simeq_{\Gamma,\gamma}B means the existence of uniform typed open proof-term transformers in both directions, with a temporary proof input of the respective source formula.✦

Take an ambient logical calculus LL with its fixed feasible witness family and quantifier routes. Its logical operations use incoming and outgoing proof paths; KYK_Y and KPK_P denote the routes for element and predicate quantification. The connectives below are those of LL, and βˆ€Y\forall_Y and βˆ€P\forall_P denote these two quantifiers. In particular, A↔BA\leftrightarrow B is the conjunction of the two logical implications between the formulas.✦

Let BB be a specialized relational coding with distinguished type TT and a three-copy observation system. Write UU for its common probe type, and β„“\ell, rr and qq for the shared channel’s logical, raw and predicate paths. A path applied to a type denotes its data wrapper. If ΞΉ\iota is the probe’s initial path, the carriers in (1) are the logical element type XX, predicate type 𝒫U\mathcal P_U, and specialized base type DD; YY is the tagged observation carrier. X=β„“U,𝒫U=q(rU),D=ΞΉT,Y=β„“D.X=\ell U,\qquad \mathcal P_U=q(rU),\qquad D=\iota T,\qquad Y=\ell D.(1) The last identity is a compatibility condition on the observation system. Its outer second path is the relational logical path, and its outer first wrapper of the middle-copy carrier is DD.

Incidence and Response

For a type AA, a channel predicate ii on AA and a logical element xx of AA, channel evaluation Ev⁡A(i,x)\operatorname{Ev}_A(i,x) is the formula obtained by observing ii along the predicate path against the raw reencoding of xx.✦ The channel predicate pred⁡A[Ξ¦]\operatorname{pred}_A[\Phi] on a type AA is the predicate formed from a one-variable formula Ξ¦\Phi by reencoding its argument from the raw path to the logical path in its body.✦ For a logical probe element xx of type XX, the tagged copy Ο„t(x)\tau_t(x), for t∈{0,1,2}t\in\{0,1,2\}, is an observation of type YY obtained by reencoding xx from the logical path to the raw path and applying the inner and outer copy embeddings.✦ Their marker bits are true precisely at t=1t=1 and t=2t=2, respectively.

The channel predicate type on DD is 𝒫D=q(rD)\mathcal P_D=q(rD).✦ The structural parameter m0m_0 is the query realization of observation invariance, class representation in all three copies, edge representation in copies 11 and 22, and relational closure.✦ The relational closure condition for a:𝒫Da:\mathcal P_D says that, if its left-copy predicate, whose body evaluates aa on tag-one copies of logical probe elements, is extensional, then that predicate lies below every valid logical element x:Xx:X for which the right-copy evaluation Ev⁡D(a,Ο„2(x))\operatorname{Ev}_D(a,\tau_2(x)) holds.✦ For a probe vv of type UU and a tagged observation yy of type YY, the incidence formula vβ‹„yv\diamond y observes vv at TT against the relational bundle whose observations are the dummy observation, m0m_0, and the point encoding of yy.✦

For y:Yy:Y and i:𝒫Ui:\mathcal P_U, the specialized probe observation of yy by ii is the three-copy observation of yy against the uniform predicate probe ziz_i, at the common probe type UU.✦ For y,z:Yy,z:Y, specialized observational comparison is the formula asserting that their specialized probe observations are logically equivalent for every channel predicate i:𝒫Ui:\mathcal P_U.✦ Tagged observational equivalence of y,z:Yy,z:Y is the conjunction of their specialized observational comparison and logical equivalence of their respective inner and outer markers.✦

The left-copy evaluation of a:𝒫Da:\mathcal P_D at x:Xx:X is Ev⁡D(a,Ο„1(x))\operatorname{Ev}_D(a,\tau_1(x))✦; the left-copy predicate of aa is the channel predicate on XX with this evaluation as its body.✦

The specialized observational relation y∼Bzy\sim_B z between tagged observations yy and zz of type YY is the guarded formula (2). The admissibility condition Good⁡m0(a)\operatorname{Good}_{m_0}(a) on a channel predicate aa of type 𝒫D\mathcal P_D is the conjunction of roundtrip invariance of aa and its structural query of index zero at m0m_0.✦ Roundtrip invariance of a channel predicate aa of type 𝒫D\mathcal P_D is the condition that its evaluations are logically equivalent before and after reencoding to the raw channel and back to the logical channel.✦ y∼Bz:=βˆ€Pa:𝒫D,Good⁡m0(a)β‡’(Ev⁡D(a,y)↔Ev⁡D(a,z)).y\sim_B z :=\forall_P a:\mathcal P_D,\quad \operatorname{Good}_{m_0}(a)\Rightarrow \bigl(\operatorname{Ev}_D(a,y)\leftrightarrow \operatorname{Ev}_D(a,z)\bigr).(2)✦

At the base type DD with admissibility condition Good⁡m0\operatorname{Good}_{m_0}, the equivalence class predicate of y:Yy:Y is the channel predicate whose value at z:Yz:Y is z∼Byz\sim_B y.✦ The class union predicate of y,z:Yy,z:Y, at the base type DD with admissibility condition Good⁡m0\operatorname{Good}_{m_0}, is the channel predicate whose value at w:Yw:Y is the disjunction of w∼Byw\sim_B y and w∼Bzw\sim_B z.✦ The class query placing y:Yy:Y in class tt is the structural query of index t+1t+1 at m0m_0 applied to the equivalence class predicate of yy, for t∈{0,1,2}t\in\{0,1,2\}.✦

For a probe vv of type UU, the response condition Resp(v)\mathrm{Resp}(v) is the formula (3) requiring incidence with vv to respect the specialized observational relation. Resp(v):=βˆ€Yy:Y,βˆ€Yz:Y,y∼Bzβ‡’(vβ‹„y↔vβ‹„z).\mathrm{Resp}(v) :=\forall_Y y:Y,\ \forall_Y z:Y,\quad y\sim_B z\Rightarrow \bigl(v\diamond y\leftrightarrow v\diamond z\bigr).(3) The response predicate ivi_v is the channel predicate on logical probe elements with tag-zero incidence as its body, as defined in (4). iv:=pred⁡U[x↦vβ‹„Ο„0(x)].i_v:=\operatorname{pred}_U [\,x\mapsto v\diamond\tau_0(x)\,].(4)✦ The response predicate ivi_v is defined for every probe vv, whether or not Resp(v)\mathrm{Resp}(v) is inhabited in proof mode.

Order and Validity

For a probe vv of type UU, the section predicate pred⁡D[y↦vβ‹„y]\operatorname{pred}_D[y\mapsto v\diamond y] is the channel predicate on DD whose body is incidence with vv.✦ For a probe vv of type UU and a tagged observation yy of type YY, the section pair query sb(v,y)\mathrm{sb}(v,y) is the structural query of index 66 at m0m_0, applied to the relational pair predicate of the section predicate of vv and yy.✦ The pair predicate uses the actual admissibility condition Good⁡m0\operatorname{Good}_{m_0} and the structural query family: its membership formula at zz is the disjunction of a class-11 edge from an element satisfying the section and a class-22 edge from yy. The first alternative is existentially quantified over the witnessing element.

The relational element lift of a probe vv of type UU is a logical probe element of type XX whose observations are the section pair queries of vv. For a channel predicate ii, its uniform predicate probe ziz_i recovers the pullback of ii along this lift, uniformly over the type parameter and single-bundle argument.✦ For a channel predicate ii of type 𝒫U\mathcal P_U and a logical probe element xx of type XX, the probe order formula iβ‰Όxi\preccurlyeq x is the observation of xx along the logical path against ziz_i.✦

Predicate equivalence iβ‰ˆPji\approx_P j between channel predicates ii and jj of type 𝒫U\mathcal P_U, and probe element equivalence xβ‰ˆXxβ€²x\approx_X x' between logical probe elements xx and xβ€²x' of type XX, are the formulas in (5). iβ‰ˆPj:=βˆ€Yx:X,Ev⁡U(i,x)↔Ev⁡U(j,x),xβ‰ˆXxβ€²:=βˆ€Pi:𝒫U,(iβ‰Όx)↔(iβ‰Όxβ€²).\begin{aligned} i\approx_P j &:=\forall_Y x:X,\quad \operatorname{Ev}_U(i,x)\leftrightarrow\operatorname{Ev}_U(j,x),\\ x\approx_X x' &:=\forall_P i:\mathcal P_U,\quad (i\preccurlyeq x)\leftrightarrow(i\preccurlyeq x'). \end{aligned}(5) Extensionality Ext(i)\mathrm{Ext}(i) of a channel predicate ii of type 𝒫U\mathcal P_U and validity Valid(x)\mathrm{Valid}(x) of a logical probe element xx of type XX are the formulas (6) expressing respect for probe element equivalence and predicate equivalence, respectively. Ext(i):=βˆ€Yx:X,βˆ€Yxβ€²:X,xβ‰ˆXxβ€²β‡’(Ev⁡U(i,x)↔Ev⁡U(i,xβ€²)),Valid(x):=βˆ€Pi:𝒫U,βˆ€Pj:𝒫U,iβ‰ˆPjβ‡’((iβ‰Όx)↔(jβ‰Όx)).\begin{aligned} \mathrm{Ext}(i) &:=\forall_Y x:X,\ \forall_Y x':X,\quad x\approx_X x'\Rightarrow \bigl(\operatorname{Ev}_U(i,x)\leftrightarrow \operatorname{Ev}_U(i,x')\bigr),\\ \mathrm{Valid}(x) &:=\forall_P i:\mathcal P_U,\ \forall_P j:\mathcal P_U,\quad i\approx_P j\Rightarrow \bigl((i\preccurlyeq x)\leftrightarrow(j\preccurlyeq x)\bigr). \end{aligned}(6)

The Claim

Theorem 1. Assume the specialized observation system satisfies its retained-path profile conditions and the carrier and path compatibilities above. Assume also Ξ“βŠ’Ξ³T:s0[𝖽]\Gamma\vdash_\gamma T:s_0\,[\mathsf d], where s0s_0 is the probe’s seed sort. Let vv satisfy Ξ“βŠ’Ξ³v:U[𝖽]\Gamma\vdash_\gamma v:U\,[\mathsf d], and suppose Resp(v)\mathrm{Resp}(v) is inhabited in proof mode.

For every xx satisfying Ξ“βŠ’Ξ³x:X[𝖽]\Gamma\vdash_\gamma x:X\,[\mathsf d], the exact evaluation law is (7). Ev⁡U(iv,x)≃Γ,Ξ³vβ‹„Ο„0(x).\operatorname{Ev}_U(i_v,x) \simeq_{\Gamma,\gamma} v\diamond\tau_0(x).(7)✦ The extensionality assertion is (8). 𝖯𝗋𝖿Γ,Ξ³(Ext(iv)).\mathsf{Prf}_{\Gamma,\gamma}\bigl(\mathrm{Ext}(i_v)\bigr).(8)✦ If, in addition, Valid(x)\mathrm{Valid}(x) is inhabited in proof mode, the predecessor law is (9). sb(v,Ο„0(x))≃Γ,Ξ³(ivβ‰Όx).\mathrm{sb}\bigl(v,\tau_0(x)\bigr) \simeq_{\Gamma,\gamma}(i_v\preccurlyeq x).(9)✦

What Is Checked

The statements range over labelled terms with their typing judgments and data or proof modes, an ambient logical calculus with element and predicate quantifier routes, and compatible specialized three-copy observations with a seed-sorted distinguished type.