如何重写给定的两个依赖类型在 Coq 中是相等的

Question

我正在使用 bbv 库中的位向量进行证明，看起来像 word : nat -> Set。如果你砍掉一些低阶位，我试图证明最高有效位是相同的：

Require Import bbv.Word.
Require Import Coq.Arith.PeanoNat.
Require Import Coq.Arith.Plus.

Lemma drop_msb : forall (n : nat) (x : word (S (S n))),
  wmsb x false = wmsb (wtl x) false.

为了证明这一点，以下引理似乎很有用：

Check wmsb_split2.
(*
wmsb_split2 :
  forall sz (w: word (sz + 1)) b,
    wmsb w b = if weq (split2 _ 1 w) (natToWord _ 0) then false else true.
*)

现在，这是我的证明尝试：

Proof.
  intros n x.
  assert (Snp : S (S n) = S n + 1). {
    rewrite <- Nat.add_1_l.
    apply plus_comm.
  }
  assert (xeq : word (S (S n)) = word ((S n) + 1)). {
    rewrite Snp.
    reflexivity.
  }
  rewrite wmsb_split2. (* Error: Found no subterm matching "wmsb ?M1864 ?M1865" in the current goal. *)

这是证明状态。

  n : nat
  x : word (S (S n))
  Snp : S (S n) = S n + 1
  xeq : word (S (S n)) = word (S n + 1)
  ============================
  wmsb x false = wmsb (wtl x) false

我很困惑为什么 wmsb_split2 不能应用；我在结论中看到了 wmsb _ _！我是否需要 EqDepFacts 中给出的某种形式的身份证明的唯一性？

我也有额外的断言，以防我需要重写 x，但我也做不到。

Answer 1

有一个更简单的计算证明：因为word被定义为一个由长度索引的位列表，如果你知道长度是S (S n)，那么前两个构造函数该列表是唯一确定的，并且该事实由引理 destruct_word_S.

提供

destruct_word_S :
  forall (sz : nat) (w : word (S sz)),
    exists (v : word sz) (b : bool), w = WS b v

在这种情况下，这允许您将 x : word (S (S n)) 重写两次，变成某个术语 WS b0 (WS b1 x'')，从而使 wmsb 和 wtl 都可以计算。

要使用destruct_word_S重写，你必须破坏两个exists来暴露等式w = WS b v。

Lemma drop_msb : forall (n : nat) (x : word (S (S n))),
  wmsb x false = wmsb (wtl x) false.
Proof.
  intros.
  destruct (destruct_word_S x) as [x' [b0 Ex]].
  destruct (destruct_word_S x') as [x'' [b1 Ex']].
  rewrite Ex.
  rewrite Ex'. cbn.
  (* Goal: wmsb x'' b1 = wmsb x'' b1 *)
  reflexivity.
Qed.

I'm confused why wmsb_split2 can't be applied; I see wmsb _ _ right there in the conclusion!

单词的长度是 wmsb 的隐式参数，这就是这里没有统一的地方：wmsb_split2 引理使用 @wmsb (sz + 1) 而你的目标使用 @wmsb (S (S n)) 在左侧，@wmsb (S n) 在右侧。但是 sz + 1 不能转换为 S (S n)（即，对于 sz 的任何实例化，它们不能归一化为相同的术语）。

在处理索引类型时，例如按长度索引的 word，等式的表现非常不直观。

我发现在这种情况下行之有效的是倒置原则，例如 destruct_word_S，根据齐次等式制定，即 =/ eq，两边类型相同

相比之下，异构平等会带来麻烦，这就是当您开始考虑 "a word (S sz) is also a word (sz + 1)" 时遇到的问题，试图将不同类型的事物等同起来.

遗憾的是，除了学习依赖类型理论的不太令人满意的途径，将 eq 视为 "just another inductive type" 之外，我不知道在这里获得正确直觉的好方法，意识到它不像 "equality".

的天真想法那样表现的所有方式

如何重写给定的两个依赖类型在 Coq 中是相等的

How to rewrite given two dependent types are equal in Coq

coq

dependent-type