Coq 功能扩展性

Question

我有一个目标，我想重写一个函数体，但是一些函数参数妨碍了重写。我已经用身份函数重新创建了这种情况。

如果函数是Defined，那么它可以工作，但是当函数是一个参数，我有一个公理说明如何重写，我是无法重写。

我只能通过假设功能扩展性来让它工作。是否可以在不假设功能扩展性的情况下以某种方式重写？

Axiom functional_extensionality: forall {A B} (f g:A->B) , (forall x, f x = g x) -> f = g.

Variables A B : Type.
Variable f : A -> B.

Definition Id (x : B) := x.         (* here my function is Defined *)

Goal (fun x => Id (f x)) = f.       (* I'd like to rewrite inside the fun *)

Proof. auto. Qed.                   (* This works (eta reduction). *)

Variable Id' : B -> B.              (* Here I don't have the function definition *)
Axiom ID     : forall x, Id' x = x. (* only proof that it does the same thing *)
Goal (fun x => Id' (f x)) = f. 
Proof.
  rewrite ID.                       (* this doesnt work *)
  eauto using functional_extensionality, ID. (* but this works *)

Answer 1

不幸的是，如果不假设功能可扩展性，就无法证明这一点； Coq 要求 fun x => Id' (f x)) = fun x => f x 持有 "definitionally".

这里的"definitionally"是什么意思？简而言之，这意味着两个术语在语法上必须具有相同的范式。回想一下，在 Coq 中，每个项都有一个（主要）由 beta 减少引起的范式。

然而，我们只知道Id' x = x"judgementally"。因此，Coq 无法执行缩减 Id' x ~> x，从而防止以上两项变得相等 "definitionally".

这确实是 Coq 理论的局限性，据我所知，类型检查仍然是可判定的。

完成此证明的另一种方法是推导满足此方程的唯一函数是 fun x => x（参数性）。这将为您提供一个假设 Hid: ID' = (fun x => x)，您可以使用它来完成证明。不幸的是 Hid 在 Coq 内部无法证明。

Coq 功能扩展性

Coq functional extensionality

coq