外延相等谓词和普遍量化应用的相等性

Question

我正在尝试使用有充分根据的固定点来定义递归谓词，并有义务证明 F_ext when rewriting with Fix_eq. The CPDT 说 大多数此类义务都可以通过简单的证明自动化来解除 ，但不幸的是，我的谓词似乎并非如此。

我已将问题简化为以下引理（来自 Proper (pointwise_relation A eq ==> eq) (@all A)）。在没有 additional axioms 的情况下是否可以在 Coq 中证明？

Lemma ext_fa:
  forall (A : Type) (f g : A -> Prop),
    (forall x, f x = g x) ->
    (forall x, f x) = (forall x, g x).

它可以用谓词或函数的外延性来证明，但由于结论比通常的结论弱 (f = g) 我天真地认为可以在不使用额外公理的情况下产生一个证明。毕竟等号两边只涉及f和g的应用；如何辨别任何内涵差异？

我是不是漏掉了一个简单的证明或者这个引理无法证明？

Answer 1

您可能对 this code I wrote a while ago 感兴趣，它包括 Fix_eq 的变体，用于各种数量的参数，并且不依赖于函数扩展性。请注意，您不需要更改 Fix_F，而只需证明 Fix_eq.

的变体即可

为了回答您提出的问题，而不是解决您的上下文，您陈述的引理称为 "forall extensionality"。

存在于Coq.Logic.FunctionalExtensionality中，这里用函数外延公理来证明。标准库版本使用公理来证明这个引理这一事实至少有力地证明了在 Coq 中没有公理它是不可证明的。

这是该事实的证明草图。由于 Coq 是强规范化*，空上下文中 x = y 的每个证明在判断上都等于 eq_refl。也就是说，如果你能在空上下文中证明x = y，那么x和y是可转换的。让f x := inhabited (Vector.t (x + 1))，让g x := inhabited (Vector.t (1 + x))。通过对 x 的归纳可以直接证明 forall x, f x = g x。因此，如果你的引理在没有公理的情况下为真，我们可以得到

的证明

(forall x, inhabited (Vector.t (x + 1))) = (forall x, inhabited (Vector.t (1 + x)))

在空上下文中，因此 eq_refl 应该证明这个说法。我们可以很容易地检查并看到 eq_refl 并不能证明这个说法。所以你的引理 ext_fa 没有公理是不可证明的。

请注意，函数的相等性和类型的相等性在 Coq 中严重不足。本质上，您可以在 Coq 中证明相等的唯一类型（或函数）是判断相等的类型（或者，更准确地说，可以表示为两个应用于可证明相等封闭项的判断相等的 lambda 的类型）。唯一可以证明不相等的类型是可证明不是同构的类型。您可以证明不相等的唯一函数是可证明在您提供的域的某些具体元素上不同的函数。在你可以证明的等式和你可以证明的不等式之间有很多 space，你不能在没有公理的情况下谈论这个 space 中的任何事情。

*Coq 实际上并不是强归一化的，因为共电感存在一些问题。但是取模，它是强烈归一化的。

外延相等谓词和普遍量化应用的相等性

Extensionally equal predicates and equality of universally quantified applications

theorem-proving

coq