OctoInformBeta

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

Lemma 54: Compared data predicates give induction formulas with typed open proof transformers in both directions

Pointwise comparison transports guarded induction.

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 uses data predicates whose observations are formulas of an internal logical calculus. Its induction condition concerns a predicate at logical probe elements satisfying an order validity condition.

Fix a pure type specification P=(S,π’œ,β„›)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications, annotated abstractions Ξ»x:A.M\lambda x:A.M, and dependent products Ξ x:A.B\Pi x:A.B.✦ The labelled syntax distinguishes argument and result modes by the labels dddd, dpdp and pppp, denoting data to data, data to proof and proof to proof. Label erasure deletes these labels.✦ Contexts are newest-first; a valid context is obtained from the empty context by adjoining a type AA for which Ξ“βŠ’A:s\Gamma\vdash A:s for some sort ss.✦

Typing is written Ξ“βŠ’M:A\Gamma\vdash M:A. The product rule uses any (s1,s2,s3)βˆˆβ„›(s_1,s_2,s_3)\in\mathcal R with Ξ“βŠ’A:s1\Gamma\vdash A:s_1 and x:A,Ξ“βŠ’B:s2x:A,\Gamma\vdash B:s_2; abstraction and application retain the product’s label. Conversion changes the expected type to a convertible type that has a sort. Full Ξ²\beta reduction contracts an application of an annotated abstraction with the same label and acts in every annotation and binder body; convertibility is its equivalence closure. Capture-avoiding simultaneous substitution includes single-variable instantiation. Renaming under a binder fixes its new variable and shifts renamed older indices; index zero denotes the newest variable.✦ Named binders here denote this syntax with capture avoided. The nondependent labelled arrow Aβ†’lBA\to_l B is the product Ξ lx:A.B\Pi^l x:A.B in which xx does not occur in BB.

A mode assignment Ξ³\gamma gives each variable data or proof mode. The mode judgement γ⊒mM:m\gamma\vdash_{\mathrm m}M:m assigns variables their given modes and sorts data mode. An application requires its function in the label’s result mode and its argument in the label’s argument mode. An abstraction requires a data annotation and a body in the result mode under extension by the argument mode. A dependent product has data mode when its domain and its codomain have data mode under the corresponding binder extension. A term MM is data-only if every application, abstraction and product in MM has label dddd.✦

For formulas FF and GG in context Ξ“\Gamma with mode assignment Ξ³\gamma, proof mode inhabitation, a typed open proof transformer, and typed logical equivalence are the relations in (1); the fresh temporary variable uu has proof mode. PrΞ“,Ξ³(F)β‡”βˆƒt(Ξ“βŠ’t:Fandγ⊒mt:π—‰π—‹π—ˆπ—ˆπ–Ώ),Tr⁡Ξ“,Ξ³(F,G)β‡”βˆƒt(u:F,Ξ“βŠ’t:Gandu:π—‰π—‹π—ˆπ—ˆπ–Ώ,γ⊒mt:π—‰π—‹π—ˆπ—ˆπ–Ώ),F≃Γ,Ξ³G⇔Tr⁡Ξ“,Ξ³(F,G)andTr⁡Ξ“,Ξ³(G,F).\begin{aligned} \operatorname{Pr}_{\Gamma,\gamma}(F) &\Longleftrightarrow \exists t\;\bigl(\Gamma\vdash t:F\quad\text{and}\quad \gamma\vdash_{\mathrm m}t:\mathsf{proof}\bigr),\\ \operatorname{Tr}_{\Gamma,\gamma}(F,G) &\Longleftrightarrow \exists t\;\bigl(u:F,\Gamma\vdash t:G\quad\text{and}\quad u:\mathsf{proof},\gamma\vdash_{\mathrm m}t:\mathsf{proof}\bigr),\\ F\simeq_{\Gamma,\gamma}G &\Longleftrightarrow \operatorname{Tr}_{\Gamma,\gamma}(F,G) \ \text{and}\ \operatorname{Tr}_{\Gamma,\gamma}(G,F). \end{aligned}(1)

Profiles and Logical Operations

A term TT is weakly normalizing if it reaches a full Ξ²\beta normal form by finitely many reductions; write T#T^\# for a chosen such normal form. A normal form admits no further reduction.✦ The sort profile πΓ(T)\pi_\Gamma(T) of a weakly normalizing term TT, the axiom successor profile Ax⁡(s)\operatorname{Ax}(s) of a sort ss, and the product output profile Out⁡(I,J)\operatorname{Out}(I,J) of profiles I,JI,J are the sets in (2). πΓ(T)={s∈Sβˆ£Ξ“βŠ’T#:s},Ax⁡(s)={t∈S∣(s,t)βˆˆπ’œ},Out⁡(I,J)={c∈Sβˆ£βˆƒa∈Iβˆƒb∈J(a,b,c)βˆˆβ„›}.\begin{aligned} \pi_\Gamma(T)&=\{s\in S\mid\Gamma\vdash T^\#:s\},\\ \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\}. \end{aligned}(2) A feasible profile II is a nonempty set of sorts realized by a normal type in a valid context.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible profiles satisfying K=Out⁡(I,J)K=\operatorname{Out}(I,J).✦ In the primary signed graph, proper inclusion between feasible profiles gives a positive edge towards the smaller profile; a feasible triple gives a negative domain edge Iβ†’KI\to K and a positive codomain edge Jβ†’KJ\to K.✦ Positive reachability permits finitely many positive edges, including none.✦

Fix a collection CC of profiles. An observation layer II for a collection CC of profiles is a profile positively reachable in the primary graph 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 JJ for a collection CC of profiles is a profile admitting a feasible triple (I,J,K)(I,J,K) with I,K∈CI,K\in C.✦

A fixed feasible witness family WW is a family of types TIT_I and values eIe_I indexed by profiles II. For every feasible II, the type TIT_I is data-only and its erasure is normal; Ξ“βŠ’TI:s\Gamma\vdash T_I:s for every s∈Is\in I, and Ξ“βŠ’eI:TI\Gamma\vdash e_I:T_I. Both TIT_I and eIe_I have data mode under Ξ³\gamma. A type AA is sorted at a profile II in Ξ“\Gamma when Ξ“βŠ’A:s\Gamma\vdash A:s for every sort s∈Is\in I.

A proof wrapper RR is a finite sequence of positive and negative extensions of the identity.✦ Applied to a formula FF, a positive extension with annotation DD gives Dβ†’dpR[F]D\to_{dp}R[F], and a negative extension with annotation EE gives R[F]β†’ppER[F]\to_{pp}E, where RR is the preceding wrapper.✦ A formed proof wrapper RR is a proof wrapper that follows feasible product triples, with the annotations chosen by the witness family WW, and may restrict its target profile by inclusion. Positive steps follow the codomain and negative steps the domain; the domain and output profiles of every negative step lie in CC. Path parity counts negative steps modulo two.

An ambient logical calculus LL has a fixed feasible witness family WW and open proof transformers between its chosen types at any two logical terminal profiles. Its domain, base and product profiles d,b,kd,b,k lie in CC and form a feasible triple (d,b,k)(d,b,k). It has even input and output proof paths from bb to dd and from kk to bb. Its falsity formula is βŠ₯=Tb\bot=T_b.✦ A quantifier route at a domain profile II chooses a feasible triple (I,J,K)(I,J,K) and even proof paths from bb to JJ and from KK to bb; LL provides such a route at every direct observation layer.✦

The logical implication and universal quantifier associated with these paths are the formulas in (3). Here Rin,RoutR_{\mathrm{in}},R_{\mathrm{out}} are the logical paths and Uin,UoutU_{\mathrm{in}},U_{\mathrm{out}} the paths of a quantifier route KK; path application under a named binder includes its capture-avoiding renaming. Fβ‡’LG=Rout[Rin[F]β†’ppG],βˆ€Kx:A.F(x)=Uout[Ξ dpx:A.Uin[F(x)]],Β¬LF=(Fβ‡’LβŠ₯),⊀L=(βŠ₯β‡’LβŠ₯),F∧LG=Β¬L(Fβ‡’LΒ¬LG),F∨LG=Β¬L(Β¬LF∧LΒ¬LG),F⇔LG=(Fβ‡’LG)∧L(Gβ‡’LF).\begin{aligned} F\Rightarrow_L G &=R_{\mathrm{out}}[R_{\mathrm{in}}[F]\to_{pp}G],\\ \forall_K x:A.\,F(x) &=U_{\mathrm{out}}\bigl[\Pi^{dp}x:A.\,U_{\mathrm{in}}[F(x)]\bigr],\\ \neg_L F&=(F\Rightarrow_L\bot), &\quad \top_L&=(\bot\Rightarrow_L\bot),\\ F\wedge_L G&=\neg_L(F\Rightarrow_L\neg_LG), &F\vee_L G&=\neg_L(\neg_LF\wedge_L\neg_LG),\\ F\Leftrightarrow_LG &=(F\Rightarrow_LG)\wedge_L(G\Rightarrow_LF). \end{aligned}(3) A guarded universal formula is a universally quantified formula with body G(x)β‡’LF(x)G(x)\Rightarrow_LF(x). Existential quantification is Β¬Lβˆ€Kx:A.Β¬LF(x)\neg_L\forall_Kx:A.\,\neg_LF(x), and the logical conditional with guard GG and branches F,HF,H is (G∧LF)∨L(Β¬LG∧LH)(G\wedge_LF)\vee_L(\neg_LG\wedge_LH). Logical negation Β¬LF\neg_L F of a formula FF is its logical implication to falsity. Logical conjunction F∧LGF\wedge_L G is the negation of the implication from FF to the negation of GG. Encoded logical equivalence F⇔LGF\Leftrightarrow_L G is the logical conjunction of the implications from FF to GG and from GG to FF.

Observation Channels and Specialized Probes

A data tail at a profile JJ is a choice of a terminal sort ss with {s}∈C\{s\}\in C and Ax⁡(s)β‰ βŒ€\operatorname{Ax}(s)\ne\varnothing, a positive path from Ax⁡(s)\operatorname{Ax}(s) to JJ, and even proof paths from bb to {s}\{s\} and back. The decoding proof path contains a negative step. The tail carrier is the positive wrapper of ss✦; encoding applies the incoming proof path and positive injection✦, while decoding applies positive projection and the outgoing proof path.✦

A retained data path UU is a finite path with positive steps retaining a domain and a dummy value, and negative steps retaining a data tail.✦ Its wrapped type U[T]U[T] is TT at the identity; a positive step gives Dβ†’ddU[T]D\to_{dd}U[T], and a negative step gives U[T]β†’ddEU[T]\to_{dd}E, where EE is the tail carrier.✦ Formation follows feasible product triples and target inclusions, using the witness family at positive steps and a formed tail at the codomain profile of each negative step.✦ A positive data path UU is a retained data path containing only positive steps.✦ Its injection is iterated constant annotated abstraction✦, and its projection applies the retained dummy values.✦

The builder along a data path returns its input at the identity and forms constant data abstractions at positive steps. At a negative step it abstracts a wrapped input and tail-encodes its observation. For an input type TT, a wrapped value ww, and an observation callback aa, the observation obs⁡U(T,w,a)\operatorname{obs}_U(T,w,a) instantiates aa with ww at the identity. At a positive step it applies ww to the retained dummy value and continues; at a negative step it applies ww to the recursively built argument and tail-decodes the result. Reencoding between odd paths U,VU,V builds along VV the observation callback of ww along UU.✦ The open composition of callbacks ff and gg replaces the distinguished input of ff by gg, keeping their common ambient variables fixed.

An observation channel HH consists of odd logical, raw and predicate paths β„“,r,p\ell,r,p.✦ Its logical, raw and predicate types, together with channel evaluation, are defined in (4). XH(T)=β„“[T],CH(T)=r[T],PH(T)=p[r[T]],EH(T,i,x)=obs⁡p(r[T],i,reencode⁡β„“,r(T,x)).\begin{aligned} X_H(T)&=\ell[T],& C_H(T)&=r[T],& P_H(T)&=p[r[T]],\\ E_H(T,i,x) &=\operatorname{obs}_p\bigl(r[T],i,\operatorname{reencode}_{\ell,r}(T,x)\bigr). \end{aligned}(4) An encoded predicate ii over a type TT in an observation channel HH is the term of PH(T)P_H(T) built along pp after composing its body FF with reencoding from rr to β„“\ell.✦ The channel roundtrip reencodes from β„“\ell to rr and back.✦ Roundtrip invariance of a predicate requires logically equivalent evaluations before and after this roundtrip at every logical element.✦ An admissible predicate ii in an observation channel HH is a predicate that is roundtrip invariant and satisfies its supplied guard.✦ Observational equivalence of elements quantifies over predicates satisfying that actual guard and compares their evaluations.✦ The logical channel encoding of a raw element cc at TT is its reencoding from the raw path rr to the logical path β„“\ell.✦

A uniform probe is a choice of a seed sort ss, an initial data path Ξ±\alpha of fixed parity, odd raw and return paths r,qr,q, an even function path ff, a positive lifting path aa, and a data tail with carrier EE.✦ The double channel (q,r)(q,r) has carrier D(T)=r[q[T]]D(T)=r[q[T]]; write D4D^4 for its fourth iterate. The probe raw, parameter, single-bundle and function types, and the common probe type QQ, are defined in (5). Raw⁡(A)=r[Ξ±[A]],Par⁡(A)=r[q[D4(Raw⁡(A))]],Single⁡(A)=D(Par⁡(A)),Fun⁡(A)=Single⁡(A)β†’ddE,Q=Ξ ddz:a[s].f[Fun⁡(project⁡a(z))].\begin{aligned} \operatorname{Raw}(A)&=r[\alpha[A]],\\ \operatorname{Par}(A)&=r[q[D^4(\operatorname{Raw}(A))]],\\ \operatorname{Single}(A)&=D(\operatorname{Par}(A)),\\ \operatorname{Fun}(A)&=\operatorname{Single}(A)\to_{dd}E,\\ Q&=\Pi^{dd}z:a[s].\,f[\operatorname{Fun}(\operatorname{project}_a(z))]. \end{aligned}(5) Probe specialization applies a probe to the positive injection of its type argument✦; probe observation then observes its specialization along ff and decodes the resulting function application through the tail.✦ Uniform probe abstraction binds the lifted type parameter and builds the tail-encoded data function along ff.✦

A shared relational coding RR is a choice of a uniform probe and odd logical and predicate paths, with the same raw path rr as the probe.✦ Its relational base type at AA is Ξ±[A]\alpha[A].✦ The probe formation requires feasible triples (I,J,k)(I,J,k) and (p0,n,g)(p_0,n,g) and a nonempty Ax⁡(s)\operatorname{Ax}(s). Its initial, raw, return and function paths run from {s}\{s\} to kk, from kk to p0p_0, from p0p_0 to kk, and from gg to JJ, respectively; the positive lifting path runs from Ax⁡(s)\operatorname{Ax}(s) to II, and the tail ends at nn. For profiles jj and hh, channel formation requires paths kβ†’jk\to j, kβ†’p0k\to p_0 and p0β†’hp_0\to h.✦

A specialized relational code BB is a choice of a type A*A_* and a three-copy observation system with relational component RR.✦ Its first copy uses rr, its middle copy applies an inner double channel to the first copy, and its observation carrier applies an outer double channel to the middle copy. Observation formation requires the inner paths p0β†’kβ†’p0p_0\to k\to p_0 and the outer paths p0β†’kβ†’jp_0\to k\to j. Specialized formation further requires Ξ“βŠ’A*:s\Gamma\vdash A_*:s and data mode for A*A_*. Writing T*=Ξ±[A*]T_*=\alpha[A_*], the observation carrier must equal XH(T*)X_H(T_*); the second outer path is the relational logical path, and its first outer path applied to the middle copy of QQ equals T*T_*. The observation system’s tagged copy syntax has source path β„“\ell, first path rr, and the observation system’s inner and outer double channels.✦ The specialized base type T*T_* is the relational base type of the chosen type A*A_*.✦

Relational Lifting

Fix quantifier routes KY,KPK_Y,K_P for logical and predicate channel types. For a type AA, put TA=Ξ±[A]T_A=\alpha[A]. The double channel (q,r)(q,r) has tagged observation queries QtA,m(p)Q_t^{A,m}(p), obtained by observing the parameter mm against the tagged payload encoding of pp, using the relational predicate path at r[TA]r[T_A].✦ At raw type TT, the predicate code type is q[D4(T)]q[D^4(T)]; its bottom code is the first-path builder with constant falsity, and its dummy observation is the second-path builder with constant truth. Tags t=0,…,7t=0,\ldots,7 use the nonzero query indices t+1t+1; index zero selects the payload.✦ A query index has its four binary digits in increasing order of significance.✦ The payload encoder builds along qq at the fourfold double carrier. Its body is the disjunction of the payload tag conjoined with fourfold recovery of the predicate-path observation callback and the nonzero query tag.✦ Tagged embeddings iterate signed embeddings along these four bits; tag predicates test each bit and recover the remaining tag recursively. For an odd data path UU, the payload decoder at TT builds along UU from a callback that observes the encoded payload along the first double-channel path at the fourfold carrier of TT, against the input embedded with payload query zero.

Roundtrip invariance, structural admissibility and observational equivalence at TAT_A are the formulas in (6). Here ρA\rho_A is the channel roundtrip on XH(TA)X_H(T_A). RoundInv⁡A(p)=βˆ€KYy:XH(TA).(EH(TA,p,y)⇔LEH(TA,p,ρA(y))),Good⁡A,m(p)=RoundInv⁡A(p)∧LQ0A,m(p),y∼A,mz=βˆ€KPp:PH(TA).Good⁡A,m(p)β‡’L(EH(TA,p,y)⇔LEH(TA,p,z)).\begin{aligned} \operatorname{RoundInv}_A(p) &=\forall_{K_Y}y:X_H(T_A).\\ &\qquad\bigl(E_H(T_A,p,y)\Leftrightarrow_L E_H(T_A,p,\rho_A(y))\bigr),\\ \operatorname{Good}_{A,m}(p) &=\operatorname{RoundInv}_A(p)\wedge_L Q_0^{A,m}(p),\\ y\mathrel{\sim_{A,m}}z &=\forall_{K_P}p:P_H(T_A).\,\operatorname{Good}_{A,m}(p)\Rightarrow_L\\ &\qquad\bigl(E_H(T_A,p,y)\Leftrightarrow_L E_H(T_A,p,z)\bigr). \end{aligned}(6) The class predicate [y]A,m[y]_{A,m} is the encoded predicate with body w∼A,myw\sim_{A,m}y; the class union predicate [y,z]A,m[y,z]_{A,m} has body (w∼A,my)∨L(w∼A,mz)(w\sim_{A,m}y)\vee_L(w\sim_{A,m}z). Class queries apply tags 1,2,31,2,3 to the class predicate.✦ The two tagged edge formulas and the pair predicate are defined in (7), where Pred⁡H(T,F)\operatorname{Pred}_H(T,F) denotes the encoded predicate with body FF over TT. Edge⁡0(y,z)=Q1A,m([y]A,m)∧L(Q2A,m([z]A,m)∧LQ4A,m([y,z]A,m)),Edge⁡1(y,z)=Q1A,m([y]A,m)∧L(Q3A,m([z]A,m)∧LQ5A,m([y,z]A,m)),Pair⁡A,m(p,a)=Pred⁡H(TA,z↦(βˆƒKYy:XH(TA).Edge⁡0(y,z)∧LEH(TA,p,y))∨LEdge⁡1(a,z)).\begin{aligned} \operatorname{Edge}_0(y,z) &=Q_1^{A,m}([y]_{A,m})\wedge_L \bigl(Q_2^{A,m}([z]_{A,m})\wedge_L Q_4^{A,m}([y,z]_{A,m})\bigr),\\ \operatorname{Edge}_1(y,z) &=Q_1^{A,m}([y]_{A,m})\wedge_L \bigl(Q_3^{A,m}([z]_{A,m})\wedge_L Q_5^{A,m}([y,z]_{A,m})\bigr),\\ \operatorname{Pair}_{A,m}(p,a) &=\operatorname{Pred}_H\Bigl(T_A,\ z\mapsto \bigl(\exists_{K_Y}y:X_H(T_A).\, \operatorname{Edge}_0(y,z)\wedge_L E_H(T_A,p,y)\bigr) \vee_L\operatorname{Edge}_1(a,z)\Bigr). \end{aligned}(7)

The relational point of yy is its raw channel encoding placed in the double channel’s point construction with the constant truth marker.✦ That marker is the raw-path builder with constant body ⊀L\top_L.✦ The point predicate conjoins its marker test at tag 77 with the decoded payload observation.✦ A relational argument bundle combines the dummy observation, a parameter mm, and this point in the double channel✦; its branch predicate is the logical conditional on the first observation, with the other two as branches.✦ The diamond observation β—‡A(m,v,y)\Diamond_A(m,v,y) is the probe observation of vv at AA against this bundle.✦ The section predicate Sect⁡A(m,v)\operatorname{Sect}_A(m,v) of the diamond observation β—‡A(m,v,y)\Diamond_A(m,v,y) is the encoded predicate over TAT_A with body y↦◇A(m,v,y)y\mapsto\Diamond_A(m,v,y).✦

The relational element lift Lift⁡A(m,a)\operatorname{Lift}_A(m,a) is the term built along the logical path at QQ with body v↦Q6A,m(Pair⁡A,m(Sect⁡A(m,v),a))v\mapsto Q_6^{A,m}(\operatorname{Pair}_{A,m}(\operatorname{Sect}_A(m,v),a)). This body is the section pair query. The predicate pullback of ii along this lift is Pred⁡H(TA,a↦EH(Q,i,Lift⁡A(m,a)))\operatorname{Pred}_H(T_A,a\mapsto E_H(Q,i,\operatorname{Lift}_A(m,a))).✦ Its recovery at a single-bundle argument ww is the double channel’s recovery access observation, tested with the data parameter callback assigning this pullback to mm.✦

The dummy parameter test observes its argument against the constant falsity predicate code.✦ Recovery access uses this test as its guard: the outer access conditional has truth as its first branch and the composed observation callback as its second; the inner probe conditional has falsity as its first branch and the tag 77 query as its second. The uniform predicate probe ziz_i is the uniform probe abstraction whose body is this pullback recovery of ii, at the positive projection of its bound type parameter.✦ The inner observation probe is built along the first double-channel path over the parameter type, with the inner probe conditional as its body. The access probe over a type AA is built along the first double-channel path at AA, with the outer access conditional as its body. The bundle access observation of ww over AA observes ww along the second double-channel path, at the first-path wrapper of AA, against the access probe.

Validity and Induction

For the common probe type QQ, put X=XH(Q)X=X_H(Q) and PX=PH(Q)P_X=P_H(Q) using (4). Pointwise predicate comparison is the formula Cmp⁡(i,iβ€²)\operatorname{Cmp}(i,i') in (8). Cmp⁡(i,iβ€²)=βˆ€KYx:X.(EH(Q,i,x)⇔LEH(Q,iβ€²,x)).\operatorname{Cmp}(i,i')= \forall_{K_Y}x:X.\, \bigl(E_H(Q,i,x)\Leftrightarrow_L E_H(Q,i',x)\bigr).(8)✦

The probe order formula is iβ‰Όx=obs⁡β„“(Q,x,zi)i\preccurlyeq x=\operatorname{obs}_{\ell}(Q,x,z_i).✦ The pointwise validity condition, validity at a predicate, and order validity Valid⁡(x)\operatorname{Valid}(x) are defined in (9). V(x,i,iβ€²)=Cmp⁡(i,iβ€²)β‡’L((iβ‰Όx)⇔L(iβ€²β‰Όx)),V(x,i)=βˆ€KPiβ€²:PX.V(x,i,iβ€²),Valid⁡(x)=βˆ€KPi:PX.V(x,i).\begin{aligned} V(x,i,i') &=\operatorname{Cmp}(i,i')\Rightarrow_L \bigl((i\preccurlyeq x)\Leftrightarrow_L(i'\preccurlyeq x)\bigr),\\ V(x,i)&=\forall_{K_P}i':P_X.\,V(x,i,i'),\\ \operatorname{Valid}(x)&=\forall_{K_P}i:P_X.\,V(x,i). \end{aligned}(9) The guarded induction condition and its universally quantified induction formula are those in (10). Step⁡(i,x)=Valid⁡(x)β‡’L((iβ‰Όx)β‡’LEH(Q,i,x)),Ind⁡(i)=βˆ€KYx:X.Step⁡(i,x).\begin{aligned} \operatorname{Step}(i,x) &=\operatorname{Valid}(x)\Rightarrow_L \bigl((i\preccurlyeq x)\Rightarrow_L E_H(Q,i,x)\bigr),\\ \operatorname{Ind}(i)&=\forall_{K_Y}x:X.\,\operatorname{Step}(i,x). \end{aligned}(10)

The Claim

Theorem 1 (Lemma 54). Fix an ambient logical calculus LL, the quantifier routes KY,KPK_Y,K_P, and a formed specialized relational code BB as above. Let v,cv,c be data-mode terms with Ξ“βŠ’v:PX\Gamma\vdash v:P_X and Ξ“βŠ’c:PX\Gamma\vdash c:P_X. Suppose Pr⁡Ξ“,Ξ³(Cmp⁡(v,c))\operatorname{Pr}_{\Gamma,\gamma}(\operatorname{Cmp}(v,c)) holds. Then the induction formulas satisfy (11). Ind⁡(v)≃Γ,Ξ³Ind⁡(c).\operatorname{Ind}(v)\simeq_{\Gamma,\gamma}\operatorname{Ind}(c).(11)✦

What Is Checked

Lemma 54 is stated over labelled typing and its data and proof mode discipline, an ambient logical calculus with fixed feasible witnesses and quantifier routes, and a specialized relational code satisfying its probe, observation and carrier shape conditions.