OctoInformBeta

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

Lemma 55: Validity and shifted induction for extensional data predicates in the specialized relational construction

Guarded induction at the well-foundedness 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

In the diagonal construction, induction is expressed through data predicates and their observations on logical probe elements. The order observation of a predicate at an element is distinct from its evaluation there.

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. Terms have variables, sort constants, applications, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ Variable names are source notation; the terms use de Bruijn indices and newest-first contexts. Renaming and simultaneous substitution act without capture under binders; instantiation replaces index zero and lowers the older indices. Full Ξ²\beta reduction includes annotations and binder bodies, and Ξ²\beta convertibility is its equivalence closure. A normal term MM is a term admitting no Ξ²\beta step; a weakly normalizing term MM is a term that reduces to a normal term. Erasure removes the labels from labelled terms.✦

The labels dddd, dpdp, and pppp specify data to data, data to proof, and proof to proof.✦ The mode discipline assigns variables their modes in Ξ³\gamma and sorts data mode. Applications use their label’s argument and result modes; abstractions use the argument mode for the bound variable and the result mode for the body. Abstraction annotations and product domains and codomains are checked in data mode; products themselves have data mode. A product’s bound variable has the label’s argument mode. A data-only term MM is a labelled term with label dddd at every labelled constructor.✦ Extending Ξ³\gamma assigns the fresh variable its declared mode and shifts the older assignments.✦

Proof-mode inhabitation βŠ¨Ξ“,Ξ³F\models_{\Gamma,\gamma}F is the existence of a proof-mode term of type FF.✦ A typed open transformer from FF to GG uses a temporary proof input of type FF; formula equivalence means uniform typed transformers in both directions, as in (1). βŠ¨Ξ“,Ξ³Fβ‡”βˆƒp(Ξ“βŠ’p:F∧γ⊒mp:π—‰π—‹π—ˆπ—ˆπ–Ώ),Tr⁡Ξ“,Ξ³(F,G)β‡”βˆƒt(h:F,Ξ“βŠ’t:G∧(h:π—‰π—‹π—ˆπ—ˆπ–Ώ,Ξ³)⊒mt:π—‰π—‹π—ˆπ—ˆπ–Ώ),F≃Γ,Ξ³G⇔Tr⁡Ξ“,Ξ³(F,G)∧Tr⁡Ξ“,Ξ³(G,F).\begin{aligned} \models_{\Gamma,\gamma}F &\quad\Longleftrightarrow\quad \exists p\;\bigl(\Gamma\vdash p:F\ \land \gamma\vdash_{\mathrm m}p:\mathsf{proof}\bigr),\\ \operatorname{Tr}_{\Gamma,\gamma}(F,G) &\quad\Longleftrightarrow\quad \exists t\;\bigl(h:F,\Gamma\vdash t:G\ \land (h:\mathsf{proof},\gamma)\vdash_{\mathrm m}t:\mathsf{proof}\bigr),\\ F\simeq_{\Gamma,\gamma}G &\quad\Longleftrightarrow\quad \operatorname{Tr}_{\Gamma,\gamma}(F,G)\ \land \operatorname{Tr}_{\Gamma,\gamma}(G,F). \end{aligned}(1)

Profiles and Logical Operations

The axiom successors, product outputs, and normal form sort profile are the sets in (2); T#T^\# denotes the chosen full Ξ²\beta normal form when one exists, with a fixed fallback otherwise. Ax⁡(s)={t∈S∣(s,t)βˆˆπ’œ},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›},πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s}.\begin{aligned} \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\},\\ \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\}. \end{aligned}(2) A valid context Ξ”\Delta is a context built from the empty context by repeatedly adjoining a type AA whenever the current context Ξ“\Gamma satisfies Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss. A feasible profile is a nonempty set πΔ(T)\pi_\Delta(T) for a normal term TT in a valid context Ξ”\Delta.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles with K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦ Sorting a labelled type at II requires its typing at every sort in II, and permits additional sorts.✦

Fix a collection CC of profiles. In the primary signed profile graph, strict feasible inclusions IβŠ‹JI\supsetneq J give positive edges Iβ†’JI\to J. A feasible triple (I,J,K)(I,J,K) gives a negative edge Iβ†’KI\to K and a positive edge Jβ†’KJ\to K. An observation layer II is a profile reachable in the primary signed profile graph by a possibly empty path of positive edges 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 is a middle profile JJ of a feasible triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

A fixed feasible witness family is a family of pairs consisting, for every feasible II, of a data-only type TIT_I with normal erasure, sorted at II, and a value vIv_I with Ξ“βŠ’vI:TI\Gamma\vdash v_I:T_I; both choices have data mode.✦ An ambient logical calculus LL supplies such witnesses, uniform typed transformers between their types at logical terminal profiles, and a feasible triple (d,b,k)(d,b,k) in CC. It has paths from bb to dd and from kk to bb built from the identity by positive data-to-proof and negative proof-to-proof arrow extensions, with an even number of negative extensions, and quantifier routes for direct observation layers. A quantifier route for II chooses a triple (I,J,K)(I,J,K) and even proof wrapper paths from bb to JJ and from KK to bb.✦

A proof wrapper UU is a path built from the identity by positive and negative arrow extensions: a positive extension forms a data-to-proof arrow into the preceding wrapped type, and a negative extension forms a proof-to-proof arrow out of it. Its paths may restrict the target profile; extensions follow feasible product triples, and a negative extension requires its source and target in CC. Parity counts negative steps. Write Uin,UoutU_{\mathrm{in}},U_{\mathrm{out}} for the logical wrappers and Kin,KoutK_{\mathrm{in}},K_{\mathrm{out}} for a quantifier’s wrappers. The falsity type βŠ₯\bot is TbT_b, and the logical operations in (3) use these fixed paths. Here [x:T]F[x:T]F denotes a formula body with the indicated fresh variable. Fβ‡’G:=Uout(Uin(F)β†’ppG),βˆ€Kx:T.F:=Kout(Ξ dpx:T.Kin(F)),Β¬F:=Fβ‡’βŠ₯,⊀:=βŠ₯β‡’βŠ₯,F∧G:=Β¬(Fβ‡’Β¬G),F∨G:=Β¬(Β¬F∧¬G),F↔G:=(Fβ‡’G)∧(Gβ‡’F),βˆƒKx:T.F:=Β¬βˆ€Kx:T.Β¬F.\begin{aligned} F\Rightarrow G &:=U_{\mathrm{out}}\bigl(U_{\mathrm{in}}(F)\to_{pp}G\bigr),& \forall_K x:T.\,F &:=K_{\mathrm{out}}\bigl(\Pi_{dp}x:T.\,K_{\mathrm{in}}(F)\bigr),\\ \neg F&:=F\Rightarrow\bot,& \top&:=\bot\Rightarrow\bot,\\ F\wedge G&:=\neg(F\Rightarrow\neg G),& F\vee G&:=\neg(\neg F\wedge\neg G),\\ F\leftrightarrow G&:=(F\Rightarrow G)\wedge(G\Rightarrow F),& \exists_K x:T.\,F&:=\neg\forall_K x:T.\,\neg F. \end{aligned}(3) A guarded universal quantifier is a universal formula with body Gβ‡’FG\Rightarrow F. The logical conditional with guard GG and branches F,HF,H is (G∧F)∨(Β¬G∧H)(G\wedge F)\vee(\neg G\wedge H); a finite marked disjunction joins marker and property at each index and ends in βŠ₯\bot. Fix quantifier routes KYK_Y and KPK_P, and write βˆ€Y\forall_Y and βˆ€P\forall_P for quantification along these routes, respectively.

Channels and Relational Lifting

A positive data path DD is a path built from the identity by adding data arrow domains with retained witness arguments; its target may be restricted to a subset. Its injection uses constant annotated abstractions, and its projection applies those arguments. A retained data path is a path starting with the identity and allowing positive data arrow extensions and negative extensions by data tails, with parity given by the number of negative extensions modulo two.✦ Positive extensions follow triples (A,J,K)(A,J,K) using TA,vAT_A,v_A; negative extensions follow triples (J,B,K)(J,B,K) using a data tail ending at BB. A data tail is a choice of a terminal sort uu with {u}∈C\{u\}\in C and nonempty Ax⁡(u)\operatorname{Ax}(u), a positive path from Ax⁡(u)\operatorname{Ax}(u) to its endpoint, an even encoding proof path from bb to {u}\{u\}, and an even decoding proof path back. The decoding path contains a negative step. Its carrier is the positive wrapper of uu; encoding applies the encoding proof path before injection, and decoding projects before applying the decoding proof path.

For a retained path DD and a type TT, write D(T)D(T) for the wrapped data type, Build⁡D(T,Q)\operatorname{Build}_D(T,Q) for the data realization of a body QQ, and Obs⁡D(T,w,a)\operatorname{Obs}_D(T,w,a) for the observation of an element ww against a test aa. The identity leaves types and realizations unchanged and observes by instantiation. At a positive extension the wrapped type adds a data domain, the data realization adds a constant abstraction, and observation applies the retained argument. At a negative extension the wrapped type is a data arrow to the tail carrier, the data realization sends an inner observation through the tail, and observation applies the input to an inner realization before decoding. An odd path’s observation body fixes ww and varies its test; its contravariant observation body fixes the test and varies ww. Reencoding from one odd path to another realizes the first path’s observation body along the second path.✦ Open composition substitutes one formula body into another.✦

A double channel consists of two successive odd retained paths.✦ The carrier of a double channel at a type TT is the type obtained by applying its two successive wrappers; the fourfold carrier of the double channel at TT is the type obtained by iterating that operation four times. Its bit observation tests the first channel’s constant truth realization along the second channel.✦ Signed payload embedding realizes a positive or negated observation body, and recovery uses its marker bit to select evaluation or negated evaluation. Query tags use four binary digits: query zero is the payload query, while a tag tt uses query t+1t+1. For a double channel at a type TT, the tagged payload encoder is the data realization along its first path at the fourfold carrier of TT whose body is the disjunction of the nonzero tag predicate and the conjunction of the payload tag predicate with depth-four recovery of the payload observation. A query observes a parameter against that encoder. Structural realization is the data realization along the second path at the predicate code type, with body the finite marked disjunction of its seven decoded branches. An encoded data point at TT is the data realization along the second path at the predicate code type of TT whose body conjoins the final tag’s marker with the payload observation after decoding. The dummy observation at TT is the data realization of the constant truth body along the second path at the predicate code type of TT. The bottom predicate code realizes constant falsity along the first path at the fourfold carrier; the dummy parameter test observes a parameter against that code. For a double channel at a type TT, the predicate code type is the first path’s wrapper of the fourfold carrier of TT. Double channel evaluation of vv against a formula body QQ at TT observes vv along the second path against the first path’s data realization of QQ at TT. The query bit string of a query qq among the nine indices is the list of its binary digits zero through three, in that order. Iterated signed embedding of a payload along an empty bit string leaves it unchanged; along a nonempty string it first embeds along the remaining bits, then applies signed embedding with the first bit at the carrier iterated once for each remaining bit. The query tagged embedding of a payload at TT is its iterated signed embedding along the query bit string. The payload decoder into an odd retained path at TT is the data realization along that path of the predicate code’s observation against the query tagged embedding at query zero.

A shared relational construction has a uniform probe and odd logical, raw, and predicate paths β„“,r,q\ell,r,q.✦ The probe has seed sort ss, an initial retained path, odd raw and return paths, an even function path, and a positive lifting path. Its common type VV is a data dependent product over the positively wrapped seed sort. At a bound parameter, its codomain applies the function path to the data arrow from the single-bundle type at the parameter’s positive projection to the data tail carrier. The probe double channel uses the return path followed by the raw path.✦ The probe raw type applies the initial path and then the raw path to a type AA; its parameter type applies the first and second probe double wrappers to that raw type’s fourfold carrier. A single-bundle type is the probe double wrapper of this parameter type.✦ Specialization applies a probe to the positive injection of a type parameter. The uniform probe for a formula body QQ is a data abstraction over the positively wrapped seed sort; at the positive projection AA of its bound parameter, its body is the data realization along the function path, at the probe function type of AA, of the data abstraction over the single-bundle type of AA whose body is the tail encoding of QQ. Probe observation specializes, observes along the function path, and decodes the resulting application through the tail.✦

The shared channel’s types and evaluation are given in (4). The channel predicate Pred⁡T(Q)\operatorname{Pred}_T(Q) realizes the body QQ along qq at RTR_T, after reencoding its fresh argument from rr to β„“\ell.✦ YT:=β„“(T),RT:=r(T),PT:=q(r(T)),Ev⁡T(p,y):=Obs⁡q(RT,p,toRaw⁡T(y)),toRaw⁡T:=reencode⁡β„“,r,T,toLog⁡T:=reencode⁡r,β„“,T,round⁡T(y):=toLog⁡T(toRaw⁡T(y)).\begin{aligned} Y_T&:=\ell(T),& R_T&:=r(T),& P_T&:=q(r(T)),\\ \operatorname{Ev}_T(p,y) &:=\operatorname{Obs}_q\bigl(R_T,p,\operatorname{toRaw}_T(y)\bigr),\\ \operatorname{toRaw}_T&:=\operatorname{reencode}_{\ell,r,T},& \operatorname{toLog}_T&:=\operatorname{reencode}_{r,\ell,T},\\ \operatorname{round}_T(y) &:=\operatorname{toLog}_T(\operatorname{toRaw}_T(y)). \end{aligned}(4) At a type AA let BAB_A be its initial wrapper type, and let mm be a probe parameter. Write QtA,m(p)Q_t^{A,m}(p) for its structural query at tag tt, for 0≀t≀60\leq t\leq6. A channel predicate pp is admissible when it satisfies roundtrip invariance and the tag-zero query.✦ Its guarded observational equivalence is defined in (5). Good⁡A,m(p):=(βˆ€Yy:YBA.Ev⁡BA(p,y)↔Ev⁡BA(p,round⁡BA(y)))∧Q0A,m(p),yβ‰ˆA,mz:=βˆ€Pp:PBA.Good⁡A,m(p)β‡’(Ev⁡BA(p,y)↔Ev⁡BA(p,z)).\begin{aligned} \operatorname{Good}_{A,m}(p) &:=\bigl(\forall_Y y:Y_{B_A}.\, \operatorname{Ev}_{B_A}(p,y)\leftrightarrow \operatorname{Ev}_{B_A}(p,\operatorname{round}_{B_A}(y))\bigr) \wedge Q_0^{A,m}(p),\\ y\approx_{A,m}z &:=\forall_P p:P_{B_A}.\, \operatorname{Good}_{A,m}(p)\Rightarrow \bigl(\operatorname{Ev}_{B_A}(p,y)\leftrightarrow \operatorname{Ev}_{B_A}(p,z)\bigr). \end{aligned}(5) The class predicate [y]A,m[y]_{A,m} is the channel predicate with body wβ‰ˆA,myw\approx_{A,m}y, and its class query at tt is Qt+1A,m([y]A,m)Q_{t+1}^{A,m}([y]_{A,m}). The class union predicate of two guarded observational equivalence classes is the channel predicate whose body is the disjunction of their class predicate bodies. The left edge formula Edge⁡0(y,z)\operatorname{Edge}_0(y,z) joins the class of yy at index zero to the class of zz at index one and tests their union at query four; the right edge formula Edge⁡1(y,z)\operatorname{Edge}_1(y,z) joins the class of yy at index zero to the class of zz at index two and uses query five.✦ The pair membership formula FA,m(p,a,z)F_{A,m}(p,a,z) and relational pair predicate Pair⁡A,m(p,a)\operatorname{Pair}_{A,m}(p,a) are defined in (6). FA,m(p,a,z):=(βˆƒYy:YBA.Edge⁡0(y,z)∧Ev⁡BA(p,y))∨Edge⁡1(a,z),Pair⁡A,m(p,a):=Pred⁡BA([z:YBA]FA,m(p,a,z)).\begin{aligned} F_{A,m}(p,a,z) &:=\bigl(\exists_Y y:Y_{B_A}.\, \operatorname{Edge}_0(y,z)\wedge\operatorname{Ev}_{B_A}(p,y)\bigr)\\ &\qquad\vee\operatorname{Edge}_1(a,z),\\ \operatorname{Pair}_{A,m}(p,a) &:=\operatorname{Pred}_{B_A}([z:Y_{B_A}]\,F_{A,m}(p,a,z)). \end{aligned}(6)

The diamond observation vβ‹„A,myv\diamond_{A,m}y is probe observation against the bundle containing the dummy observation, mm, and the point encoding of toRaw⁡BA(y)\operatorname{toRaw}_{B_A}(y).✦ The bundle’s conditional selects the parameter or point observation using the contravariant dummy observation as its guard.✦ The section predicate Sec⁡A,m(v)\operatorname{Sec}_{A,m}(v) of a probe vv is a channel predicate with body y↦vβ‹„A,myy\mapsto v\diamond_{A,m}y.✦ The relational lift in (7) realizes the tag-six query of the pair formed from that section and its argument. Sec⁡A,m(v):=Pred⁡BA([y:YBA]vβ‹„A,my),Lift⁡A,m(a):=Build⁡β„“(V,[v:V]Q6A,m(Pair⁡A,m(Sec⁡A,m(v),a))).\begin{aligned} \operatorname{Sec}_{A,m}(v) &:=\operatorname{Pred}_{B_A}([y:Y_{B_A}]\,v\diamond_{A,m}y),\\ \operatorname{Lift}_{A,m}(a) &:=\operatorname{Build}_{\ell}\bigl(V, [v:V]\,Q_6^{A,m}(\operatorname{Pair}_{A,m} (\operatorname{Sec}_{A,m}(v),a))\bigr). \end{aligned}(7) For a predicate ii on logical probe elements, the uniform predicate probe ziz_i abstracts the positively wrapped type parameter and recovers the pullback predicate with body a↦Ev⁡V(i,Lift⁡A,m(a))a\mapsto\operatorname{Ev}_V(i,\operatorname{Lift}_{A,m}(a)) from its single bundle. The inner recovery probe uses the dummy parameter test with falsity as its dummy branch; the outer access uses the same test with truth as its dummy branch. The recovered parameter supplies the pullback’s mm. Logical probe elements, their predicates, and the probe order are defined in (8). X:=β„“(V),PX:=q(r(V)),E(i,x):=Ev⁡V(i,x),iβ‰Όx:=Obs⁡β„“(V,x,zi).X:=\ell(V),\qquad P_X:=q(r(V)),\qquad E(i,x):=\operatorname{Ev}_V(i,x),\qquad i\preccurlyeq x:=\operatorname{Obs}_\ell(V,x,z_i).(8)

Validity and the Induction Object

Predicate equivalence i≑Xji\equiv_X j is the relation between predicates on the logical probe elements given by pointwise formula equivalence under KYK_Y.✦ Probe element equivalence x≑oyx\equiv_o y is the relation between logical probe elements requiring equivalence of all their order observations under KPK_P.✦ Extensionality Ext(i)\mathrm{Ext}(i) and validity Valid(x)\mathrm{Valid}(x) are the respect conditions in (9). i≑Xj:=βˆ€Yx:X.(E(i,x)↔E(j,x)),x≑oy:=βˆ€Pi:PX.((iβ‰Όx)↔(iβ‰Όy)),Ext(i):=βˆ€Yx:X.βˆ€Yy:X.(x≑oy)β‡’(E(i,x)↔E(i,y)),Valid(x):=βˆ€Pi:PX.βˆ€Pj:PX.(i≑Xj)β‡’((iβ‰Όx)↔(jβ‰Όx)).\begin{aligned} i\equiv_X j&:=\forall_Y x:X.\,(E(i,x)\leftrightarrow E(j,x)),\\ x\equiv_o y&:=\forall_P i:P_X.\, ((i\preccurlyeq x)\leftrightarrow(i\preccurlyeq y)),\\ \mathrm{Ext}(i)&:=\forall_Y x:X.\,\forall_Y y:X.\, (x\equiv_o y)\Rightarrow(E(i,x)\leftrightarrow E(i,y)),\\ \mathrm{Valid}(x)&:=\forall_P i:P_X.\,\forall_P j:P_X.\, (i\equiv_X j)\Rightarrow ((i\preccurlyeq x)\leftrightarrow(j\preccurlyeq x)). \end{aligned}(9)

A specialized relational construction BB fixes a chosen type A0A_0 and a three-copy observation system.✦ Require Ξ“βŠ’A0:s\Gamma\vdash A_0:s and data mode for A0A_0, where ss is the probe seed. Its copy source is β„“\ell, its first path is rr, and its inner and outer double channels form the middle wrapper 𝖬𝗂𝖽\mathsf{Mid} and tagged observation type YY in (10). Write π’Ÿin,π’Ÿout\mathcal D_{\mathrm{in}},\mathcal D_{\mathrm{out}} for the inner and outer channels, d1,d2d_1,d_2 for the outer channel’s first and second paths, and T0=BA0T_0=B_{A_0}. The specialized carrier conditions are the equalities in that display. 𝖬𝗂𝖽:=π’Ÿin(r(V)),Y:=π’Ÿout(𝖬𝗂𝖽),Y=β„“(T0),d2=β„“,d1(𝖬𝗂𝖽)=T0.\begin{aligned} \mathsf{Mid}&:=\mathcal D_{\mathrm{in}}(r(V)),& Y&:=\mathcal D_{\mathrm{out}}(\mathsf{Mid}),\\ Y&=\ell(T_0),& d_2&=\ell,& d_1(\mathsf{Mid})&=T_0. \end{aligned}(10) The observation paths use profiles I,J,k,p,n,g,j,hI,J,k,p,n,g,j,h with feasible triples (I,J,k)(I,J,k) and (p,n,g)(p,n,g) and nonempty Ax⁡(s)\operatorname{Ax}(s). The probe’s initial path runs from {s}\{s\} to kk, its raw path from kk to pp, its return path from pp to kk, and its function path from gg to JJ. Its positive lifting path runs from Ax⁡(s)\operatorname{Ax}(s) to II, and its tail ends at nn. The channel paths β„“\ell and qq run from kk to jj and from pp to hh; the inner double channel runs from pp through kk to pp, and the outer double channel from pp through kk to jj.

The tagged copy Ο„t(x)\tau_t(x) of a logical probe element xx, for t∈{0,1,2}t\in\{0,1,2\}, is the tagged observation obtained by reencoding xx from β„“\ell to rr and using signed inner and outer embeddings with positive bits exactly at t=1t=1 and t=2t=2, respectively.✦ The inner marker is recovered through the outer channel; the outer marker is its bit observation. The specialized observation obs⁡(i,y)\operatorname{obs}(i,y) of a predicate ii at a tagged observation yy is the formula obtained by recovering the copy payload against the uniform probe ziz_i.✦ Tagged observational equivalence ae⁡(y,z)\operatorname{ae}(y,z) is the relation between tagged observations requiring equivalence of both markers and, uniformly for i:PXi:P_X, equivalence of obs⁡(i,y)\operatorname{obs}(i,y) and obs⁡(i,z)\operatorname{obs}(i,z).✦

For a channel predicate vv at the specialized carrier and a tagged observation yy, write ev⁡(v,y)=Ev⁡T0(v,y)\operatorname{ev}(v,y)=\operatorname{Ev}_{T_0}(v,y).✦ The seven structural properties of vv are observation invariance G(v)G(v), class representations C0(v),C1(v),C2(v)C_0(v),C_1(v),C_2(v), edge representations D1(v),D2(v)D_1(v),D_2(v), and relational closure R(v)R(v), defined in (11). The left-copy predicate is rvr_v. G(v):=βˆ€Yy:Y.βˆ€Yz:Y.ae⁡(y,z)β‡’(ev⁡(v,y)↔ev⁡(v,z)),Ct(v):=βˆƒYx:X.βˆ€Yw:Y.(ev⁡(v,w)↔ae⁡(w,Ο„t(x))),Dt(v):=βˆƒYx:X.βˆ€Yw:Y.(ev⁡(v,w)↔(ae⁡(w,Ο„0(x))∨ae⁡(w,Ο„t(x)))),rv:=Pred⁡V([x:X]ev⁡(v,Ο„1(x))),R(v):=Ext(rv)β‡’βˆ€Yx:X.Valid(x)β‡’(ev⁡(v,Ο„2(x))β‡’rvβ‰Όx).\begin{aligned} G(v)&:=\forall_Y y:Y.\,\forall_Y z:Y.\, \operatorname{ae}(y,z)\Rightarrow (\operatorname{ev}(v,y)\leftrightarrow\operatorname{ev}(v,z)),\\ C_t(v)&:=\exists_Y x:X.\,\forall_Y w:Y.\, (\operatorname{ev}(v,w)\leftrightarrow \operatorname{ae}(w,\tau_t(x))),\\ D_t(v)&:=\exists_Y x:X.\,\forall_Y w:Y.\, \bigl(\operatorname{ev}(v,w)\leftrightarrow (\operatorname{ae}(w,\tau_0(x))\vee \operatorname{ae}(w,\tau_t(x)))\bigr),\\ r_v&:=\operatorname{Pred}_V([x:X]\,\operatorname{ev}(v,\tau_1(x))),\\ R(v)&:=\mathrm{Ext}(r_v)\Rightarrow \forall_Y x:X.\,\mathrm{Valid}(x)\Rightarrow \bigl(\operatorname{ev}(v,\tau_2(x))\Rightarrow r_v\preccurlyeq x\bigr). \end{aligned}(11) The structural parameter m0m_0 is the probe double channel’s structural realization of the branches (G,C0,C1,C2,D1,D2,R)(G,C_0,C_1,C_2,D_1,D_2,R), using the predicate path and the constant truth marker on the probe raw type of A0A_0.✦ Specialized incidence vβ‹„yv\diamond y and lifting Lift⁡(y)\operatorname{Lift}(y) are vβ‹„A0,m0yv\diamond_{A_0,m_0}y and Lift⁡A0,m0(y)\operatorname{Lift}_{A_0,m_0}(y).

The induction formula Ind⁡(i)\operatorname{Ind}(i) is the guarded universal formula in (12). The response predicate Resp⁡(v)\operatorname{Resp}(v) is the channel predicate given by incidence with the zeroth copy; the shifted predicate Shift⁡(i)\operatorname{Shift}(i) is the channel predicate given by evaluation at the specialized lift Ξ΄(x)\delta(x) of the zeroth tagged copy of a logical probe element xx. Ind⁡(i):=βˆ€Yx:X.Valid(x)β‡’((iβ‰Όx)β‡’E(i,x)),Ξ΄(x):=Lift⁡(Ο„0(x)),Resp⁡(v):=Pred⁡V([x:X]vβ‹„Ο„0(x)),Shift⁡(i):=Pred⁡V([x:X]E(i,Ξ΄(x))).\begin{aligned} \operatorname{Ind}(i) &:=\forall_Y x:X.\,\mathrm{Valid}(x)\Rightarrow ((i\preccurlyeq x)\Rightarrow E(i,x)),\\ \delta(x)&:=\operatorname{Lift}(\tau_0(x)),\\ \operatorname{Resp}(v) &:=\operatorname{Pred}_V([x:X]\,v\diamond\tau_0(x)),\\ \operatorname{Shift}(i) &:=\operatorname{Pred}_V([x:X]\,E(i,\delta(x))). \end{aligned}(12) The well-foundedness object WW is the logical data realization of the response induction body in (13). W:=Build⁡β„“(V,[v:V]Ind⁡(Resp⁡(v))).W:=\operatorname{Build}_\ell (V,[v:V]\,\operatorname{Ind}(\operatorname{Resp}(v))).(13)✦

The Claim

Theorem 1. Fix an ambient logical calculus and its quantifier routes, and specialized relational data satisfying the observation formation and carrier conditions above. Then βŠ¨Ξ“,Ξ³Valid(W).\models_{\Gamma,\gamma}\mathrm{Valid}(W).(14)✦ Let ii be a data-mode term with Ξ“βŠ’i:PX\Gamma\vdash i:P_X, and assume βŠ¨Ξ“,Ξ³Ext(i)\models_{\Gamma,\gamma}\mathrm{Ext}(i). Then (iβ‰ΌW)≃Γ,Ξ³Ind⁡(Shift⁡(i)).(i\preccurlyeq W)\simeq_{\Gamma,\gamma} \operatorname{Ind}(\operatorname{Shift}(i)).(15)✦ If Ind⁡(i)\operatorname{Ind}(i) is also inhabited in proof mode, then βŠ¨Ξ“,Ξ³E(i,W).\models_{\Gamma,\gamma}E(i,W).(16)✦

What Is Checked

Statements (14), (15), and (16) are over labelled typing and mode discipline in Ξ“,Ξ³\Gamma,\gamma, a logical calculus with its fixed feasible witnesses and quantifier routes, and specialized relational data whose probe and channel paths follow the specified feasible product profiles, whose chosen type has seed sorting and data mode, and whose carriers satisfy (10).