💻 computer science

Are Dependent Types in Set Theory Feasible?

This paper presents a mechanized embedding of dependent types and universes into Tarski-Grothendieck set theory within the Lisa proof assistant, enabling a verified, proof-producing type-checking tactic that leverages standard set-theoretic equality and substitution rules for automated reasoning.

Original authors: Yunsong Yang, Simon Guilloud, Viktor Kunčak

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunsong Yang, Simon Guilloud, Viktor Kunčak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a massive, intricate library. For over a century, the standard blueprint for this library has been Set Theory (specifically ZFC). In this blueprint, everything is just a "box" (a set) containing other boxes. It's a solid, time-tested foundation, but it can be a bit clunky when you want to build complex, self-referential structures.

In recent decades, a new, more modern blueprint called Dependent Type Theory (used by tools like Lean and Rocq) has become the favorite of many mathematicians and programmers. It's like a library where every book has a label that changes depending on what's inside it, allowing for incredibly precise organization. However, this new blueprint is complex to build and verify. If you make a tiny mistake in the foundation, the whole library could be unsafe.

The Big Question: Can we build the fancy, self-organizing features of the "Type Theory" library inside the sturdy, old-school "Set Theory" foundation?

This paper says Yes, and here is how they did it, using some simple analogies:

1. The Translator (The Embedding)

The authors built a translator that speaks both languages.

The Problem: Set theory doesn't naturally understand "functions that depend on their inputs" (dependent types). It only understands standard sets.
The Solution: They created a dictionary that translates "Type Theory" concepts into "Set Theory" concepts.
- Analogy: Imagine you have a recipe for a cake that says, "Add flour if the batter is yellow." Set theory doesn't know what "if" means in a recipe context. The authors translated this into a strict rule: "The set of all ingredients includes flour only if the batter is yellow."
- They used a special extension of logic (called $\lambda$ FOL) that allows them to write these "conditional recipes" as standard mathematical sets.

2. The Infinite Shelves (Universes)

In Type Theory, you have "Universes." Think of these as shelves. A shelf holds books (types), but the shelf itself must sit on a bigger shelf.

The Problem: In standard Set Theory, you can't have a "set of all sets" (it leads to paradoxes). You can't easily build an infinite ladder of shelves where each shelf is big enough to hold the one below it.
The Solution: They used a powerful mathematical rule called Tarski's Axiom.
- Analogy: Imagine you are trying to build a tower of boxes. Standard rules say, "You can't put a box inside a box that is too big." Tarski's Axiom is like a magic rule that says, "For every box you have, there exists a super-box big enough to hold it, and a super-super-box to hold that one, forever."
- This allows them to create an infinite hierarchy of "Universes" (shelves) inside Set Theory, just like Type Theory needs.

3. The Auto-Checker (Proof-Producing Tactic)

Usually, when you write code or a proof in these systems, you have to manually convince the computer that your logic is sound.

The Innovation: The authors built an automatic proof generator.
- Analogy: Imagine you are writing a story. Usually, you have to write footnotes explaining why every sentence makes sense. This new tool is like a smart editor that reads your story, checks the logic, and automatically writes the footnotes for you in a language the library's security guard (the Set Theory kernel) understands.
- If you say, "This function takes a number and returns a list," the tool automatically generates the mathematical proof that says, "Yes, this set of numbers is indeed inside the set of lists."

4. The "Subtyping" Trick

They also added a feature called Subtyping.

The Concept: In programming, a "Dog" is a type of "Animal." If a function needs an "Animal," you can give it a "Dog."
The Challenge: In pure Set Theory, this is tricky because sets don't always play nice with "is a kind of" relationships.
The Result: They proved a specific rule that allows this to work safely within their Set Theory translation, but with some guardrails to prevent the "set of all functions" from becoming too big to exist.

Why Does This Matter?

Think of Lean and Rocq as high-tech, futuristic libraries that are amazing to use but have complex, fragile foundations. Think of Set Theory as a library built on bedrock—boring but unshakeable.

This paper is like building a bridge.

It allows people to write their fancy, modern code in the "Type Theory" style.
The bridge automatically translates it into "Set Theory" language.
The Set Theory foundation verifies it is 100% correct.

The Bottom Line:
The authors have shown that you don't have to choose between "fancy, modern features" and "rock-solid, simple foundations." You can have both. They proved that the complex logic of modern type theory can be fully simulated, verified, and trusted using the classic, simple rules of Set Theory. This opens the door for different proof tools to talk to each other and for mathematicians to use their favorite tools without worrying about the underlying foundation being too complex to trust.

1. Problem Statement

The paper addresses the tension between the dominance of Dependent Type Theory (DTT) in interactive theorem proving (e.g., Lean 4, Rocq) and the foundational simplicity of Zermelo-Fraenkel set theory with Choice (ZFC).

The Challenge: While DTT offers practical features like built-in computation and predictable type checking, its logical kernels are complex, difficult to validate, and prone to implementation bugs. Conversely, ZFC is a mature, well-understood foundation but lacks native support for dependent types and the "types-as-sets" paradigm required for modern proof assistants.
The Goal: The authors aim to determine if it is feasible to implement a soft type system for dependent types on top of an existing set-theoretic foundation (specifically the Lisa proof assistant). The objective is to provide the syntax and automation of DTT while ensuring all reasoning is formally justified by set-theoretic axioms and first-order logic (FOL) deduction rules.

2. Methodology

The authors propose a mechanized embedding of dependent function types with a universe hierarchy into schematic first-order logic with equality, utilizing the Lisa proof assistant.

A. Logical Foundation: $\lambda$ FOL

To handle variable binding (essential for $\lambda$ -abstractions in type theory) within a first-order framework, the authors utilize $\lambda$ FOL, an extension of FOL available in Lisa.

Features: $\lambda$ FOL includes $\lambda$ -terms and Hilbert's $\epsilon$ -operator.
Simplicity: The system relies on $\beta$ -reduction and schematic symbol instantiation, allowing higher-order terms to be unfolded into pure first-order terms, maintaining the "first-order spirit" of the kernel.

B. Embedding Dependent Types

The authors define an embedding function mapping type-theoretic terms to $\lambda$ FOL terms:

Abstraction ( $\lambda x:T. u$ ): Mapped to a set of pairs representing a functional relation: abs(T)(λx.u) := {⟨x, L(x)⟩ | x ∈ T}.
Application ( $t u$ ): Mapped using the $\epsilon$ -operator to select a value from the function set: app(t)(u) := εy. (u, y) ∈ t.
Dependent Product ( $\Pi x:T_1. T_2$ ): Mapped to a set of functional relations satisfying the domain and codomain constraints:
$\Pi(T_1)(L) := \{ f \in \mathcal{P}(T_1 \times \bigcup_{x \in T_1} L(x)) \mid \text{isFunc}(f) \land \forall x \in T_1. \text{app}(f)(x) \in L(x) \}$
Key Theorems: They prove that these definitions recover standard DTT inference rules, including $\beta$ -reduction, Abstraction (Tabs), and Application (Tapp), purely from set-theoretic axioms.

C. Universe Management

Standard ZFC lacks an internal notion of universes (sets closed under all constructions). To model the cumulative hierarchy ( $Type_i : Type_{i+1}$ ) required for polymorphism:

Tarski-Grothendieck Axioms: The authors adopt Tarski's axiom, which asserts the existence of infinitely many Grothendieck universes.
Definition: A Grothendieck universe is a set closed under pairing, union, power sets, and replacement.
Implementation: They define a predicate isUniverse and a function universeOf(x) (using the $\epsilon$ -operator) to select a universe containing a given set. This allows the construction of a hierarchy of universes ($Typen$) necessary for dependent product formation.

D. Automated Proof Generation

To avoid manual proof construction for typing judgments, the authors implemented a bidirectional type-checking tactic (Typecheck.prove) within Lisa.

Modes: The tactic operates in Check (verifying a term against an expected type), Infer (computing the type of a term), and Subset (handling subtyping).
Subtyping: They implement a restricted form of subtyping. While full contravariance is problematic in set theory (due to size issues), they prove a rule for invariant domains and covariant codomains for dependent products ( $\Pi$ -subtyping).
Output: Instead of returning a boolean, the tactic synthesizes a formal proof object (a set-theoretic proof) that can be verified by the Lisa kernel.

3. Key Contributions

Set-Theoretic Embedding of DTT: A formal realization of dependent function types and universe hierarchies within a first-order set-theoretic framework, proving that DTT constructs can be reduced to set membership and equality.
Proof-Producing Type Checker: The implementation of a tactic that automatically generates kernel-verifiable proofs for typing judgments, bridging the gap between high-level type theory and low-level set theory.
Subtyping Support: A proof-of-concept implementation of subtyping (specifically covariant function types) within the set-theoretic model, demonstrating the flexibility of the approach.
Interoperability Pathway: A step toward translating proofs from DTT-based systems (like Lean 4 and Rocq) into set-theoretic proof assistants, facilitating proof transfer and system interoperability.

4. Results

Verification: The authors successfully mechanized the embedding in Lisa. They demonstrated that typing judgments (e.g., function composition with polymorphic identity) can be automatically verified.
Example Case: They verified a polymorphic composition example (Function.comp and id), showing that the tactic correctly derives set membership for the composed function based on the input assumptions and universe levels.
Correctness: The system ensures that all type-checking decisions are backed by Tarski-Grothendieck axioms and FOL deduction rules, eliminating the need for a complex, unverified type-theoretic kernel.

5. Significance

Foundational Robustness: By grounding dependent types in ZFC, the approach leverages a century of mathematical consensus and simplifies the logical kernel, potentially reducing the risk of implementation bugs compared to complex DTT kernels.
Bridging Communities: This work facilitates the transfer of proofs between the DTT-dominated ecosystem (Lean, Rocq) and set-theoretic systems (Mizar, Isabelle/ZF), potentially unifying formal mathematics.
Practical Automation: It demonstrates that the "soft type system" approach can provide the usability and automation of DTT without sacrificing the foundational simplicity of set theory.
Future Directions: The authors view this as a first step toward a full translation layer for Lean 4 and Rocq, suggesting that set-theoretic foundations can support advanced type-theoretic features like dependent types and subtyping without requiring a paradigm shift in the underlying logic.