问题 Coq中的“错误:宇宙不一致”是什么意思?


我正在努力 软件基础 我现在正在做教会数字的练习。这是自然数的类型签名:

Definition nat := forall X : Type, (X -> X) -> X -> X.

我已经定义了一个函数 succ 类型 nat -> nat。我现在想定义一个这样的加法函数:

Definition plus (n m : nat) : nat := n nat succ m.

但是,我收到以下错误消息:

Error: Universe inconsistency.

这个错误信息实际意味着什么?


3932
2017-08-22 07:47


起源

你可以通过 -type-in-type 标记为Coq以禁用所有Universe一致性检查。使用这个标志是危险的,因为它使Girard的悖论成为可能(解释说 这里)。 - Konstantin Weitz
注意 -type-in-type 仅适用于Coq 8.5 beta(不适用于目前稳定的8.4版本) - Catalin Hritcu


答案:


在Coq,一切都有类型。 Type 也不例外:如果你问Coq Check 命令,它会告诉你它的类型是...... Type

实际上,这有点谎言。如果您通过发布指令要求更多详细信息 Set Printing Universes.,Coq会告诉你那个 Type 与第一个不同,但是“更大”。每个人都是正式的 Type 有一个与之关联的索引,称为Universe级别。通常在打印表达式时,此索引不可见。因此,该问题的正确答案是 Type_i 有类型 Type_j,对于任何索引 j > i。这需要确保Coq理论的一致性:如果只有一个 Type如果假设存在一组所有集合,那么就有可能表现出一种矛盾,类似于如何在集合理论中产生矛盾。

为了更容易使用类型索引,Coq为您提供了一些灵活性:没有类型实际上有与之关联的固定索引。相反,Coq每次编写时都会生成一个新的索引变量 Type,并跟踪内部约束,以确保它们可以使用满足理论要求的限制的具体值进行实例化。

您看到的错误消息意味着Coq的Universe级别约束求解器表示无法解决您要求的约束系统。问题是, forall 在定义中 nat 量化了 Type_i,但是Coq的逻辑力量 nat 本身就是一种类型 Type_j,与 j > i。另一方面,申请 n nat 要求 j <= i,导致一组不可满足的索引约束。


14
2017-08-22 12:56



有没有办法通过迭代succ函数来定义加号,就像OP试图做的那样,并让它进行类型检查?我设法做到的唯一方法是通过内联succ和零的定义,结果看起来非常可怕。 - hugomg
@hugomg添加 Set Universe Polymorphism. 之前 nat的定义。那应该可以解决问题。 - Anton Trunov
@hugomg而不是将添加定义为 n succ m,您可以将其定义为 λ f. λ x. n f (m f x)。 - augurar
当然,但你不能用取幂来做类似的事情。您必须将其定义为迭代乘法。 - hugomg
@hugomg您可以定义取幂 无 迭代乘法。见 教会编码 维基百科上的条目。它在Coq中几乎相同,你只需要弄清楚类型参数。 - Anton Trunov