DEKL 2.0: Trace-Indexed Knowledge Evolution in Dependent Type Theory
Chen Peng · 2026
Read DEKL 2.0: Trace-Indexed Knowledge Evolution in Dependent Type Theory by Chen Peng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22530.txt.
Introduction
Peng presents DEKL 2.0, a type-theory framework for knowledge evolving along traces, step records of a system. Its central claim splits behavior in two: the proof calculus stays monotone under standard rules, while non-monotone change arises in meaning when traces extend. Finite and infinite traces count as first-class objects, and knowledge is read as a presheaf over the finite-trace category. The paper establishes trace-reachability and completeness, characterizes non-monotonicity through non-surjective restriction maps, and interprets the system via a free category from a transition system.
Catalog record
| CREATOR | Chen Peng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35818 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22530
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DEKL 2.0: Trace-Indexed Knowledge Evolution in Dependent Type Theory Chen Peng Abstract DEKL 2.0 is a dependent type-theoretic framework for trace-indexed knowledge evolution. Its central claim is that the proof calculus remains monotone under standard structural rules, while non-monotonic behavior arises semantically from trace extension. Finite and infinite traces are first-class objects in the computational universe; knowledge is interpreted as a presheaf over the finite-trace category; and proposition-level reasoning is handled categorically with fixed-point support. We establish trace–reachability correspondence and completeness, characterize non-monotonicity by non-surjective restriction maps, and present a semantic interpretation based on the free category generated by a transition system. The framework unifies executable traces, typed witnesses, and knowledge revision in one dependent language. Keywords. Dependent type theory, trace semantics, presheaf semantics, knowledge evolution, non-monotonicity, categorical semantics. 1 Introduction Many dynamic systems require reasoning about facts that depend on execution history. A statement may hold now, then fail after a new event. Standard dependent type theory is monotone at the level of derivability (weakening, substitution, subject reduction); therefore, this kind of knowledge invalidation is not represented as a proof-theoretic rule. DEKL resolves this tension by separating proof-theoretic monotonicity from semantic dynamics: • The proof system remains ordinary dependent type theory. • Traces are represented as first-class terms in the computational universe. • Knowledge is indexed by traces and interpreted contravariantly. Hence “non-monotonicity” is not a non-monotonic logic rule; it is the behavior of trace-indexed knowledge under trace extension. The main technical contributions are: • a layered syntax for computational objects, trace-indexed knowledge, and fixed-point reasoning at the proposition layer; • a bidirectional correspondence between finite traces and constructive reachability witnesses; • a semantic characterization of non-monotonicity via failure of surjectivity of restriction maps; • a categorical interpretation combining CwF syntax with free trace categories and presheaf semantics. Paper organization follows a definition–theorem–proof-sketch style. Section 2 gives intuition; Section 3 fixes syntax and judgments; Section 4 presents typing and operational rules; Section 5 proves the presheaf characterization of non-monotonicity; Section 6 gives full categorical semantics; Section 7 states metatheory; Section 8 provides application templates; Section 9 discusses related work; Section 10 discusses current limitations; and Section 11 concludes. 2 Informal Overview Consider an execution: \sigma_{0}\to\sigma_{1}\to\cdots\to\sigma_{n}. A finite trace from \sigma_{0} to \sigma_{n} is a term t:\mathsf{FinTrace}(\sigma_{0},\sigma_{n}). This term is a constructive typed witness that \sigma_{n} is reachable from \sigma_{0} . 2.1 A simple \tau / \tau^{\prime} example Let \tau be a trace prefix and \tau^{\prime}=\tau\cdot e its one-step extension. Suppose \Gamma\vdash p:K_{f}(\tau) for a knowledge family K_{f} . In general, it does not follow that \Gamma\vdash p:K_{f}(\tau^{\prime}). The knowledge witness p does not disappear; rather, its type index changes. So invalidation is an index mismatch, not inconsistency of the core logic. 2.2 Intuition for non-monotonicity Knowledge is modeled as a presheaf over traces: K_{f}:T_{f}^{op}\to\mathbf{Type}. For each extension \epsilon:\tau\to\tau^{\prime} , there is a restriction map \mathsf{restrict}(\epsilon,-):K_{f}(\tau^{\prime})\to K_{f}(\tau). Contravariance means we move backwards along extensions. If this map is not surjective, some old knowledge at \tau has no extension witness at \tau^{\prime} , which is exactly non-monotonic behavior. 2.3 Running intuition: revocation under trace extension To make the index shift concrete, consider a credential lifecycle with events \mathsf{Issue}(c) , \mathsf{Use}(c) , and \mathsf{Revoke}(c) . Let \mathsf{Auth}(c,\tau):\mathsf{Type}_{\ell} denote that credential c is valid on trace \tau . On a prefix containing only issue/use events, one may construct q:\mathsf{Auth}(c,\tau). If the trace extends to \tau^{\prime}=\tau\cdot\mathsf{Revoke}(c), the original typed witness q generally does not inhabit \mathsf{Auth}(c,\tau^{\prime}) . This illustrates the central point used throughout the paper: typed witnesses are stable as terms, but their typing index changes with trace evolution. 3 Syntax and Judgments The core judgment forms are standard: \Gamma\vdash A:U\qquad\Gamma\vdash t:A. We use three stratified layers: \displaystyle\mathsf{Uc}_{0}:\mathsf{Uc}_{1}:\mathsf{Uc}_{2}:\cdots,\quad\mathsf{Type}_{\ell,0}:\mathsf{Type}_{\ell,1}:\cdots,\quad\mathsf{Prop}:\mathsf{Type}_{\ell,0}. 3.1 Notation table Symbol Meaning \mathsf{State},\mathsf{Event} base types of states and events \mathsf{Step}(\sigma,e,\sigma^{\prime}) one-step transition typed witness \mathsf{FinTrace}(\sigma_{0},\sigma_{n}) finite traces from start to end state \mathsf{InfTrace} coinductive infinite-trace type T_{f} finite-trace category generated by (\mathsf{State},\mathsf{Event},\mathsf{Step}) K_{f}:T_{f}^{op}\to\mathbf{Type} trace-indexed knowledge presheaf \mathsf{restrict}(\epsilon,-) restriction along extension morphism \epsilon \Gamma\vdash t:A typing judgment \sigma_{0}\leadsto\sigma_{n} reflexive-transitive reachability 3.2 Layered syntax ( \mathsf{Uc} / Type / Prop) • Computational layer \mathsf{Uc} . Carries executable objects (states, events, traces, naturals, etc.) and standard MLTT constructors. • Knowledge layer \mathsf{Type}_{\ell} . Families indexed by traces, interpreted as presheaves. • Proposition layer \mathsf{Prop} . Proposition objects with fixed-point constructions, interpreted categorically. Core base types include: \mathsf{State}:\mathsf{Uc}_{0},\quad\mathsf{Event}:\mathsf{Uc}_{0},\quad\mathsf{Nat}:\mathsf{Uc}_{0},\quad\mathsf{FinTrace}:\mathsf{Uc}_{0},\quad\mathsf{InfTrace}:\mathsf{Uc}_{0}. 3.3 Trace language Finite traces are inductive: \mathsf{nil}:\mathsf{State}\to\mathsf{FinTrace},\qquad\mathsf{step}:\mathsf{FinTrace}\to\mathsf{Event}\to\mathsf{State}\to\mathsf{FinTrace}. Infinite traces are coinductive: \mathsf{InfTrace}:\mathsf{Uc}_{0},\qquad\mathsf{head}:\mathsf{InfTrace}\to\mathsf{State},\qquad\mathsf{tail}:\mathsf{InfTrace}\to(\mathsf{Event}\times\mathsf{InfTrace}). Guarded corecursion is required for productivity. 3.4 Structural and definitional judgments In addition to typing judgments, we rely on the standard structural layer: \vdash\Gamma\ \mathsf{ctx},\qquad\Gamma\vdash t\equiv u:A,\qquad\Gamma\vdash A\equiv B:U. These judgments support transport of terms and types across definitional equalities. In particular, trace-indexed families are used extensionally through conversion: \frac{\Gamma\vdash t:A\qquad\Gamma\vdash A\equiv B:U}{\Gamma\vdash t:B}. This rule is essential when different syntactic presentations of a trace denote the same normal form. 4 Typing / Operational Rules 4.1 Core typing and operational rules Context formation and dependent products follow standard dependent type theory: \frac{}{\,\vdash\cdot\ \mathsf{ctx}\,}\qquad\frac{\vdash\Gamma\ \mathsf{ctx}\quad\Gamma\vdash A:U}{\,\vdash\Gamma,x:A\ \mathsf{ctx}\,}, \frac{\Gamma\vdash A:U\quad\Gamma,x:A\vdash B:U}{\Gamma\vdash\Pi(x:A).B:U}, \frac{\Gamma,x:A\vdash t:B}{\Gamma\vdash\lambda x.t:\Pi(x:A).B}\qquad\frac{\Gamma\vdash f:\Pi(x:A).B\quad\Gamma\vdash a:A}{\Gamma\vdash f\,a:B[a/x]}. For the remainder of this section, fix a transition system with state type \mathsf{State} , event type \mathsf{Event} , and transition predicate \mathsf{Step}:\mathsf{State}\to\mathsf{Event}\to\mathsf{State}\to\mathsf{Uc}_{0}. Write \sigma\to\sigma^{\prime} for one-step transition and \sigma_{0}\leadsto\sigma_{n} for reflexive-transitive closure. 4.2 Trace-specific formation and elimination rules For clarity, we isolate the trace-specific typing shape used in proofs: \frac{\Gamma\vdash\sigma:\mathsf{State}}{\Gamma\vdash\mathsf{nil}(\sigma):\mathsf{FinTrace}(\sigma,\sigma)} \frac{\Gamma\vdash\tau:\mathsf{FinTrace}(\sigma_{0},\sigma_{1})\quad\Gamma\vdash e:\mathsf{Event}\quad\Gamma\vdash\pi:\mathsf{Step}(\sigma_{1},e,\sigma_{2})}{\Gamma\vdash\mathsf{step}(\tau,e,\pi):\mathsf{FinTrace}(\sigma_{0},\sigma_{2})}. Intuitively, \mathsf{step} composes a previously validated prefix with one operational transition witness \pi . For finite traces, elimination proceeds by structural recursion on \tau : \mathsf{trace\mbox{-}elim}:\Pi(P)\to P(\mathsf{nil})\to\left(\Pi(\tau,e,\pi).\,P(\tau)\to P(\mathsf{step}(\tau,e,\pi))\right)\to\Pi(\tau).\,P(\tau), where P ranges over trace-indexed families in an appropriate universe. Theorem 4.1 (Trace–Proof Correspondence) . For arbitrary states \sigma_{0},\sigma_{n}\in\mathsf{State} , a term t:\mathsf{FinTrace}(\sigma_{0},\sigma_{n}) is a constructive typed reachability witness for \sigma_{0}\leadsto\sigma_{n} . Proof sketch. By induction on the structure of finite traces. The base constructor \mathsf{nil} witnesses reflexive reachability. The extension constructor \mathsf{step} composes a previously witnessed prefix with one legal transition step. Hence every inhabitant of \mathsf{FinTrace}(\sigma_{0},\sigma_{n}) encodes a finite typed witness of \sigma_{0}\leadsto\sigma_{n} . ∎ Theorem 4.2 (Trace Completeness) . For arbitrary states \sigma_{0},\sigma_{n}\in\mathsf{State} , if \sigma_{0}\leadsto\sigma_{n} , then there exists t:\mathsf{FinTrace}(\sigma_{0},\sigma_{n}). Proof sketch. Induct on the length of a typed reachability witness. Length 0 yields the empty trace. For length k+1 , decompose the run as \sigma_{0}\leadsto\sigma_{k} followed by \sigma_{k}\to\sigma_{n} ; apply the induction hypothesis to obtain a prefix trace and then extend it using \mathsf{step} . ∎ 5 Non-monotonicity via Presheaf Semantics 5.1 Trace category Definition 5.1 (Finite-trace category) . Fix a transition system (\mathsf{State},\mathsf{Event},\mathsf{Step}) . Let T_{f} be the category whose objects are finite traces generated by this system and whose morphisms are trace extensions \epsilon:\tau\to\tau^{\prime} . 5.2 Knowledge presheaf Definition 5.2 (Trace-indexed knowledge) . A constructive knowledge system is a functor K_{f}:T_{f}^{op}\to\mathbf{Type}, assigning each trace \tau a type K_{f}(\tau) and each extension \epsilon:\tau\to\tau^{\prime} a restriction map \mathsf{restrict}(\epsilon,-):K_{f}(\tau^{\prime})\to K_{f}(\tau). 5.3 Restriction maps Lemma 5.3 (Restriction Functoriality) . Restriction maps satisfy: \mathsf{restrict}(id_{\tau},k)=k,\qquad\mathsf{restrict}(\epsilon_{1}\circ\epsilon_{2},k)=\mathsf{restrict}(\epsilon_{1},\mathsf{restrict}(\epsilon_{2},k)). Proof sketch. These are exactly the identity and composition laws of the functor K_{f}:T_{f}^{op}\to\mathbf{Type} , transported to element-level notation for restriction maps. ∎ 5.4 Characterization theorem Theorem 5.4 (Non-monotonicity Characterization) . Let K_{f}:T_{f}^{op}\to\mathbf{Type} be a knowledge presheaf. Then the following are equivalent: • K_{f} is non-monotone under trace extension. • There exists \epsilon:\tau\to\tau^{\prime}