这在 agda 中是如何工作的？

Question

我想证明存在一个小于10的自然数，我这样写代码..

thm2 : (∃ λ m → (m < 10))
thm2 = zero , s≤s z≤n

我无法理解这是如何工作的。请解释..

Answer 1

我们来剖析一下thm2。

表达式的类型

∃ λ m → m < 10

∃ is defined in Data.Product as an alias for Σ 其中第一个参数是隐式的。这意味着 ∃ 正在获取类型 A → Set 的元素 B 并返回包含 A 类型的 a 和 b 类型 B a.

现在，λ m → m < 10 在 ℕ 中获取 m 并返回 m < 10.

的证明类型

所以 ∃ λ m → m < 10 是 ℕ 的对的类型和它小于 10 的证明。

表达式本身

zero , s≤s z≤n

对于整个类型检查，我们需要：

zero 成为 ℕ，它就是这样。

s≤s z≤n证明0 < 10。 _<_ 在 Data.Nat.Base 中定义为 λ m n → suc m ≤ n 的别名。所以证明 0 < 10 等同于证明 1 ≤ 10.

现在，_≤_ 是一个具有两个构造函数的归纳类型：

• 一个基本案例z≤n说0小于或等于所有自然数
• 步骤案例 s≤s 表示如果一个数字小于或等于另一个数字，则它们的 suc 也小于或等于。

证明 s≤s z≤n 确实是 1 ≤ 10 的有效证明： z≤n 证明 0 ≤ 9 并且 s≤s 得出结论因此 1 ≤ 10 .