Set 与 Prop 的可判定相等性声明

Question

在查看具有可判定相等性的类型的结果时（尤其是在 Eqdep_dec 中），有些结果（对于类型 A）需要

  forall x y : A, x = y \/ x <> y

而有些则需要

  forall x y : A, {x = y} + {x <> y}

我的印象是它是最后一个被称为可判定相等性的，但我非常不确定有什么区别。我知道 Prop 中的 x = y \/ x <> y 和 Set 中的 {x = y} + {x <> y}，我可以从第二个证明第一个，但不能反过来。据我了解，这是因为不允许我从 Set.

类型的值构造 Prop 类型的值

谁能说出这两者的区别是什么？是否有一些类型的例子可以证明第一个陈述但不能证明第二个陈述。另外，带 {x = y} + {x <> y} 的版本是否就是所谓的可判定相等性？

Answer 1

你说得对，Set 中的后一个定义被称为 可判定相等性。

直觉上，我们将 Set 中的对象解释为程序，将 Prop 中的对象解释为证明。所以可判定的相等类型是一个函数的类型，它接受某种类型的任意两个元素 A 并决定它们是否相等。

另一种说法稍弱一些。它描述了 A 中任意两个元素要么相等要么不相等的命题。值得注意的是，我们将无法检查哪个结果是 x 和 y 的特定值的情况，至少在证明中的案例分析之外。这是您提到的 Prop 消除限制的结果（尽管您倒退了：不允许通过 eliminating/matching 构造排序 Set/Type 的值在 Prop).

排序的元素上

不加公理，Prop宇宙是构造性的，所以我相信不会有任何类型A等式是不可判定的，但命题变体是可证明的。但是，考虑我们通过添加以下公理使 Prop 宇宙成为经典宇宙的场景：

Axiom classic : forall P, P \/ ~P

这将使命题变体对于任何类型都可以简单证明A，而可判定的等式可能无法实现。

请注意，我们的公理是一个命题。直觉上，命题或其否定必须成立是有道理的。如果我们没有将其设为 Prop（例如，如果我们将 forall P, {P} + {~P} 公理化），那么我们可能不会接受该公理，因为它会宣布存在通用决策程序。

这有点题外话，但希望它表明我们对 Props 和 Sets 的解释存在一些差异。

Set 与 Prop 的可判定相等性声明

Decidable equality statement with Set vs. Prop

coq