Fail to `destruct` due to ill-typedness and even cannot give an exact term in Coq

huangapple go评论53阅读模式
英文:

Fail to `destruct` due to ill-typedness and even cannot give an exact term in Coq

问题

以下是您要翻译的内容:

Set Implicit Arguments.

Inductive fun_eq A B (f : A -> B) : forall C D, (C -> D) -> Prop :=
  fun_eqrefl : forall g : A -> B, f = g -> fun_eq f g.

Lemma fun_eq0 A B (f g : A -> B) : fun_eq f g -> f = g.
Proof. intros H. destruct H.

destruct H. 失败并显示错误消息:

Abstracting over the terms "A", "B" and "g" leads to a term
fun (A0 B0 : Type) (g0 : A0 -> B0) => f = g0 which is ill-typed.
Reason is: Illegal application: 
The term "@eq" of type "forall A : Type, A -> A -> Prop" cannot be applied to the terms
 "A0 -> B0" : "Type"
"f" : "A -> B"
"g0" : "A0 -> B0"
The 2nd term has type "A -> B" which should be coercible to
 "A0 -> B0".

我认为对于这种类型的错误,有两种解决方法,但在这种情况下都不起作用。

  • 一种方法是承认 proof_irrelevance。但是,无法构造 fun_eq f g 的交替证明,因为 fun_eqrefl 的参数就是我们想要的。

  • 另一种方法是使用 refine 提供一个确切的术语,但我无法想出这样的术语。而且,如果存在这样的术语(它将涉及 match 语句),我怀疑我的先前问题可以以类似的方式解决。

是否可能证明 fun_eq0?如果可以,如何做到?

英文:

I tried to implement the following Coq code:

Set Implicit Arguments.

Inductive fun_eq A B (f : A -> B) : forall C D, (C -> D) -> Prop :=
  fun_eqrefl : forall g : A -> B, f = g -> fun_eq f g.

Lemma fun_eq0 A B (f g : A -> B) : fun_eq f g -> f = g.
Proof. intros H. destruct H.

But destruct H. fails with an error message:

Abstracting over the terms "A", "B" and "g" leads to a term
fun (A0 B0 : Type) (g0 : A0 -> B0) => f = g0 which is ill-typed.
Reason is: Illegal application: 
The term "@eq" of type "forall A : Type, A -> A -> Prop" cannot be applied to the terms
 "A0 -> B0" : "Type"
"f" : "A -> B"
"g0" : "A0 -> B0"
The 2nd term has type "A -> B" which should be coercible to
 "A0 -> B0".

I think there would be two workarounds for this kind of error, neither of which worked in this case.

  • One is to admit the proof_irrelevance. However, it is impossible to construct an alternating proof for fun_eq f g because the argument of fun_eqrefl is what we want.

  • Another way is to provide an exact term using refine, but I couldn't come up with such a term. Also, if there were such a term (it would involve match statement), I suspect my previous question could be solved in a similar way.

Is it possible to prove fun_eq0? If so, how can it be done?

答案1

得分: 2

你可以使用 UIP(eq的证明不可知性的特殊情况)来证明它。

技巧是将等式f的一侧重写为cast eq_refl f,其中cast:A = B -> A -> B,并使用UIP/证明不可知性来用H: fun_eq f g假设得到的等式证明替换eq_refl。这样,当你解构H时,LHS的类型会与RHS的类型同时改变。

英文:

You can prove it using UIP (special case of proof irrelevance for eq).

The trick is to rewrite one side of the equality f to cast eq_refl f, where cast : A = B -> A -> B, and use UIP/proof irrelevance to replace eq_refl with an equality proof obtained from the H : fun_eq f g assumption. That way, when you destruct H, the type of the LHS changes simultaneously with the type of the RHS.

Set Implicit Arguments.
From Coq Require Import ProofIrrelevance.

Inductive fun_eq A B (f : A -> B) : forall C D, (C -> D) -> Prop :=
  fun_eqrefl : forall g : A -> B, f = g -> fun_eq f g.

(* Extract the equality on types *)
Definition fun_eq_tyeq {A B C D} (f : A -> B) (g : C -> D) (H : fun_eq f g) : (A -> B) = (C -> D) :=
  match H with
  | fun_eqrefl _ => eq_refl
  end.

Definition cast A B (e : A = B) (x : A) : B := eq_rect A (fun T => T) x B e.

Lemma fun_eq0 A B (f g : A -> B) : fun_eq f g -> f = g.
Proof.
  intros H.
  change (cast eq_refl f = g).
  replace eq_refl with (fun_eq_tyeq H) by apply UIP.
  destruct H.
  cbn.
  auto.
Qed.

huangapple
  • 本文由 发表于 2023年2月18日 01:22:35
  • 转载请务必保留本文链接:https://go.coder-hub.com/75487415.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定