Are Dependent Types in Set Theory Feasible?
Yunsong Yang, Simon Guilloud, Viktor Kunčak · 2026
Read Are Dependent Types in Set Theory Feasible? by Yunsong Yang, Simon Guilloud, Viktor Kunčak (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-2603-12827.txt.
Introduction
Yunsong Yang and co-authors test whether dependent types can be embedded in set theory in a feasible, mechanized way. In the types-as-sets view, they map dependent function types and universe levels into first-order logic. The target theory is Tarski-Grothendieck set theory, carried out in the Lisa proof assistant. On that base, they build a proof-producing type-checking tactic with partial subtyping support. Examples show verified automated reasoning for dependent types from set axioms alone.
Catalog record
| CREATOR | Yunsong Yang, Simon Guilloud, Viktor Kunčak |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20650 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.12827
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Are Dependent Types in Set Theory Feasible? Yunsong Yang, Simon Guilloud, Viktor Kunčak Abstract Following the types-as-sets paradigm, we present a mechanized embedding of dependent function types with a hierarchy of universes into schematic first-order logic with equality, with axiom schemas of Tarski-Grothendieck set theory. We carry this embedding in the Lisa proof assistant. On top of this foundation, we implement a proof-producing bidirectional type-checking tactic to compute proofs for typing judgements, with partial support for subtyping. We present examples showing how our approach enables automated reasoning for dependent types that is fully verified from set-theoretic axioms and deduction rules for schematic first-order logic with equality. Because types are merely sets, the resulting formalism supports equality that applies to all types and values and permits the usual substitution rules. Laboratory for Automated Reasoning and Analysis, EPFL, Lausanne, Switzerland, and KTH Royal Institute of Technology, Stockholm, Sweden and https://people.epfl.ch/yunsong.yang [email protected]://orcid.org/0009-0002-7654-3995Laboratory for Automated Reasoning and Analysis, EPFL, Switzerland and https://people.epfl.ch/simon.guilloud [email protected]://orcid.org/0000-0001-8179-7549 Laboratory for Automated Reasoning and Analysis, EPFL, Switzerland and https://lara.epfl.ch/~kuncak/ [email protected]://orcid.org/0000-0001-7044-9522 ccs Theory of computation Semantics and reasoning keywords First Order Logic, Set Theory, Dependent Types † † runningauthor: Y. Yang, S. Guilloud and V. Kunčak † † copyright: Yunsong Yang, Simon Guilloud and Viktor Kunčak † † category: Short paper † † supplement: Source code and mechanized proofs are available on Zenodo at https://doi.org/10.5281/zenodo.18997443 1 Introduction Zermelo-Fraenkel set theory with the axiom of choice (ZFC, [ 8 ] ) has remained the standard foundation of mathematics for over a century. In contrast, the landscape of interactive theorem proving is dominated by systems based on dependent type theory (DTT), such as Rocq [ 1 ] and Lean 4 [ 9 ] . While the foundations of these systems offer useful practical properties, such as built-in computation, they are typically more complex to implement and validate than first-order logic with ZFC axioms. This is attested, for example, by the size of the logical kernel of these tools, the complexity of their core deduction rules, and the number of implementation bugs that have been discovered in practice over the years [ 3 ] . The successes of DTT-inspired features—including predictable type checking, built-in evaluation, and simplified structural recursion—motivate the development of similar features within set-theory-based proof assistants. Such developments also represents a step towards system interoperability via the transfer of proofs between proof assistants. Proof transfer can occur either at a low level via the mechanized translation of kernel-level statements and proofs, or at a higher level by using, for example, increasingly effective LLMs [ 11 ] to translate user-written high-level proof scripts. In either case, the receiving system should be able to simulate the key features of the host system faithfully and without complex encoding. We believe this work is timely especially in the light of popularity of Lean among mathematicians. This popularity is, in our experience, sometimes met with the questioning of the necessity of using type theory as underlying foundation. We thus aim to develop dependent type theory as a soft type system for a set-theory-based proof assistant. Whereas soft type systems, including one for Mizar’s set theory, were considered in the past [ 13 ] , here we aim for an implemented solution targeting dependent types. For the present paper, we build on the recent version of Lisa [ 7 ] , a proof framework with a small logical kernel based on first-order logic and set theory, which has already been used to mechanize higher-order logic and simulate proofs from HOL Light [ 6 ] . While the prior work supports only the simply typed lambda calculus with top-level polymorphism, in the present paper we embed dependent function types with universes , which form the core of the calculus of constructions (CoC, [ 4 ] ); a key part of the foundation of Rocq and Lean. The resulting interface offers the syntax and key properties of dependent type theory, while ensuring that type checking and evaluation are formally justified using set-theoretic axioms. (We do not discuss inductive types or recursive function definitions in this paper; [ 6 ] presents an implementation usable in the simpler HOL settings.) While our encoding is similar in spirit to previous work constructing set-theoretic models of CiC, our objective is practical and focused on shallow, syntactic translation: for example, typing judgements are represented as first-order sequents, and not as sets (as in e.g. [ 12 ] ). An advantage of developing type-theoretic constructs on top of an existing set theoretic foundation is that it allows us to further extend type-theoretic features while guaranteeing soundness. As an example, our implementation enriches our dependent function-type interface with a proof-of-concept form of subtyping, supporting subtyping assumptions as well as function types covariant in the codomain. Contributions . In this paper, we present a set-theoretic realization of dependent types within Lisa. We provide an interface in Lisa that offers syntax and automated reasoning for dependent types with universes, and we implement proof tactics corresponding to evaluation and type checking, based on bidirectional type checking. Additionally, our proof-producing type checker supports a form of subtyping, serving as a proof-of-concept toward the design of a richer set-theoretic type system. Our interface is an extension of Lisa that is fully compatible with both past and future developments, with types represented as set membership sub-formulas. We demonstrate practical use cases of our extension in conjunction with Lisa’s library. This approach enables the automated derivation of set-theoretic proofs corresponding to dependently typed judgments. We view our work as a first step towards translating statements and proofs from Lean 4 and Rocq into set-theoretic proof assistants [ 2 , 10 , 7 ] . 2 Embedding of Dependent Product In first-order logic, variable binding occurs only through the quantifiers \forall and \exists , but embedding type theory requires representing abstractions \lambda x.e , i.e. terms binding variables. Though it is still possible to embed such \lambda -terms, it requires complex and inefficient encoding [ 6 ] . In this paper we make use of recently developed \lambda FOL within Lisa, an extension of first-order logic with \lambda -terms and Hilbert’s epsilon operator \varepsilon . In \lambda FOL, expressions are given by simply typed \lambda -terms over two primitive sorts: Prop (propositions) and Ind (individuals). Over these atomic sorts, predicates and functions are typed using an arrow constructor, as is customary in systems based on higher-order logic. 1 1 1 In Lisa, arrow types are written as >>: , which is right-associative. For instance, membership \in is a binary predicate with type \texttt{Ind}\to\texttt{Ind}\to\texttt{Prop} and the quantifier \forall is a constant of type (\texttt{Ind}\to\texttt{Prop})\to\texttt{Prop} . \varepsilon is a quantifier of type (\texttt{Ind}\to\texttt{Prop})\to\texttt{Ind} so that \varepsilon x.P(x) represents some value satisfying P , if one exists. Crucially, the only rules given by Lisa to reason with these \lambda -terms are \beta -reduction and instantiation of schematic symbols (on top of the rules of classical sequent calculus). Hence it is in principle always possible to unfold higher-order terms and definition into pure first-order terms, justifying that the system is still, in spirit, first-order. 2 2 2 For example, it is impossible to define equality or universal quantification on higher-order types. Using \lambda FOL and set-theoretic axioms, we embed