英文:
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 forfun_eq f g
because the argument offun_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 involvematch
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论