为什么 UIP 在 Coq 中无法证明？为什么 match 构造泛化类型？

Question

如果需要，必须在 Coq 中公理地添加 UIP（以及公理 K 等等价物）：

uip : ∀ A (x y: A) (p q: x = y), p = q

这很令人惊讶，因为从只有一个构造函数的相等性定义来看，这是显而易见的。（这当然依赖于 Coq 中的归纳定义捕获其类型的所有元素的解释）。

当一个人试图证明 UIP 时，一个人被困在反身子案例上：

uip_refl : ∀ A (x: A) (h: x = x), h = eq_refl x

我们可能希望以下术语是合适的证明术语：

fun A (x: A) (h: x = x) =>
  match h as h0 in (_ = a) return (h0 = eq_refl x) with
    | eq_refl _ => eq_refl (eq_refl x)
  end

这失败了，因为它的类型有误。我们知道 h: x = x，但是当我们匹配这个词时，我们丢失了自反性信息并且它被泛化为 h0: x = a。结果，我们的 return 类型 h0 = eq_refl x 类型错误。

为什么 match 构造在这里泛化了我们的类型？非泛化的替代方案是否易于处理？

Answer 1

如 , the eliminator for equality in Coq inherits this behavior from intensional type theory, where it was introduced to keep type checking decidable. However, later people realized that it is possible to have an elimination principle for equality that validates axiom K without ruining decidability. This is not implemented in Coq, but it is implemented in Agda 中所暗示：

module Test where

{- Equality type -}

data _≡_ {A : Set} (a : A) : A → Set where
  refl : a ≡ a

{- Proving K by pattern matching -}

K : {A : Set} → (a : A) → (p : a ≡ a) → p ≡ refl
K a refl = refl

（K 的等式在道德上等同于 Coq 中的 | eq_refl => ... 分支。）我不完全确定 Agda 如何检查这个定义，但我的印象是它不会需要像 Coq 一样的泛化步骤。

Answer 2

Would a non-generalizing alternative be tractable?

这样的比赛是有先例的。它在 Coq 的现成可用扩展中提供（在 Program 中；它也是 Equations plugin). Agda also typechecks pattern-matches in a similar manner (if --with-K is enabled, which is the default 中的一个选项）。

正如您所展示的，您可以用它来定义 UIP，因此不采用 UIP 的所有原因都适用于不采用该匹配项。相反，可以使用 UIP 将该匹配项编译为一个项，就像 Program and Equations 所做的那样。

我无法真正解释为什么“泛化”会有所不同。我敢打赌，答案就在 Conor McBride 的论文中。

为什么 UIP 在 Coq 中无法证明？为什么 match 构造泛化类型？

Why is UIP unprovable in Coq? Why does the match construct generalize types?

coq