OctoInformBeta

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

Response predicates, shift, and induction: The data shift and its predicate pullback in a specialized three-copy observation system

Response predicates and a guarded induction object.

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 argument takes place between logical probe elements and a carrier with three tagged copies. Its induction formulas are labelled terms, alongside the data terms on which their observations are taken.

Fix a family of sorts SS. Labelled terms are variables, sorts, applications, annotated abstractions λlx:A.M\lambda_l x:A.M, and dependent products Πlx:A.B\Pi_l x:A.B.✦ The label records the argument and result modes: dddd means data to data, dpdp data to proof, and pppp proof to proof.✦ Bound variables below are written by name, and substitution avoids capture.

A retained data path is a finite path generated by the identity, positive extensions with a fixed domain and dummy argument, and negative extensions with a fixed data tail.✦ The parity of a retained data path is the number of its negative extensions modulo two. A positive extension adds a constant annotated data abstraction; its observation applies the retained dummy argument. A negative extension reverses the arrow and uses its tail to encode and decode the resulting formula. A data tail consists of a terminal sort, a positive data path containing only positive extensions, and encoding and decoding proof paths generated by identity, positive data-to-proof arrows, and negative proof-to-proof arrows. Positive data path injection uses constant data abstractions, and projection applies the retained dummy arguments. The carrier of a data tail is the positive wrapper of its terminal sort along its positive path. Data tail encoding applies the encoding proof path to a formula and then takes the positive injection. Data tail decoding of a term first takes its projection along the positive path and then applies the decoding proof path.

For a retained data path UU and a data type TT, write U[T]U[T] for the wrapped data type. For odd UU, write build⁡U(T;x.Φ)\operatorname{build}_U(T;x.\Phi) for its data path builder from a one-variable formula body, and obs⁡U(T;w,a)\operatorname{obs}_U(T;w,a) for its data path observation. The wrapper reencoding rU,VTr^T_{U,V} from an odd path UU to an odd path VV is the operation on data terms defined by (1). rU,VT(w)=build⁡V(T;x.obs⁡U(T;w,x)).r^T_{U,V}(w) =\operatorname{build}_V \bigl(T;x.\operatorname{obs}_U(T;w,x)\bigr).(1)✦

A logical syntax LL is a choice of falsity ⊥\bot and incoming and outgoing proof paths IL,OLI_L,O_L.✦ A universal quantifier syntax KK is a choice of proof paths IK,OKI_K,O_K.✦ Implication and quantification are the labelled constructions in (2); a nondependent arrow has a codomain independent of its bound variable. Φ⇒Ψ=OL(IL(Φ)→ppΨ),∀Kx:T.Φ=OK(Πdpx:T.IK(Φ)).\begin{aligned} \Phi\Rightarrow\Psi &=O_L\bigl(I_L(\Phi)\to_{pp}\Psi\bigr),\\ \forall_K x:T.\Phi &=O_K\bigl(\Pi_{dp}x:T.I_K(\Phi)\bigr). \end{aligned}(2)

The logical connectives and guarded quantification are defined by (3). Formula equivalence denotes uniform typed proof-term transformers in both directions. ¬Φ=Φ⇒⊥,⊤=⊥⇒⊥,Φ∧Ψ=¬(Φ⇒¬Ψ),Φ∨Ψ=¬(¬Φ∧¬Ψ),Φ⇔Ψ=(Φ⇒Ψ)∧(Ψ⇒Φ),∃Kx:T.Φ=¬∀Kx:T.¬Φ,cond⁡(G,Φ,Ψ)=(G∧Φ)∨(¬G∧Ψ),∀Kx:T∣G(x).Φ(x)=∀Kx:T.(G(x)⇒Φ(x)).\begin{aligned} \neg\Phi&=\Phi\Rightarrow\bot,& \top&=\bot\Rightarrow\bot,\\ \Phi\wedge\Psi&=\neg(\Phi\Rightarrow\neg\Psi),& \Phi\vee\Psi&=\neg(\neg\Phi\wedge\neg\Psi),\\ \Phi\Leftrightarrow\Psi &=(\Phi\Rightarrow\Psi)\wedge(\Psi\Rightarrow\Phi),& \exists_Kx:T.\Phi&=\neg\forall_Kx:T.\neg\Phi,\\ \operatorname{cond}(G,\Phi,\Psi) &=(G\wedge\Phi)\vee(\neg G\wedge\Psi),& \forall_Kx:T\mid G(x).\Phi(x) &=\forall_Kx:T.\bigl(G(x)\Rightarrow\Phi(x)\bigr). \end{aligned}(3)

Channels and Relational Lifting

A uniform probe PP is a choice of a seed sort, an initial path of either parity, odd raw and back paths, an even function path, a positive lifting path, and a data tail.✦ A relational coding RR is a choice of a uniform probe PP and odd logical and predicate paths ℓ,p\ell,p.✦ The raw path rr of a relational coding RR is the raw path of its uniform probe PP. These three paths form the shared logical channel.✦ For a relational coding RR and a base type TT, the logical, raw, and predicate types are ℓ[T]\ell[T], r[T]r[T], and 𝒫T=p[r[T]]\mathcal P_T=p[r[T]]. Channel evaluation ETE_T and predicate construction Pred⁡T\operatorname{Pred}_T are given by (4); the latter takes an open formula on logical elements. ET(q,x)=obs⁡p(r[T];q,rℓ,rT(x)),Pred⁡T[x.Φ(x)]=build⁡p(r[T];c.Φ(rr,ℓT(c))).\begin{aligned} E_T(q,x) &=\operatorname{obs}_p\bigl(r[T];q,r^T_{\ell,r}(x)\bigr),\\ \operatorname{Pred}_T[x.\Phi(x)] &=\operatorname{build}_p \bigl(r[T];c.\Phi(r^T_{r,\ell}(c))\bigr). \end{aligned}(4) The logical channel encoding of a raw term cc at TT is its wrapper reencoding from the raw path rr to the logical path ℓ\ell.

The channel roundtrip is round⁡T(x)=rr,ℓT(rℓ,rT(x))\operatorname{round}_T(x) =r^T_{r,\ell}(r^T_{\ell,r}(x)). Fix universal quantifier syntaxes KY,KPK_Y,K_P. Roundtrip invariance Round⁡T(q)\operatorname{Round}_T(q) and observational equivalence ≈T,G\approx_{T,G} with an admissibility guard GG are the formulas in (5). Round⁡T(q)=∀KYx:ℓ[T].(ET(q,x)⇔ET(q,round⁡T(x))),y≈T,Gz=∀KPq:𝒫T∣G(q).(ET(q,y)⇔ET(q,z)).\begin{aligned} \operatorname{Round}_T(q) &=\forall_{K_Y}x:\ell[T]. \bigl(E_T(q,x)\Leftrightarrow E_T(q,\operatorname{round}_T(x))\bigr),\\ y\approx_{T,G}z &=\forall_{K_P}q:\mathcal P_T\mid G(q). \bigl(E_T(q,y)\Leftrightarrow E_T(q,z)\bigr). \end{aligned}(5)

A double data channel D=(U,V)D=(U,V) consists of two odd paths, with carrier D[T]=V[U[T]]D[T]=V[U[T]]. For a double data channel D=(U,V)D=(U,V) at a type TT, the fourfold carrier is D4[T]D^4[T], the predicate code type is U[D4[T]]U[D^4[T]], and the parameter type is V[U[D4[T]]]V[U[D^4[T]]]. Signed payload embedding uses the builder along VV with the positive or negated contravariant observation along UU.✦ Its bit observation tests against constant truth.✦ Signed payload recovery is the logical conditional selecting double channel evaluation or its negation by that bit.✦ Double channel evaluation observes along VV against a predicate built along UU.✦

Query tags use four bits, the binary digits zero through three of an index among 0,…,80,\ldots,8, in that order.✦ The corresponding tagged embedding iterates signed embedding four times.✦ Tag predicates combine the selected bit conditions with successive signed recoveries.✦ For a double channel D=(U,V)D=(U,V), an odd predicate path WW, a type TT, and a predicate qq, the tagged payload code for query tt is built along UU over D4[T]D^4[T]. Its body is the disjunction of the tag-t+1t+1 marker and the conjunction of the tag-zero marker with four successive signed recoveries of observation by qq along WW; payload decoding builds a predicate along WW at TT whose body observes the code along UU against the tag-zero embedding of its argument. A tagged query observes a parameter against the corresponding encoded predicate.✦ A structural query realization is the second-path builder whose body is the finite marked disjunction of seven branches, each branch conjoining its tag marker with its formula on the decoded predicate.✦ The disjunction ends in ⊥\bot.

The double channel of PP is D=(back,r)D=(\mathrm{back},r).✦ For a type AA, write TAT_A for its initial-path wrapper.✦ The probe raw type is r[TA]r[T_A]✦; its parameter type is the double-channel parameter type at r[TA]r[T_A]✦, and its single bundle type is the double carrier of that parameter type.✦ The common probe type CC of a uniform probe PP is a dependent data product over the positive wrapper of the seed sort whose codomain at a parameter zz is the function-path wrapper of the data arrow from the single bundle type at the positive projection of zz to the data tail carrier. Uniform probe abstraction binds that parameter and then a single bundle argument, encoding its formula through the tail and building along the function path.✦ Probe specialization applies a probe in data mode to the positive injection of AA✦; probe application observation decodes its result after function-path observation.✦

For a type AA and parameter mm, the relational incidence formula ◇A,m(v,a)\Diamond_{A,m}(v,a) is the probe application observation of vv at AA against the relational argument bundle of mm and aa.✦ The relational argument bundle of a parameter mm and an element aa at a type AA is the data term built along the raw path over the back-path wrapper of the probe parameter type of AA. Its body is a logical conditional whose guard, true branch, and false branch are respectively the contravariant observations along the back path of the dummy observation, mm, and the relational point encoding of aa.✦ The dummy observation at AA is the term built along the raw path over the predicate code type of the probe double channel at r[TA]r[T_A], with constant truth body. The relational point encoding of aa at AA is the term built along the raw path over the predicate code type of the probe double channel at r[TA]r[T_A]. Its body conjoins marker seven, using the constant truth marker build⁡r(TA;x.⊤)\operatorname{build}_r(T_A;x.\top), with predicate-path observation of the decoded input against the raw channel encoding of aa.✦

Write Qtm(q)Q_t^m(q) for structural query tt of mm against qq, using the predicate path at probe raw type r[TA]r[T_A].✦ The structural admissibility condition is Gm(q)=Round⁡TA(q)∧Q0m(q)G_m(q)=\operatorname{Round}_{T_A}(q)\wedge Q_0^m(q).✦ The equivalence class predicate [a]m[a]_m has body z≈TA,Gmaz\approx_{T_A,G_m}a✦; the union of two class predicates has the disjunction of their bodies.✦ The class query 𝒞tm(a)\mathcal C_t^m(a) is Qt+1m([a]m)Q_{t+1}^m([a]_m) for t=0,1,2t=0,1,2.✦ The two edge formulas and the relational pair predicate are defined in (6). ℰbm(y,z)=𝒞0m(y)∧(𝒞1+bm(z)∧Q4+bm([y]m∪[z]m)),b∈{0,1},Pair⁡A,m(q,a)=Pred⁡TA[z.(∃KYy:ℓ[TA].(ℰ0m(y,z)∧ETA(q,y)))∨ℰ1m(a,z)].\begin{aligned} \mathcal E_b^m(y,z) &=\mathcal C_0^m(y)\wedge \bigl(\mathcal C_{1+b}^m(z)\wedge Q_{4+b}^m([y]_m\cup[z]_m)\bigr), \qquad b\in\{0,1\},\\ \operatorname{Pair}_{A,m}(q,a) &=\operatorname{Pred}_{T_A}\bigl[z. (\exists_{K_Y}y:\ell[T_A]. (\mathcal E_0^m(y,z)\wedge E_{T_A}(q,y))) \vee\mathcal E_1^m(a,z)\bigr]. \end{aligned}(6)

The section predicate Sect⁡A,m(v)\operatorname{Sect}_{A,m}(v), the section pair query SB⁡A,m(v,a)\operatorname{SB}_{A,m}(v,a), and the relational element lift Lift⁡A,m(a)\operatorname{Lift}_{A,m}(a) are respectively the channel predicate, formula, and labelled term defined by (7). Sect⁡A,m(v)=Pred⁡TA[a.◇A,m(v,a)],SB⁡A,m(v,a)=Q6m(Pair⁡A,m(Sect⁡A,m(v),a)),Lift⁡A,m(a)=build⁡ℓ(C;v.SB⁡A,m(v,a)).\begin{aligned} \operatorname{Sect}_{A,m}(v) &=\operatorname{Pred}_{T_A}[a.\Diamond_{A,m}(v,a)],\\ \operatorname{SB}_{A,m}(v,a) &=Q_6^m\bigl(\operatorname{Pair}_{A,m} (\operatorname{Sect}_{A,m}(v),a)\bigr),\\ \operatorname{Lift}_{A,m}(a) &=\operatorname{build}_\ell \bigl(C;v.\operatorname{SB}_{A,m}(v,a)\bigr). \end{aligned}(7)

For a predicate ii, its uniform predicate probe ziz_i abstracts the type parameter and single bundle argument and uses recovery access with the parameter-dependent predicate pullback Pred⁡TA[a.EC(i,Lift⁡A,m(a))]\operatorname{Pred}_{T_A}[a.E_C(i,\operatorname{Lift}_{A,m}(a))].✦ Here AA is the positive projection of the bound type parameter, and mm is the bound parameter. Recovery access uses the dummy parameter test as its outer conditional guard, with truth as its dummy branch. Its inner probe has falsity as its dummy branch and the payload query as its other branch; the non-dummy branches retain the negated dummy test through the conditional of (3). For a double channel D=(U,V)D=(U,V) at a type TT, the dummy parameter test is the observation of a fresh parameter along VV against the bottom predicate code, the data path builder along UU over D4[T]D^4[T] with constant falsity body.

The probe order i≼xi\preceq x is the logical-path observation obs⁡ℓ(C;x,zi)\operatorname{obs}_\ell(C;x,z_i).✦ Put X=ℓ[C]X=\ell[C].✦ Predicate equivalence, probe element equivalence, predicate extensionality Ext\mathrm{Ext}, and probe order validity Valid\mathrm{Valid} are the formulas in (8). i≃j=∀KYx:X.(EC(i,x)⇔EC(j,x)),x≈Xy=∀KPi:𝒫C.(i≼x⇔i≼y),Ext(i)=∀KYx:X.∀KYy:X.(x≈Xy⇒(EC(i,x)⇔EC(i,y))),Valid(x)=∀KPi:𝒫C.∀KPj:𝒫C.(i≃j⇒(i≼x⇔j≼x)).\begin{aligned} i\simeq j &=\forall_{K_Y}x:X. \bigl(E_C(i,x)\Leftrightarrow E_C(j,x)\bigr),\\ x\approx_Xy &=\forall_{K_P}i:\mathcal P_C. \bigl(i\preceq x\Leftrightarrow i\preceq y\bigr),\\ \mathrm{Ext}(i) &=\forall_{K_Y}x:X.\forall_{K_Y}y:X. \bigl(x\approx_Xy\Rightarrow (E_C(i,x)\Leftrightarrow E_C(i,y))\bigr),\\ \mathrm{Valid}(x) &=\forall_{K_P}i:\mathcal P_C.\forall_{K_P}j:\mathcal P_C. \bigl(i\simeq j\Rightarrow (i\preceq x\Leftrightarrow j\preceq x)\bigr). \end{aligned}(8)

The Specialized Observation System

A three-copy observation system OO is a choice of a relational coding RR and inner and outer double channels Din,DoutD_{\mathrm{in}},D_{\mathrm{out}}.✦ Its copy source is ℓ\ell and its first copy path is rr. The tagged observation carrier YY and tagged copies ιt\iota_t are given in (9), where emb⁡Db\operatorname{emb}_D^b denotes signed payload embedding with positive sign when bb holds and negative sign otherwise. Y=Dout[Din[r[C]]],ιt(x)=emb⁡Doutt=2(Din[r[C]],emb⁡Dint=1(r[C],rℓ,rC(x))),t∈{0,1,2}.\begin{aligned} Y&=D_{\mathrm{out}}[D_{\mathrm{in}}[r[C]]],\\ \iota_t(x) &=\operatorname{emb}_{D_{\mathrm{out}}}^{t=2} \bigl(D_{\mathrm{in}}[r[C]], \operatorname{emb}_{D_{\mathrm{in}}}^{t=1} (r[C],r^C_{\ell,r}(x))\bigr), \qquad t\in\{0,1,2\}. \end{aligned}(9)

The specialized probe observation H(i,y)H(i,y) performs outer signed recovery and then inner signed recovery, with raw-path observation against ziz_i as its innermost test.✦ The outer marker bout(y)b_{\mathrm{out}}(y) is the outer channel bit✦; the inner marker bin(y)b_{\mathrm{in}}(y) is recovered through the outer channel.✦ Tagged observational equivalence is defined by (10). y≈Yz=(bin(y)⇔bin(z))∧((bout(y)⇔bout(z))∧∀KPi:𝒫C.(H(i,y)⇔H(i,z))).\begin{aligned} y\approx_Yz ={}&(b_{\mathrm{in}}(y)\Leftrightarrow b_{\mathrm{in}}(z))\wedge\\ &\bigl((b_{\mathrm{out}}(y)\Leftrightarrow b_{\mathrm{out}}(z))\wedge \forall_{K_P}i:\mathcal P_C. (H(i,y)\Leftrightarrow H(i,z))\bigr). \end{aligned}(10)✦

A specialized relational coding BB consists of OO and a chosen type A0A_0.✦ For a specialized relational coding BB with chosen type A0A_0, the specialized base type is TA0T_{A_0}, and the specialized channel evaluation is e(v,y)=ETA0(v,y)e(v,y)=E_{T_{A_0}}(v,y). The left copy predicate is iv=Pred⁡C[x.e(v,ι1(x))]i_v=\operatorname{Pred}_C[x.e(v,\iota_1(x))].✦ Observation invariance 𝒢\mathcal G, class representation 𝒞t\mathcal C_t, edge representation ℱt\mathcal F_t, and relational closure ℛ\mathcal R are the structural formulas in (11). 𝒢(v)=∀KYy:Y.∀KYz:Y.(y≈Yz⇒(e(v,y)⇔e(v,z))),𝒞t(v)=∃KYx:X.∀KYw:Y.(e(v,w)⇔w≈Yιt(x)),ℱt(v)=∃KYx:X.∀KYw:Y.(e(v,w)⇔(w≈Yι0(x)∨w≈Yιt(x))),ℛ(v)=Ext(iv)⇒∀KYx:X.(Valid(x)⇒(e(v,ι2(x))⇒iv≼x)).\begin{aligned} \mathcal G(v) &=\forall_{K_Y}y:Y.\forall_{K_Y}z:Y. \bigl(y\approx_Yz\Rightarrow (e(v,y)\Leftrightarrow e(v,z))\bigr),\\ \mathcal C_t(v) &=\exists_{K_Y}x:X.\forall_{K_Y}w:Y. \bigl(e(v,w)\Leftrightarrow w\approx_Y\iota_t(x)\bigr),\\ \mathcal F_t(v) &=\exists_{K_Y}x:X.\forall_{K_Y}w:Y. \bigl(e(v,w)\Leftrightarrow (w\approx_Y\iota_0(x)\vee w\approx_Y\iota_t(x))\bigr),\\ \mathcal R(v) &=\mathrm{Ext}(i_v)\Rightarrow \forall_{K_Y}x:X. \bigl(\mathrm{Valid}(x)\Rightarrow (e(v,\iota_2(x))\Rightarrow i_v\preceq x)\bigr). \end{aligned}(11)

The structural parameter m0m_0 is the structural query realization in the probe double channel at r[TA0]r[T_{A_0}], using predicate path pp, constant truth marker build⁡r(TA0;x.⊤)\operatorname{build}_r(T_{A_0};x.\top), and the seven branches, in order, 𝒢\mathcal G, 𝒞0\mathcal C_0, 𝒞1\mathcal C_1, 𝒞2\mathcal C_2, ℱ1\mathcal F_1, ℱ2\mathcal F_2, ℛ\mathcal R.✦ Specialized incidence and specialized lifting are the fixed-parameter constructions in (12). ◇(v,y)=◇A0,m0(v,y),Lift⁡(y)=Lift⁡A0,m0(y).\Diamond(v,y)=\Diamond_{A_0,m_0}(v,y), \qquad \operatorname{Lift}(y)=\operatorname{Lift}_{A_0,m_0}(y).(12)

The Definition

Definition 1. Fix a specialized relational coding BB, logical syntax LL, and universal quantifier syntaxes KY,KPK_Y,K_P.

The response predicate Resp⁡(v)\operatorname{Resp}(v) of a term vv is the channel predicate in (13). Resp⁡(v)=Pred⁡C[x.◇(v,ι0(x))].\operatorname{Resp}(v) =\operatorname{Pred}_C[x.\Diamond(v,\iota_0(x))].(13)✦

The data shift δ\delta is the operation on labelled terms defined by (14). δ(x)=Lift⁡(ι0(x)).\delta(x)=\operatorname{Lift}(\iota_0(x)).(14)✦

Pulling a predicate vv back along δ\delta gives the shifted predicate Shift⁡(v)\operatorname{Shift}(v) in (15). Shift⁡(v)=Pred⁡C[x.EC(v,δ(x))].\operatorname{Shift}(v) =\operatorname{Pred}_C[x.E_C(v,\delta(x))].(15)✦

For a predicate ii, define its guarded induction formula Ind⁡(i)\operatorname{Ind}(i) by (16). Ind⁡(i)=∀KYx:X.(Valid(x)⇒(i≼x⇒EC(i,x))).\operatorname{Ind}(i) =\forall_{K_Y}x:X. \bigl(\mathrm{Valid}(x)\Rightarrow (i\preceq x\Rightarrow E_C(i,x))\bigr).(16)✦

The well-foundedness object 𝗐𝖿\mathsf{wf} is the labelled term defined by the logical-path data construction in (17). 𝗐𝖿=build⁡ℓ(C;v.Ind⁡(Resp⁡(v))).\mathsf{wf} =\operatorname{build}_\ell \bigl(C;v.\operatorname{Ind}(\operatorname{Resp}(v))\bigr).(17)✦

What Is Checked

These definitions are stated over labelled terms and the fixed specialized relational coding, logical syntax, and two universal quantifier syntaxes.