Typed Knowledge over Constructive Institutions

Hans-Martin WillarXiv 2026 · DOI · arXiv

TL;DR

Eigenius is a new theoretical framework for a persistent knowledge store that treats proofs as first-class, permanent data rather than temporary scaffolding. By moving proof irrelevance from a built-in rule to a provable axiom, Eigenius allows a system to not only verify claims but also audit their provenance, track assumptions, and integrate results from diverse external reasoning tools.

What Problem Does This Paper Address?

In traditional type theories used for mathematics or software verification (like those powering Lean or Coq), the primary goal is to establish that a proposition is true. Once a proof is verified, the specific steps taken to get there are often "erased" at the kernel level—a concept known as definitional proof irrelevance. In these systems, any two proofs of the same statement are considered identical.

However, if you are building a persistent store for scientific or engineering knowledge, "truth" isn't enough. You need the "receipts." You need to know who established a claim, which version of a tool was used, and what specific empirical observations or assumptions the conclusion rests upon. If a specific measurement is later found to be faulty, a robust knowledge store must be able to trace exactly which dependent claims are now invalidated. Existing systems like standard databases or simple knowledge graphs lack the logical rigor to do this, while current proof assistants discard the very provenance data needed for such an audit.

Methods

The paper defines the Eigenius kernel, a dependent type theory that serves as the logical foundation for this knowledge store. Key technical choices include:

  • Axiomatic Proof Irrelevance: Unlike Lean, where proofs are identical by definition, Eigenius makes them identical only through a propositional axiom. This keeps proof terms distinct and inspectable within the system.
  • Untyped Joinability: Definitional equality is handled by a simple, type-free rewriting system. This makes the core conversion test efficient and confluent.
  • Justification Logic: The authors adapt Artemov’s Justification Logic to record the "grounds" of a claim (e.g., "observed via instrument X" or "declared by agent Y") separately from the deductive proof itself.
  • Institution Theory: To handle "multi-logic" environments, the system uses the category-theoretic framework of institutions. This allows claims to be transported between different systems (like moving a theorem from Lean into the Eigenius store) while preserving their meaning and evidence.
  • Type Theory with Records (TTR): The authors embed a theory of records and width subtyping to represent knowledge graphs, allowing for flexible, "open-world" data structures where resources can have extra properties not strictly required by their classes.

Datasets

As this is a foundational theory paper (Volume I of a series), it does not use traditional training or evaluation datasets. However, it does provide a formal mapping for Atomic Data, a modular specification for graph data, demonstrating how real-world knowledge graph formats can be represented within the Eigenius logic.

Key Insights and Ideas

  • The "Receipts" Matter: The central "aha" moment is that for a shared, persistent knowledge base, the identity of a proof is as important as its validity. By keeping proofs as distinct terms, the system can perform complex audits and counterfactual reasoning.
  • Separating Conversion from Subsumption: By keeping definitional equality (is A the same as B?) separate from subsumption (is A a subtype of B?), the authors maintain a simpler, more decidable kernel while still supporting complex class hierarchies.
  • Phantom Summands and Counterfactuals: In the Justification Logic section, the authors show that their "proposition-relative support" correctly handles counterfactual queries. For example, it can correctly answer whether a claim still stands if a specific summands (a "phantom" reason that didn't actually contribute to the proof) is removed.
  • Logic Agnosticism via Comorphisms: Using institution theory allows Eigenius to act as a "host" for many different types of reasoning (statistical, deductive, etc.) without having to re-implement every logic inside its own kernel.

Key Results

  • Consistency Proof: The authors prove the consistency of the kernel theory using a stratified set-theoretic model in ZFC with inaccessible cardinals. This ensures that the system cannot derive a contradiction (like False).
  • Decidability: The paper establishes that the procedures for type inference, checking, and conversion are decidable, provided that the terms eventually terminate (strong normalization).
  • Lean 4 Formalization: Perhaps the most significant practical result is that the entire theory—including the kernel, the justification logic, and the institution-theoretic framework—has been fully formalized and verified in the Lean 4 proof assistant.

Limitations and Future Work

  • Normalization Hypothesis: While the authors expect the system to be strongly normalizing (meaning all programs eventually finish), a full proof of this for the combined system remains an open challenge and is stated as a hypothesis.
  • Implementation Details: This volume is strictly theoretical. The actual system implementation, the language pipeline, and the runtime performance are deferred to Volumes II, III, and IV.
  • Coercive Subtyping: The current kernel only supports "identity-coercion" subsumption (where the term doesn't change when its type changes). More complex coercions that transform data are left for the "elaboration" layer, which is not covered in this volume.

Summary updated

Abstract

Type theories designed for mathematics or program verification need only that a proposition holds; proof irrelevance in conversion erases, at the kernel level, how a claim was established. A persistent knowledge store, by contrast, must retain that record: who established a claim, by which derivation or external tool, and under which assumptions. This volume presents the theory of Eigenius---a store of typed knowledge over constructive institutions---and develops its metatheory from that requirement. The kernel theory is a dependent type theory with cumulative universes, an impredicative universe of propositions, inductive families, and an intensional identity type. Proof irrelevance is an axiom with an explicit witness rather than a conversion rule, so proofs of a proposition are provably equal yet remain distinct terms. Definitional equality is joinability under an orthogonal rewriting system---confluent, injective on type formers, and decidable by a type-free test---while a separate subsumption judgment covers universe cumulativity, codomain-covariant function types, and declared class inclusions. We prove consistency via a set-theoretic model; develop a justification logic over the kernel's propositions to track evidence and support; organize environments as an institution so that store extensions are signature morphisms and external verdicts enter via comorphisms; formulate a typed knowledge-graph theory with records, classes, and refinements; and prove the correctness of conversion, normalization by evaluation, and bidirectional type checking relative to termination. A Lean 4 formalization accompanies the volume.
BibTeX
@misc{will2026typed,
  author = {Hans-Martin Will},
  title = {{Typed Knowledge over Constructive Institutions}},
  year = {2026},
  eprint = {2611.07432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07432},
}
Figure