TL;DR
This paper presents a novel approach to embedding dependent type theory (DTT) within the familiar framework of Zermelo-Fraenkel set theory (ZFC). By mechanizing DTT features like dependent function types and universes within a set-theoretic proof assistant, the authors enable richer reasoning capabilities while maintaining formal soundness and potentially bridging the gap between different proof systems.
What Problem Does This Paper Address?
Interactive theorem proving systems often rely on complex foundations like dependent type theory (DTT), which offer powerful features such as built-in computation and predictable type checking. However, these systems can be challenging to implement and validate due to their intricate logical kernels and deduction rules. This complexity can hinder interoperability between different proof assistants and even lead to implementation bugs. The authors aim to address this by demonstrating that the core features of DTT, specifically dependent function types and universes, can be faithfully realized within a simpler, more established foundation: first-order logic with ZFC axioms. This approach could make advanced reasoning features more accessible and verifiable, potentially simplifying proof transfer and reducing the burden of formal system development.
Methods
The core of this work is a mechanized embedding of dependent type theory into the Lisa proof assistant, which is based on first-order logic and set theory. The authors leverage an extension of first-order logic called AFOL (Abstract First-Order Logic) which includes A-terms and the epsilon operator, allowing for the representation of abstractions and quantified variables.
Key methodological contributions include:
- Types-as-Sets Paradigm: Dependent function types and universes are modeled as specific sets within ZFC. For instance, a dependent function type $\Pi x: T_1. T_2(x)$ is represented as a set of functions that map elements from $T_1$ to corresponding types in $T_2(x)$.
- Universe Hierarchy: To handle the recursive nature of types and polymorphism, the paper models a hierarchy of universes using Tarski's axiom. This axiom guarantees the existence of infinitely many universes, each closed under set-theoretic operations, which is crucial for interpreting dependent product types.
- Bidirectional Type-Checking Tactic: A proof-producing tactic,
Typecheck.prove, is implemented. This tactic synthesizes proofs for typing judgments, rather than just returning a boolean. It follows a bidirectional type-checking discipline, combining "check mode" (verifying a term against an expected type) and "infer mode" (determining the type of a term). - Subtyping Support: A proof-of-concept for subtyping is included, demonstrating how to handle covariant function types and cumulative universes. This adds flexibility to the type system.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Feasibility of DTT in Set Theory: The paper convincingly demonstrates that the core expressive power of dependent type theory, including dependent function types and universes, can be soundly and mechanistically embedded within ZFC. This challenges the notion that DTT is inherently tied to its own foundational systems.
- Bridging the Gap: By providing a set-theoretic interpretation of DTT, this work offers a potential pathway for interoperability between DTT-based proof assistants (like Lean and Coq) and set-theory-based ones. This could simplify proof transfer and verification across different tools.
- Simplified Foundations, Richer Reasoning: The approach allows for the benefits of DTT (like predictable type checking and automated reasoning) to be realized on top of a more established and arguably simpler foundation (ZFC). This can lead to more verifiable and maintainable proof systems.
- Universes as a Key Enabler: The careful modeling of universe hierarchies is crucial. It allows for polymorphism and the interpretation of dependent product types, which are central to DTT's expressiveness, within the set-theoretic framework.
Key Results
The paper presents a mechanized embedding of dependent function types with universes into Lisa. This embedding supports:
- Formal Justification: All type-checking and evaluation rules are formally justified by set-theoretic axioms and first-order logic deduction rules.
- Automated Proof Generation: A proof-producing type-checking tactic (
Typecheck.prove) is implemented, which automatically generates proofs for typing judgments that are verifiable by the Lisa kernel. - Subtyping Proof-of-Concept: The implementation includes a form of subtyping, demonstrating its feasibility within the set-theoretic model.
- Example of Polymorphic Composition: A concrete example of composing polymorphic functions is shown, illustrating how the system handles type instantiation and reasoning.
Limitations and Future Work
The authors acknowledge several limitations and suggest future directions:
- Inductive Types and Recursive Functions: The current implementation does not cover inductive types or recursive function definitions, which are crucial for many practical applications of DTT. Future work will focus on incorporating these.
- Subtyping Generalization: While a proof-of-concept for subtyping is presented, the authors are exploring ways to generalize subtyping conditions and the type-checking algorithm more broadly. Specifically, contravariance in function types is noted as a challenge.
- Full Interoperability: This work is presented as a "first step towards translating statements and proofs" from systems like Lean 4 and Rocq. Achieving full interoperability will require further development.
- Universe Management: While the paper uses Tarski's axiom for universes, the authors mention that for simulating countably many universes, they only need it at the meta-level. Further exploration of universe management and its implications for expressiveness is implied.
Summary updated