外延公理：为什么它不是不可靠的

Question

外延性公理表示，如果两个函数在域的每个参数上的作用相等，则它们相等。

Axiom func_ext_dep : forall (A : Type) (B : A -> Type) (f g : forall x, B x),
  (forall x, f x = g x) -> f = g.

定理语句两边的等式= 是命题等式（具有单个eq_refl 构造函数的数据类型）。使用这个公理可以证明 f = a + b 和 g = b + a 在命题上是相等的。

但是f和g作为数据结构显然不相等。

你能解释一下我在这里遗漏了什么吗？可能函数对象没有正常形式？

Answer 1

编辑：在评论中进一步讨论后，实际的混淆点是：

Doesn't match a with... = match b with gives me False right away the same way as S S Z = S Z does?

您可以在 nat 上进行模式匹配，但不能在函数上进行。依赖模式匹配是我们如何证明构造函数的单射性和不相交性的方法，而我们对函数唯一能做的就是应用它。（另见）

尽管如此，我希望下面的其余答案仍然具有指导意义。

来自评论：

AFAIU, = has a very precise meaning in Coq/CIC - syntactic equality of normal forms.

这是不对的。例如我们可以证明如下：

Lemma and_comm : forall a b : bool, (* a && b = b && a *)
   match a with
   | true => b
   | false => false
   end = match b with
         | true => a
         | false => false
         end.
Proof.
  destruct a, b; reflexivity.
Qed.

我们只能使用 eq_refl 当双方在句法上相等时，但是除了归纳命题的构造函数之外，我们还可以应用更多的推理规则，最显着的是依赖模式匹配，并且，如果我们承认吧，功能可扩展性。

But f and g are obviously not equal as data structures.

这种说法似乎混淆了可证明性和真实性。区分这两个世界很重要。（而且我不是逻辑学家，所以请对我要说的话持保留态度。）

Coq 是一种符号推动游戏，具有明确定义的规则来构造某些类型的项。这就是可证明性。当 Coq 接受一个证明时，我们所知道的就是我们按照规则构造了一个项。

当然，我们也希望这些术语和类型具有某种意义。当我们证明一个命题时，我们希望它能告诉我们一些关于世界状况的信息。这是事实。在某种程度上，Coq 在这件事上几乎没有发言权。当我们阅读 f = g 时，我们正在为符号 f 赋予意义，为 g 赋予意义，同时也为 = 赋予意义。这完全取决于我们（好吧，总是有规则可循），并且有不止一种解释（或"model"）。

大多数人心目中的 "naive model" 认为函数是输入和输出之间的关系（也称为图形）。在这个模型中，函数外延性成立：一个函数只不过是输入和输出之间的映射，所以具有相同映射的两个函数是相等的。函数可扩展性在 Coq 中是合理的（我们无法证明 False），因为至少有一个模型是有效的。

在您的模型中，函数的特征在于它的代码，对一些方程取模。（这或多或少是 "syntactic model"，在这里我们将每个表达式解释为它本身，具有尽可能少的语义行为。）然后，确实存在扩展相等但代码不同的函数。所以函数扩展性在这个模型中是无效的，但这并不意味着它在 Coq 中是错误的（即，我们可以证明它的否定），如前所述。

f 和 g 不是 "obviously not equal"，因为平等与其他事物一样，是相对于特定解释的。

外延公理：为什么它不是不可靠的

Extensionality axiom: why is it not unsound

theorem-proving

coq