OctoInformBeta

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

Lemma 53: Validity, extensional predicates and predecessor comparison in a specialized relational coding

Diagonal shifting respects guarded comparison.

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 diagonal construction acts on logical probe elements, while predicate shifting constructs a predicate from evaluation at a diagonal image. Element comparison uses order observations, and predicate comparison uses channel evaluation.

Fix a pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), with arbitrary axiom and product-rule relations, a valid context Γ\Gamma, and a mode assignment γ\gamma. Terms have annotated abstractions and dependent products. The judgment Γ⊢M:A\Gamma\vdash M:A includes its expected type AA; calling MM a data term also requires data mode under γ\gamma. A formula FF is inhabited in proof mode, written ⊩F\Vdash F, when some pp satisfies Γ⊢p:F\Gamma\vdash p:F in proof mode.✦

A uniform typed transformer from formulas FF to GG is a proof-mode term of type GG with a temporary proof-mode input of type FF.✦ Typed logical equivalence F≃GF\simeq G means that such transformers exist in both directions.✦ The connectives and quantifiers below belong to a fixed ambient logical calculus LL; in particular, F↔GF\leftrightarrow G denotes its formula of mutual implication. Neither notation asserts equality or convertibility of data. The calculus has chosen falsity and incoming and outgoing proof wrappers, together with universal quantifier routes KYK_Y for logical elements and KPK_P for predicates.

A sort profile πΓ(T)\pi_\Gamma(T) is the set of all s∈Ss\in S with Γ⊢T#:s\Gamma\vdash T^\#:s, where T#T^\# is a chosen β\beta normal form when TT is weakly normalizing.✦ A feasible sort profile II is a nonempty sort profile of a β\beta normal type in a valid context.✦ A feasible product profile triple (I,J,K)(I,J,K) consists of feasible domain, codomain and product profiles with the output condition in (1). K=Out⁡(I,J)={c∈S∣∃a∈I∃b∈J.(a,b,c)∈ℛ}.K=\operatorname{Out}(I,J) =\{c\in S\mid \exists a\in I\;\exists b\in J.\,(a,b,c)\in\mathcal R\}.(1)✦ The axiom profile Ax⁡(s)\operatorname{Ax}(s) of a sort ss is the set of sorts tt for which (s,t)∈𝒜(s,t)\in\mathcal A.✦ The primary signed graph has a positive inclusion edge from a feasible profile II to a feasible profile JJ when J⊊IJ\subsetneq I, and a feasible product profile triple (I,J,K)(I,J,K) gives a negative domain edge from II to KK and a positive codomain edge from JJ to KK.✦ Positive reachability in a signed graph means reachability by a finite, possibly empty path containing only positive edges.✦ An observation layer II for a collection CC of sort profiles is a profile 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 for CC 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).✦

The logical calculus uses a fixed feasible witness family: at each feasible profile II, a data-only type WIW_I in data mode under γ\gamma whose erasure is a full β\beta normal form, and a data term wIw_I with Γ⊢wI:WI\Gamma\vdash w_I:W_I. Sorting at II requires Γ⊢WI:s\Gamma\vdash W_I:s for every s∈Is\in I.✦ Full β\beta reduction includes annotations and binder bodies.

Channels and Probe Order

A retained data path DD is a finite path generated from an identity path by positive steps retaining a domain type and a chosen argument, and negative steps retaining a data path tail.✦ Its wrapper sends TT to TT at the identity, replaces the preceding wrapper by the data function type from the retained domain to that wrapper at a positive step, and by the data function type from that wrapper to the retained tail carrier at a negative step.✦ Its parity counts negative path steps. An observation channel consists of odd logical, raw and predicate paths DlogD_{\mathrm{log}}, DrawD_{\mathrm{raw}} and DpredD_{\mathrm{pred}}.✦ Its logical element type XTX_T and predicate type PTP_T are the wrapper types in (2). XT=Dlog(T),Traw=Draw(T),PT=Dpred(Traw).X_T=D_{\mathrm{log}}(T),\qquad T_{\mathrm{raw}}=D_{\mathrm{raw}}(T),\qquad P_T=D_{\mathrm{pred}}(T_{\mathrm{raw}}).(2) A positive data path is a finite path of positive extensions, each retaining a fixed domain type and a chosen argument✦; its wrapper forms successive nondependent function types in data mode with those domains.✦ A data path tail consists of a terminal sort, a positive data path, and fixed encoding and decoding proof paths✦; its carrier is the positive wrapper of that sort✦, encoding follows the encoding proof path and positive injection✦, and decoding follows positive projection and the decoding proof path.✦ A data path tail ending at JJ is formed when the singleton of its terminal sort belongs to CC, that sort has a nonempty axiom profile, its positive path runs from the axiom profile to JJ, and its encoding and decoding proof paths run from the logical base to the singleton and back with even parity, with at least one negative step in the decoding path.✦

Wrapper reencoding sends an element from one retained path to another by observation along the source path and building along the target path.✦ Write toRaw⁡T:XT→Traw\operatorname{toRaw}_T:X_T\to T_{\mathrm{raw}} and toLog⁡T:Traw→XT\operatorname{toLog}_T:T_{\mathrm{raw}}\to X_T for the two channel reencodings. For a predicate p:PTp:P_T and an element x:XTx:X_T, channel evaluation 𝖤T(p,x)\mathsf E_T(p,x) is the formula obtained by observing pp along the predicate path against toRaw⁡T(x)\operatorname{toRaw}_T(x).✦ The encoded predicate Pred⁡T[x:XT.F(x)]\operatorname{Pred}_T[x:X_T.\,F(x)] is built along the predicate path with body F(toLog⁡T(r))F(\operatorname{toLog}_T(r)), where rr is the raw input.✦

The channel roundtrip on XTX_T is the map defined by round⁡T(x)=toLog⁡T(toRaw⁡T(x))\operatorname{round}_T(x)= \operatorname{toLog}_T(\operatorname{toRaw}_T(x)). For a predicate p:PTp:P_T, roundtrip invariance Resp⁡T(p)\operatorname{Resp}_T(p) is the formula in (3). Resp⁡T(p)=∀x:XT.(𝖤T(p,x)↔𝖤T(p,round⁡T(x))).\operatorname{Resp}_T(p)= \forall x:X_T.\, \bigl(\mathsf E_T(p,x)\leftrightarrow \mathsf E_T(p,\operatorname{round}_T(x))\bigr).(3)✦

Relational coding fixes a uniform probe type UU, a logical path, and a predicate path, sharing the probe’s raw path.✦ The uniform probe type UU is the dependent product in data mode over the positive wrapper of the seed sort along the lifting path. Its codomain at a bound parameter is the wrapper along the even function path of the data function type from the single-bundle type at the positive projection of that parameter to the data tail carrier. Its elements specialize to that parameter and observe a single-bundle argument. Write X=XUX=X_U, PX=PUP_X=P_U, and 𝖤=𝖤U\mathsf E=\mathsf E_U. Uniform probe syntax fixes a seed sort, an initial retained data path of chosen parity, odd raw and return paths, an even function path, a positive lifting path, and a data path tail. The specialization of a probe vv to a type AA is its application in data mode to the positive wrapper injection of AA along the lifting path.

For a type AA, its relational base type TAT_A is its wrapper along the probe’s initial path.✦ The relational incidence formula ◇A,m(v,y)\Diamond_{A,m}(v,y) observes the specialization of vv to AA against a bundle containing a dummy observation, the parameter mm, and the point encoding of yy.✦ The point encoding uses the raw channel encoding of yy and a constant truth marker. The section predicate of vv is the encoded predicate with body ◇A,m(v,y)\Diamond_{A,m}(v,y).✦

The relational lift ℓA,m(y)\ell_{A,m}(y) is a logical-path builder whose body asks the section pair query at tag 66.✦ That query tests mm against the relational pair predicate of the section predicate and yy.✦ The pair construction uses class and edge queries with their actual admissibility guard: roundtrip invariance conjoined with the structural query at tag 00. For the observation channel over TT and admissibility condition GG, guarded observational equivalence of y,z:XTy,z:X_T requires equivalent channel evaluations at yy and zz for every predicate p:PTp:P_T satisfying G(p)G(p).✦ The equivalence class predicate of y:XTy:X_T, with admissibility condition GG, is the encoded predicate whose body compares its bound element with yy by guarded observational equivalence.✦ The class union predicate of y,z:XTy,z:X_T, with admissibility condition GG, is the encoded predicate whose body is the disjunction of guarded observational equivalence with yy and with zz.✦ The pair membership condition for a predicate pp, an element aa, and a tested element zz holds when either some element satisfying pp has an edge of the first kind to zz, or aa has an edge of the second kind to zz, using the same admissibility condition and structural queries.✦

For a predicate i:PXi:P_X, the uniform predicate probe ziz_i is a data abstraction over the wrapped type parameter whose single-bundle body recovers the pullback of ii along relational lifting.✦ Recovery uses the dummy parameter test as its access guard. For a predicate i:PXi:P_X and an element x:Xx:X, the probe order formula i≼xi\preccurlyeq x is the observation of xx along the logical path against ziz_i.✦ Predicate comparison i≈Pji\approx_P j and element comparison x≈Xyx\approx_X y are the formulas in (4). i≈Pj=∀x:X.(𝖤(i,x)↔𝖤(j,x)),x≈Xy=∀i:PX.((i≼x)↔(i≼y)).\begin{aligned} i\approx_P j &=\forall x:X.\, \bigl(\mathsf E(i,x)\leftrightarrow\mathsf E(j,x)\bigr),\\ x\approx_X y &=\forall i:P_X.\, \bigl((i\preccurlyeq x)\leftrightarrow(i\preccurlyeq y)\bigr). \end{aligned}(4)

An extensional predicate i:PXi:P_X respects element comparison.✦ A valid element x:Xx:X has order observations that respect predicate comparison.✦ Their defining formulas Ext⁡(i)\operatorname{Ext}(i) and Valid⁡(x)\operatorname{Valid}(x) are given by (5); quantification over elements uses KYK_Y, and quantification over predicates uses KPK_P. Ext⁡(i)=∀x,y:X.(x≈Xy⇒(𝖤(i,x)↔𝖤(i,y))),Valid⁡(x)=∀i,j:PX.(i≈Pj⇒((i≼x)↔(j≼x))).\begin{aligned} \operatorname{Ext}(i) &=\forall x,y:X.\, \bigl(x\approx_X y\Rightarrow (\mathsf E(i,x)\leftrightarrow\mathsf E(i,y))\bigr),\\ \operatorname{Valid}(x) &=\forall i,j:P_X.\, \bigl(i\approx_P j\Rightarrow ((i\preccurlyeq x)\leftrightarrow(j\preccurlyeq x))\bigr). \end{aligned}(5)

Tagged Diagonal Data

A specialized relational coding BB fixes a three-copy observation system and a distinguished data type A0A_0 sorted at the probe’s seed sort.✦ Its specialized base type is T0=TA0T_0=T_{A_0}✦, and its tagged observation type is YY.✦ For t∈{0,1,2}t\in\{0,1,2\}, the copy embedding from XX to YY sends xx to τt(x)\tau_t(x) by reencoding xx from the logical path to the first copy path and then using inner and outer signed embeddings. Their embedding bits are true exactly for t=1t=1 and t=2t=2, respectively.

For a tagged element y:Yy:Y, the outer copy marker bout(y)b_{\mathrm{out}}(y) is the encoded bit observation of yy in the outer copy channel.✦ The inner copy marker bin(y)b_{\mathrm{in}}(y) is signed recovery along the outer copy channel with the inner channel bit observation as its test.✦ Let 𝖮(i,y)\mathsf O(i,y) be the three-copy observation of yy against ziz_i.✦ For tagged elements y,z:Yy,z:Y, tagged observational equivalence y≈Yzy\approx_Y z is the formula comparing their copy markers and all three-copy observations, as in (6). y≈Yz=(bin(y)↔bin(z))∧(bout(y)↔bout(z))∧∀i:PX.(𝖮(i,y)↔𝖮(i,z)).\begin{aligned} y\approx_Y z={}& (b_{\mathrm{in}}(y)\leftrightarrow b_{\mathrm{in}}(z))\ \wedge\, (b_{\mathrm{out}}(y)\leftrightarrow b_{\mathrm{out}}(z))\\ &\wedge\ \forall i:P_X.\, (\mathsf O(i,y)\leftrightarrow\mathsf O(i,z)). \end{aligned}(6)✦

Write 𝖤0=𝖤T0\mathsf E_0=\mathsf E_{T_0} for specialized channel evaluation.✦ The left copy predicate rvr_v of a predicate vv on YY is the encoded predicate in (7). rv=Pred⁡U[x:X.𝖤0(v,τ1(x))].r_v=\operatorname{Pred}_U[x:X.\,\mathsf E_0(v,\tau_1(x))].(7)✦

The structural parameter m0m_0 is the structural query realization in the probe’s double channel, using the predicate path, the raw type of A0A_0, and the constant truth marker.✦ Its seven branches, in order, are observation invariance GG, class representation C0,C1,C2C_0,C_1,C_2, edge representation E1,E2E_1,E_2, and relational closure RR.✦ These properties of vv are defined in (8); the universal and existential element binders use KYK_Y and the logical existential construction. G(v)=∀y,z:Y.(y≈Yz⇒(𝖤0(v,y)↔𝖤0(v,z))),Ct(v)=∃x:X.∀y:Y.(𝖤0(v,y)↔y≈Yτt(x)),Et(v)=∃x:X.∀y:Y.(𝖤0(v,y)↔(y≈Yτ0(x)∨y≈Yτt(x))),R(v)=Ext⁡(rv)⇒∀x:X.(Valid⁡(x)⇒(𝖤0(v,τ2(x))⇒rv≼x)).\begin{aligned} G(v)&=\forall y,z:Y.\, \bigl(y\approx_Y z\Rightarrow (\mathsf E_0(v,y)\leftrightarrow\mathsf E_0(v,z))\bigr),\\ C_t(v)&=\exists x:X.\,\forall y:Y.\, \bigl(\mathsf E_0(v,y)\leftrightarrow y\approx_Y\tau_t(x)\bigr),\\ E_t(v)&=\exists x:X.\,\forall y:Y.\, \bigl(\mathsf E_0(v,y)\leftrightarrow (y\approx_Y\tau_0(x)\vee y\approx_Y\tau_t(x))\bigr),\\ R(v)&=\operatorname{Ext}(r_v)\Rightarrow \forall x:X.\,\bigl(\operatorname{Valid}(x)\Rightarrow (\mathsf E_0(v,\tau_2(x))\Rightarrow r_v\preccurlyeq x)\bigr). \end{aligned}(8)

For a tagged element y:Yy:Y, the specialized lift ℓ(y)\ell(y) is the logical element ℓA0,m0(y)\ell_{A_0,m_0}(y)✦; for a probe vv, specialized incidence v⋄yv\diamond y is the formula ◇A0,m0(v,y)\Diamond_{A_0,m_0}(v,y).✦ The diagonal map δ\delta is a map from XX to XX that sends each element to the lift of its tag-zero copy, by (9). δ(x)=ℓ(τ0(x)).\delta(x)=\ell(\tau_0(x)).(9)✦

The shifted predicate σi\sigma i of a predicate i:PXi:P_X is a predicate on XX encoded with a body that evaluates ii at the diagonal image of its bound argument, as in (10). σi=Pred⁡U[x:X.𝖤(i,δ(x))].\sigma i=\operatorname{Pred}_U[x:X.\,\mathsf E(i,\delta(x))].(10)✦

A probe vv has a response predicate ρv\rho_v on XX, encoded with a body that tests incidence of vv with the tag-zero copy of its bound argument, as in (11). ρv=Pred⁡U[x:X.v⋄τ0(x)].\rho_v=\operatorname{Pred}_U[x:X.\,v\diamond\tau_0(x)].(11)✦

The Claim

Theorem 1. Assume the specialized coding satisfies its observation and channel formation conditions and its wrapper identities. For each data term xx with Γ⊢x:X\Gamma\vdash x:X, the validity assertion is (12). ⊩Valid⁡(δ(x)).\Vdash\operatorname{Valid}(\delta(x)).(12)✦ For data terms x,yx,y with Γ⊢x:X\Gamma\vdash x:X and Γ⊢y:X\Gamma\vdash y:X, assume ⊩x≈Xy\Vdash x\approx_X y. Their diagonal images satisfy (13). ⊩δ(x)≈Xδ(y).\Vdash\delta(x)\approx_X\delta(y).(13)✦ Let ii be a data term with Γ⊢i:PX\Gamma\vdash i:P_X and assume ⊩Ext⁡(i)\Vdash\operatorname{Ext}(i). For every data term xx with Γ⊢x:X\Gamma\vdash x:X, the evaluation equivalence is (14). 𝖤(σi,x)≃𝖤(i,δ(x)).\mathsf E(\sigma i,x)\simeq\mathsf E(i,\delta(x)).(14)✦ The extensionality assertion for this predicate is (15). ⊩Ext⁡(σi).\Vdash\operatorname{Ext}(\sigma i).(15)✦ The response predicate of ziz_i satisfies (16). ⊩ρzi≈Pσi.\Vdash\rho_{z_i}\approx_P\sigma i.(16)✦ For a data term xx with Γ⊢x:X\Gamma\vdash x:X, assume also ⊩Valid⁡(x)\Vdash\operatorname{Valid}(x). The predecessor equivalence is (17). (i≼δ(x))≃(σi≼x).(i\preccurlyeq\delta(x))\simeq(\sigma i\preccurlyeq x).(17)✦

What Is Checked

The claims are stated over the ambient logical calculus and a specialized coding whose distinguished type is sorted at the seed sort in data mode, whose probe and retained paths satisfy their formation conditions at the prescribed feasible product profiles, whose inner and outer copy channels consist of successive odd paths, and whose wrapper identities identify YY with Dlog(T0)D_{\mathrm{log}}(T_0), the second outer path with the relational logical path, and the first outer wrapper of the middle-copy type with T0T_0.