破坏coq中依赖记录的相等性

Question

给定依赖记录类型：

Record FinPath : Type := mkPath { fp_head : S i;
                                  fp_tail : FinPathTail fp_head
                                }.

和两个Path类型的对象是相等的，我想推断它们的头和尾是相等的。问题是我很快得到了这种形式的东西：

fpH : {| path_head := fp_head fp; path_tail := fpt_to_pt (fp_tail fp) |} =
      {| path_head := fp_head fp'; path_tail := fpt_to_pt (fp_tail fp') |}

使用注入策略，我可以推断出 fp_head fp = fp_head fp' 还有这个术语：

existT (fun path_head : S i => PathTail path_head) (fp_head fp)
       (fpt_to_pt (fp_tail fp)) =
existT (fun path_head : S i => PathTail path_head) (fp_head fp')
       (fpt_to_pt (fp_tail fp'))

假设 S i 的可判定性，我通常会想使用 inj_pair2_eq_dec 但这在这种情况下不适用，因为 fp_head fp 和 fp_head fp' 不是t 在语法上相同。我也不能将它们重写为相同，因为用 fp_head fp' = fp_head fp 重写会使右侧输入错误。

我该如何继续？是否有更聪明的 inj_pair2_eq_dec 版本以某种方式使用（非句法）基数相等而不是要求 sigma 类型的基数相等？

编辑：仔细想想这个问题，我意识到要求尾部相等是没有意义的（因为它们属于不同类型）。但是是否有可能基于 eq_rect?

证明它们之间存在某种形式的莱布尼兹等式

Answer 1

像这样的问题是为什么许多人更喜欢避免 Coq 中的依赖类型。我将在 Coq sigma 类型 {x : T & S x} 的情况下回答你的问题，它可以推广到其他相关记录。

我们可以通过强制转换函数来表示对的依赖组件应满足的相等性：

Definition cast {T} (S : T -> Type) {a b : T} (p : a = b) : S a -> S b :=
  match p with eq_refl => fun a => a end.

Definition eq_sig T (S : T -> Type) (a b : T) x y
  (p : existT S a x = existT S b y) :
  {q : a = b & cast S q x = y} :=
  match p in _ = z return {q : a = projT1 z & cast S q x = projT2 z} with
  | eq_refl => existT _ eq_refl eq_refl
  end.

cast 函数允许我们使用等式 p : a = b 从 S a 转换为 S b。我通过证明项定义的 eq_sig 引理表示，给定两个依赖对 existT S a x 和 existT S b y 之间的等式 p，我可以生成另一个依赖对包含：

等式q : a = b，和
x 和 y 相等的证明转换后。

通过类似的定义，我们可以提供一个“归纳”的证明原理来证明依赖对之间的相等性：

Definition eq_sig_elim T (S : T -> Type) (a b : T) x y
  (p : existT S a x = existT S b y) :
  forall (R : forall c, S c -> Prop), R a x -> R b y :=
  match p in _ = z return forall (R : forall c, S c -> Prop), R a x -> R _ (projT2 z) with
  | eq_refl => fun R H => H
  end.

引理的形状类似于eq_sig，但是这次它表示在存在这样一个等式的情况下我们可以证明一个任意的dependent谓词 R b y 提供了 R a x.

的证明

使用这样的依赖原则可能会很尴尬。挑战在于找到这样一个 R 来表达你的目标：在上面的结果类型中， R 的第二个参数的类型相对于第一个参数是参数化的。在许多有趣的情况下，第二项的第一个组成部分 y 不是变量，但具有特定的形状，这可能会阻止直接概括。

破坏coq中依赖记录的相等性

Destructing equality of dependent records in coq

coq

dependent-type