💻 computer science

Are Dependent Types in Set Theory Feasible?

本文利用 Lisa 证明助手，在塔斯基 - 格罗滕迪克集合论公理体系下，通过“类型即集合”范式将依赖函数类型及宇宙层级嵌入一阶逻辑，并实现了支持子类型的双向类型检查战术，从而为依赖类型提供了完全基于集合论公理验证的自动化推理能力。

原作者： Yunsong Yang, Simon Guilloud, Viktor Kunčak

发布于 2026-03-16

📖 1 分钟阅读☕ 轻松阅读

原作者： Yunsong Yang, Simon Guilloud, Viktor Kunčak

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个非常有趣且大胆的想法：能不能把“依赖类型”（一种现代编程语言和数学证明中非常高级的工具）塞进传统的“集合论”（数学最基础的基石）里，并且让计算机自动帮你检查证明？

为了让你轻松理解，我们可以用几个生动的比喻来拆解这篇论文的核心内容。

1. 背景：两派数学家的“语言之争”

想象一下，数学界有两个主要的“部落”：

集合论部落（ZFC）： 这是老派但极其稳固的部落。他们相信万物皆“集合”。就像盖房子，地基是泥土（集合），上面可以盖出任何形状的房子。这个部落的规矩（公理）很简单，大家都懂，但有时候表达复杂的逻辑（比如“如果 A 是 B 的子集，那么 C 必须是 D"）会显得有点啰嗦。
类型论部落（Dependent Types）： 这是新派且极其精密的部落（比如 Lean 4, Rocq 使用的系统）。他们发明了“依赖类型”，就像是一个智能的乐高说明书。在这个系统里，积木的形状（类型）会根据你手里拿的积木（数值）自动变化。比如，如果你拿的是“红色积木”，说明书会自动告诉你只能拼“红色底座”。这让写代码和做证明非常安全，不容易出错。

问题在于： 类型论部落的“智能说明书”太复杂了，计算机很难验证它是不是真的没写错。而集合论部落的“泥土”虽然简单，但缺乏那种“智能变化”的灵活性。

这篇论文的目标： 作者们想做一个“翻译官”。他们想证明：我们可以用集合论的“泥土”，搭建出类型论的“智能乐高”，并且让计算机自动验证这个过程是完美的。

2. 核心魔法：把“函数”变成“集合”

在类型论里，最核心的概念是“依赖函数”（Dependent Function），它的类型会根据输入值的变化而变化。

比喻： 想象一个万能快递柜。
- 在普通系统里，快递柜的格子大小是固定的。
- 在依赖类型系统里，快递柜的格子大小是动态的：如果你寄的是“小盒子”，柜子就生成一个小格子；如果你寄的是“大箱子”，柜子就生成一个大格子。

作者们做了一件很酷的事：他们把这个“动态变化的柜子”在集合论里翻译成了“集合的集合”。

他们定义了一个规则：一个依赖函数，本质上就是一个特殊的集合（里面装着所有的“输入 - 输出”配对）。
他们利用集合论里的公理（比如塔斯基 - 格罗滕迪克公理，这就像是一个无限大的仓库管理员），保证了无论你的“盒子”怎么变，这个“柜子”永远都能装得下，不会溢出。

3. 宇宙层级：给积木分级

类型论里有一个概念叫“宇宙”（Universes），为了防止逻辑悖论（比如“所有集合的集合”这种会导致崩溃的怪圈），他们把类型分成了不同的层级：

Level 1 的积木只能放在 Level 2 的架子上。
Level 2 的积木只能放在 Level 3 的架子上。
以此类推，无限向上。

在集合论里，这很难办，因为集合论里没有天然的“无限层级”。
作者的解决方案： 他们引入了“塔斯基公理”。

比喻： 想象有一排无限大的俄罗斯套娃。
- 每个套娃（宇宙）里面都装满了更小的套娃（集合）。
- 只要你需要一个更大的空间，公理就保证存在一个更大的套娃把你装进去。
- 这样，他们就能在集合论里完美模拟出类型论那种“层级无限向上”的感觉。

4. 自动证明：聪明的“检查员”

有了理论基础，作者们还写了一个自动检查员（叫 Typecheck.prove）。

以前的做法： 如果你想证明一个复杂的依赖类型程序是对的，你需要手动写一大堆步骤，告诉计算机“因为 A 是 B，所以 C 是 D"，非常累人。
现在的方法： 你只需要把代码（或证明）扔给这个检查员。
- 检查员会像双向翻译官一样工作：它既看“输入”（你给了什么），也看“输出”（你想要什么）。
- 如果匹配，它会自动在后台生成一份基于集合论公理的详细证明报告。
- 这份报告是“可验证”的，意味着任何懂集合论的人（或机器）都能一眼看出它是对的，因为它完全符合最基础的数学规则。

5. 为什么要这么做？（意义）

这篇论文不仅仅是为了炫技，它有非常实际的用途：

互操作性（翻译桥梁）： 现在有很多数学家在用 Lean 4（类型论）写证明。如果未来大家想用集合论工具（比如 Mizar 或 Lisa）来验证这些证明，这篇论文就是翻译字典。它证明了 Lean 里的证明可以无损地“搬运”到集合论的世界里。
更简单、更可信： 类型论系统的核心（Kernel）通常很复杂，容易有 Bug。而集合论的核心非常简单。如果能把复杂的类型论证明“降维”成简单的集合论证明，那么这些证明的可信度就更高了，因为地基更稳。
统一标准： 它让“智能乐高”和“泥土”不再是对立的，而是可以互相理解的。

总结

简单来说，这篇论文就像是在用最基础的砖块（集合论），搭建出了一座拥有智能变形功能的摩天大楼（依赖类型）。

作者们不仅证明了这是可行的，还造出了一套自动施工队（证明生成器），能自动把设计图变成符合建筑规范（集合论公理）的合格大楼。这意味着，未来我们可能不再需要在“复杂的类型论”和“简单的集合论”之间做选择，而是可以在两者之间自由穿梭，享受两者的优点。

这篇论文题为《集合论中的依赖类型是否可行？》（Are Dependent Types in Set Theory Feasible?），由 EPFL 和 KTH 的研究人员 Yunsong Yang、Simon Guilloud 和 Viktor Kunčak 撰写。文章提出了一种将依赖类型理论（Dependent Type Theory, DTT）嵌入到基于集合论的一阶逻辑中的方法，并在 Lisa 证明助手上进行了机械化实现。

以下是该论文的详细技术总结：

1. 研究背景与问题 (Problem)

现状对比：数学的标准基础是带有选择公理的 Zermelo-Fraenkel 集合论（ZFC）。然而，交互式定理证明领域（如 Rocq/Coq 和 Lean 4）主要基于依赖类型理论（DTT）。
痛点：虽然 DTT 提供了计算性、结构递归等实用特性，但其逻辑内核通常比一阶逻辑（FOL）更复杂，实现和验证难度更大，且历史上存在较多实现漏洞。
核心问题：能否在基于集合论的证明助手（如 Lisa）中，构建一个功能完备的依赖类型系统？即，能否将 DTT 的核心特性（如依赖函数类型、宇宙层级）作为“软类型系统”嵌入到集合论中，同时保持逻辑内核的简单性和可验证性？
目标：开发一种机制，使得基于集合论的系统能够模拟 DTT 的关键特性（如类型检查、求值），从而促进不同证明助手之间的证明转移（Proof Transfer），特别是针对 Lean 4 和 Rocq 的迁移。

2. 方法论 (Methodology)

作者基于 Lisa 证明框架（其内核基于带有等式的一阶逻辑和集合论公理），通过以下步骤实现了依赖类型的嵌入：

A. 基础逻辑扩展： $\lambda$ FOL

利用 Lisa 中扩展的一阶逻辑（ $\lambda$ FOL），该逻辑引入了 $\lambda$ -项和希尔伯特 $\epsilon$ 算子。
表示：将类型论中的抽象（ $\lambda x. e$ ）和项绑定映射为 $\lambda$ FOL 中的 $\lambda$ -项。
优势：虽然引入了高阶项，但通过 $\beta$ -归约和公理化定义，最终仍可展开为纯一阶项，保持了系统的“一阶”精神。

B. 依赖乘积类型的嵌入 (Embedding of Dependent Product)

作者定义了从类型论项到 $\lambda$ FOL 项的嵌入映射 $t \mapsto s$ ：

抽象 (Abs)： $\lambda x : T. u$ 映射为集合 $\{ \langle x, L(x) \rangle \mid x \in T \}$ ，即函数图像。
应用 (App)： $t \ u$ 映射为 $\epsilon y. (u, y) \in t$ ，利用 $\epsilon$ 算子提取满足关系的值。
依赖乘积 (Pi)： $\Pi x : T_1. T_2$ 映射为满足特定函数性条件（functional relation）且值域在 $T_2$ 内的函数集合。
定理验证：证明了嵌入后的定义满足 $\beta$ -归约（Theorem 2）、抽象规则（Tabs, Theorem 3）和应用规则（Tapp, Theorem 4）。

C. 宇宙层级管理 (Universe Management)

挑战：标准 ZFC 公理无法直接提供封闭的宇宙层级（即没有集合能包含所有集合论构造，特别是 $\Pi$ 算子）。
解决方案：引入 Tarski-Grothendieck 公理（Tarski's Axiom），该公理断言对于任意集合 $x$ ，存在一个包含 $x$ 的 Grothendieck 宇宙 $U$ 。
定义：
- 定义了 isUniverse 谓词，要求集合对配对、并集、幂集和函数像（Replacement）封闭。
- 利用 $\epsilon$ 算子定义 universeOf(x) 为包含 $x$ 的某个宇宙。
- 通过迭代应用构建宇宙层级（ $Type_n$ ）。
关键引理：证明了宇宙在依赖乘积下的封闭性（Lemma 9），并推导了类型形成规则（Tform）和宇宙排序规则（Tsort）。

D. 证明生成的双向类型检查 (Proof-Producing Bidirectional Type Checking)

实现了一个名为 Typecheck.prove 的自动化策略（Tactic）。
机制：遵循双向类型检查（Bidirectional Type Checking）范式，包含三种递归模式：
1. Check 模式：给定项和预期类型，验证项是否符合类型（处理抽象和子类型转换）。
2. Infer 模式：给定项，推导其类型（处理应用、抽象和宇宙层级计算）。
3. Subset 模式：处理子类型关系（Subtyping）。
子类型支持：实现了部分子类型支持，特别是协变（Covariance）的函数类型。由于集合论解释的限制，作者证明了受限的 $\Pi$ -子类型规则（不变的定义域，协变的值域），避免了不可满足的“过大集合”问题。

3. 关键贡献 (Key Contributions)

集合论实现的依赖类型：在 Lisa 中首次实现了带有宇宙层级的依赖函数类型的机械化嵌入。
可验证的类型检查：开发了一个证明生成的类型检查器，它不直接返回布尔值，而是合成一个可被 Lisa 内核验证的集合论证明对象。
子类型支持：在集合论语义下实现了协变函数类型的子类型支持，作为更丰富类型系统设计的概念验证。
统一性与兼容性：该接口完全兼容 Lisa 的现有库，类型被表示为集合成员关系的子公式，允许在集合论公理基础上进行自动化推理。
证明转移的可行性：展示了如何将类似 Lean 4 的高层证明脚本（如多态函数组合）转化为集合论证明，为未来不同证明系统间的证明转移奠定了基础。

4. 结果与示例 (Results & Examples)

形式化验证：所有类型检查规则和宇宙层级规则均基于 Tarski-Grothendieck 集合论公理和 $\lambda$ FOL 规则进行了形式化证明。
多态组合示例：论文展示了一个具体案例，模拟了 Lean 中的多态函数组合（Function.comp）和恒等函数（id）。
- 系统成功自动推导了复合函数 comp(A, B, B, Id(B), f) 的类型为 $A \to B$ 。
- 该过程完全自动化，仅需基础假设 isUniverse(Typ)，无需用户手动干预宇宙层级或子类型证明。
代码可用性：源代码和机械化证明已公开在 Zenodo 上。

5. 意义与影响 (Significance)

理论意义：证明了依赖类型理论可以完全建立在集合论基础之上，且不需要复杂的逻辑内核。这挑战了“依赖类型必须基于类型论”的传统观念，表明集合论足以支撑现代类型系统的核心特性。
工程意义：
- 降低验证成本：基于集合论的证明助手通常具有更小的逻辑内核和更简单的验证难度，这有助于提高证明系统的可靠性。
- 互操作性：为将 Lean 4 和 Rocq 中的证明迁移到基于集合论的系统（如 Mizar 或未来的 Lisa 版本）提供了技术路径。
- 扩展性：这种“软类型系统”的方法允许在保持底层集合论安全性的同时，灵活地添加新的类型论特性（如子类型、归纳类型等）。
未来展望：这是将 DTT 特性引入集合论证明助手的第一步，未来计划扩展支持归纳类型、递归函数定义，并进一步探索更通用的子类型规则。

总结：该论文通过巧妙的集合论嵌入和 $\lambda$ FOL 扩展，成功地在 Lisa 中实现了依赖类型系统。这不仅验证了“集合论基础上的依赖类型”的可行性，也为构建更轻量级、更可靠的定理证明器以及实现跨系统的证明转移开辟了新途径。