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