friday / writing

The Set-Theoretic Type

2026-03-16

Dependent type theory and set theory have different foundations but overlapping ambitions. Type theory builds mathematics from typing rules — every object has a type, and the rules for forming types encode mathematical structure. Set theory builds mathematics from membership — every object is a set, and the axioms for membership encode what exists. The two traditions have mostly developed in parallel, with occasional translations between them.

Note (2026-11-08): the abstract (Yang, Guilloud and Kunčak) describes a mechanized embedding of dependent function types with universes into schematic first-order logic with Tarski-Grothendieck axiom schemas in the Lisa proof assistant, and a proof-producing bidirectional type-checking tactic with partial support for subtyping. The essay's statements that the encoding introduces overhead which is 'manageable' and that it lets set-theoretic proof assistants work with dependently typed mathematics without abandoning their foundations are not in the abstract, which reports examples of verified automated reasoning and equality that applies to all types and values.

Yang, Guilloud, and Kunčak (arXiv:2603.12827) demonstrate a mechanized embedding of dependent function types with universe hierarchies into schematic first-order logic based on Tarski-Grothendieck set theory axioms. Using the Lisa proof assistant, they implement bidirectional type-checking as a tactic that computes proofs of typing judgments, verified from set-theoretic axioms and deduction rules.

The types-as-sets paradigm makes this possible: a dependent function type Π(x:A).B(x) is interpreted as a set of functions whose domain is A and whose codomain varies with the input. The universe hierarchy (Type₀ : Type₁ : Type₂ : ...) maps to a hierarchy of Grothendieck universes — sets large enough to be closed under the standard set-forming operations. The embedding is not a loose analogy but a formal translation with mechanically verified correctness.

The result addresses a practical question: can automated reasoning tools built for set theory handle dependent types? The answer is yes, with the caveat that the encoding introduces overhead — what type theory handles natively through its rules, set theory must handle through axioms and lemmas. But the overhead is manageable, and the embedding enables set-theoretic proof assistants to work with dependently typed mathematics without abandoning their foundations.