Coq中相等类型证据的案例分析
case analysis on evidence of equality type in Coq
我对 Coq 中的归纳定义关系 eq 有疑问。考虑 Coq 中 eq 的以下定义：
Inductive eq (A : Type) (x : A) : A -> Prop := eq_refl : x = x
这是一个归纳定义的关系，就像le (<=)。因此，我应该能够对任何此类证据进行案例分析。
但是，当我尝试证明以下结果时，我无法成功。
Lemma true_num: forall m :nat, forall x y: m=m, x=y.
Proof. intros. destruct x.
(// Error: Abstracting over the terms "m" and "x" leads to a term
fun (m0 : nat) (x0 : m0 = m0) => x0 = y
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
"m0 = m0" : "Prop"
"x0" : "m0 = m0"
"y" : "m = m"
The 3rd term has type "m = m" which should be coercible to
"m0 = m0". )
我无法解码这个错误。
m=m 的唯一证明应该是 @eq_refl nat m 因为 eq_refl 是唯一的构造函数。因此，通过案例分析应该能够证明 x 和 y 相等。
这种推理有什么问题？
错误是由于 destruct 的工作方式造成的，回想一下该策略试图构建一个匹配语句，并且为了做到这一点，它有一些启发式方法可以将相关假设带入上下文。
特别是，在这种情况下，它试图抽象变量 m，它是 y : m = m 中 eq 归纳的索引；然而 y 没有进入上下文，因此错误为 m != m0 [m0 是抽象的 m]。您可以通过执行 "less smart" 匹配来解决该问题，这不会修改 m:
refine (match x with | @eq_refl _ _ => _ end).
但通常，最好的解决方案是将错误假设纳入范围：
revert y; destruct x.
另一方面，如其他优秀答案所指出的那样，要证明您的目标，简单的模式匹配是不够的。解决像您这样的目标的我首选的实用方法是使用库：
From mathcomp Require Import all_ssreflect.
Lemma true_num (m : nat) (x y : m = m) : x = y.
Proof. exact: eq_irrelevance. Qed.
在这种情况下，nat 类型的适当附加条件由库的机器自动推断。
The only proof for m=m should be @eq_refl nat m since eq_refl is the only constructor
没有。你的定理恰好是真的，因为你在谈论 nat 的相等性，但是如果你用 Type 替换 nat 并替换 nat 和 Type 使得定理无法证明。
问题在于相等类型 family 是由自反证明 自由生成的 。因此，由于 Coq 中的一切都以正确的方式尊重平等（这是我有点模糊的一点），要证明一个家庭中所有平等证明的 属性（即 [=15 的所有证明=] for some fixed x and for all y), 足以证明生成器的属性，自反证明。然而，一旦你修复了两个端点，可以这么说，你就不再拥有这个 属性。换句话说，eq的归纳原理实际上是{ y | x = y }的归纳原理，而不是x = y的归纳原理。类似地，向量（长度索引列表）的归纳原理实际上是 { n & Vector.t A n }.
的归纳原理
要解码错误消息，尝试手动应用 eq 的归纳原理可能会有所帮助。归纳原理指出：给定类型 A、项 x : A 和 属性 P : forall y : A, x = y -> Prop，以证明 P y e 对于任何给定的 y : A和任何证明e : x = y，足以证明P x eq_refl。 （要了解为什么这是有道理的，请考虑非依赖版本：给定类型 A、术语 x : A 和 属性 P : A -> Prop，对于任何 y : A和任何证明e : x = y，证明P y，足以证明P x。）
如果您尝试手动应用此方法，您会发现在尝试归纳第二个等式证明时无法构造类型良好的函数P。
有一篇很棒的博客 post 在此处更深入地解释了这一点：http://math.andrej.com/2013/08/28/the-elements-of-an-inductive-type/
我对 Coq 中的归纳定义关系 eq 有疑问。考虑 Coq 中 eq 的以下定义：
Inductive eq (A : Type) (x : A) : A -> Prop := eq_refl : x = x
这是一个归纳定义的关系，就像le (<=)。因此，我应该能够对任何此类证据进行案例分析。
但是，当我尝试证明以下结果时，我无法成功。
Lemma true_num: forall m :nat, forall x y: m=m, x=y.
Proof. intros. destruct x.
(// Error: Abstracting over the terms "m" and "x" leads to a term
fun (m0 : nat) (x0 : m0 = m0) => x0 = y
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
"m0 = m0" : "Prop"
"x0" : "m0 = m0"
"y" : "m = m"
The 3rd term has type "m = m" which should be coercible to
"m0 = m0". )
我无法解码这个错误。
m=m 的唯一证明应该是 @eq_refl nat m 因为 eq_refl 是唯一的构造函数。因此，通过案例分析应该能够证明 x 和 y 相等。
这种推理有什么问题？
错误是由于 destruct 的工作方式造成的，回想一下该策略试图构建一个匹配语句，并且为了做到这一点，它有一些启发式方法可以将相关假设带入上下文。
特别是，在这种情况下，它试图抽象变量 m，它是 y : m = m 中 eq 归纳的索引；然而 y 没有进入上下文，因此错误为 m != m0 [m0 是抽象的 m]。您可以通过执行 "less smart" 匹配来解决该问题，这不会修改 m:
refine (match x with | @eq_refl _ _ => _ end).
但通常，最好的解决方案是将错误假设纳入范围：
revert y; destruct x.
另一方面，如其他优秀答案所指出的那样，要证明您的目标，简单的模式匹配是不够的。解决像您这样的目标的我首选的实用方法是使用库：
From mathcomp Require Import all_ssreflect.
Lemma true_num (m : nat) (x y : m = m) : x = y.
Proof. exact: eq_irrelevance. Qed.
在这种情况下，nat 类型的适当附加条件由库的机器自动推断。
The only proof for m=m should be @eq_refl nat m since eq_refl is the only constructor
没有。你的定理恰好是真的，因为你在谈论 nat 的相等性，但是如果你用 Type 替换 nat 并替换 nat 和 Type 使得定理无法证明。
问题在于相等类型 family 是由自反证明 自由生成的 。因此，由于 Coq 中的一切都以正确的方式尊重平等（这是我有点模糊的一点），要证明一个家庭中所有平等证明的 属性（即 [=15 的所有证明=] for some fixed x and for all y), 足以证明生成器的属性，自反证明。然而，一旦你修复了两个端点，可以这么说，你就不再拥有这个 属性。换句话说，eq的归纳原理实际上是{ y | x = y }的归纳原理，而不是x = y的归纳原理。类似地，向量（长度索引列表）的归纳原理实际上是 { n & Vector.t A n }.
要解码错误消息，尝试手动应用 eq 的归纳原理可能会有所帮助。归纳原理指出：给定类型 A、项 x : A 和 属性 P : forall y : A, x = y -> Prop，以证明 P y e 对于任何给定的 y : A和任何证明e : x = y，足以证明P x eq_refl。 （要了解为什么这是有道理的，请考虑非依赖版本：给定类型 A、术语 x : A 和 属性 P : A -> Prop，对于任何 y : A和任何证明e : x = y，证明P y，足以证明P x。）
如果您尝试手动应用此方法，您会发现在尝试归纳第二个等式证明时无法构造类型良好的函数P。
有一篇很棒的博客 post 在此处更深入地解释了这一点：http://math.andrej.com/2013/08/28/the-elements-of-an-inductive-type/