为什么Agda拒绝Set₁→Set₁？

问题背景

Agda 是一种基于依赖类型的编程语言，广泛用于形式化验证和证明。它对类型系统有着严格的要求，特别是在处理高阶类型时。

基础概念

在 Agda 中，Set 是一个基本的类型构造器，表示集合。Set₁ 表示由 Set 类型构成的集合，即 Set 的幂集。Set₁→Set₁ 表示从 Set₁ 到 Type₁ 的函数类型。

为什么 Agda 拒绝 Set₁→Set₁？

Agda 拒绝 Set₁→Set₁ 的主要原因是其类型系统的限制，特别是关于高阶类型的限制。具体来说，Agda 的类型系统不允许某些高阶类型的存在，以避免类型理论中的悖论和不一致性。

类型理论中的悖论

在类型理论中，类似于罗素悖论的悖论可能会导致系统不一致。例如，考虑一个集合，它包含所有不包含自身的集合。这个集合是否包含自身？如果包含，那么根据定义它不应该包含自身；如果不包含，那么根据定义它应该包含自身。

Agda 的解决方案

为了避免这种悖论，Agda 采用了一种称为“分层类型”的方法。每个 Set 层次只能包含比它低层次的类型。例如，Set₀ 可以包含基本类型（如 Nat 和 Bool），Set₁ 可以包含 Set₀ 类型的集合，但不能包含 Set₁ 类型的集合。

解决方案

如果你需要在 Agda 中处理类似 Set₁→Set₁ 的类型，可以考虑以下几种方法：

1. 使用 Universe Polymorphism： Agda 支持 Universe Polymorphism，允许你在不同层次之间进行类型操作。你可以使用 Type 而不是 Set 来表示更高层次的类型。
2. 使用 Universe Polymorphism： Agda 支持 Universe Polymorphism，允许你在不同层次之间进行类型操作。你可以使用 Type 而不是 Set 来表示更高层次的类型。
3. 使用 Inductive Types： 通过定义递归类型，可以在一定程度上绕过类型系统的限制。例如，你可以定义一个递归类型来表示高阶函数。
4. 使用 Inductive Types： 通过定义递归类型，可以在一定程度上绕过类型系统的限制。例如，你可以定义一个递归类型来表示高阶函数。
5. 使用 Coinductive Types： 类似地，你可以使用共递归类型来处理高阶类型。
6. 使用 Coinductive Types： 类似地，你可以使用共递归类型来处理高阶类型。

参考链接

• Agda Documentation
• Type Theory and Formal Proof: An Introduction

通过这些方法，你可以在 Agda 中处理高阶类型，同时避免类型系统中的悖论和不一致性。